Interaction Nets

Compute by replacing principal-port-connected pairs of fixed-arity graph agents with interface-preserving local nets under a one-rule-per-agent-pair discipline, so distinct redexes are disjoint and reductions are strongly confluent by construction.

Version

v2 · 2026-09-19 · History

Domain-specific #

2085

Domain group

Applied Sciences & Engineering

Origin domain

Computer Science & Software Engineering

Subdomains

Theoretical Computer Science, Graph Rewriting and Models of Computation → Computer Science & Software Engineering

Aliases

Interaction net

Core Idea

Interaction nets are a restricted graph-rewriting model of computation introduced by Yves Lafont. A program state is a port graph whose vertices are labeled agents. Every agent has exactly one distinguished principal port and a fixed number of auxiliary ports determined by its symbol. Computation occurs only when two agents meet principal port to principal port, forming an active pair. A rule replaces that pair with another net while preserving all connections by which the pair met the surrounding graph.

How would you explain it like I'm…

Special-Hand Block Swaps

Imagine building blocks joined by strings, and each block has one special hand. Nothing happens until two blocks hold special hands. Then those two get swapped for new blocks by a rule, and the strings to everything else stay attached. Because each block has only one special hand, swaps never get in each other's way.

Box-and-Wire Swap Computing

Interaction nets are a way to do computing by changing a drawing made of dots and wires. Each dot is an agent with one special main connector and some extra connectors. Things only happen when two agents are joined main-connector to main-connector. Then a rule replaces that pair with a new little drawing, keeping all the outside wires hooked up. There's only one rule for each kind of pair, and an agent can be in only one pair at a time. Because of that, different changes never clash and can even happen at the same time. If you reach a finished answer, it's always the same one. That doesn't mean every drawing finishes, though.

Principal-Port Graph Rewriting

Interaction Nets, introduced by Yves Lafont, are a restricted graph-rewriting model of computation. A program is a graph of labeled agents; each has one principal port and a fixed number of auxiliary ports. Rewriting happens only at an active pair, two agents connected through their principal ports, and a rule replaces the pair with a new net while preserving its connections to the rest. With at most one rule per pair of agent kinds and one principal port per agent, active pairs never overlap, so rewrites can happen in any order or in parallel. This gives strong confluence: a finished result, if reachable, is unique. But that doesn't promise the computation ever finishes or that parallel hardware will run it cheaply, and even copying and erasing must be done by explicit agents.

 

Interaction Nets are Lafont's restricted graph-rewriting model. A net is a port graph whose vertices are agents labeled by symbols; each symbol fixes one principal port and a set number of auxiliary ports. The only redexes are active pairs, agents joined principal-to-principal, and a rule rewrites such a pair into a new net while preserving its interface to the surrounding graph. The system allows at most one rule per unordered pair of symbols, and since each agent has one principal port it belongs to at most one active pair. Redexes are therefore disjoint and their local rewrites commute, giving the one-step diamond property (strong or uniform confluence): divergent single steps rejoin in one step each, and any reachable normal form is unique up to graph isomorphism. Copying, erasure, sharing, and substitution must all be explicit agents and wires, and disjoint active pairs expose parallelism without a global evaluation order. Confluence does not imply termination, large parallel width, bounded cost, or synchronization-free hardware. Typed systems are an important variant, but types are not required; untyped systems such as interaction combinators are genuine interaction nets.

Scope of Application

The core scope is theoretical computer science: graph rewriting, models of computation, declarative programming, functional-language implementation, linear logic, and parallel reduction. Interaction nets can serve as a high-level visual programming formalism or as a low-level target into which another calculus is compiled. Their interface-preserving rules support compositional construction; their explicit resource agents expose copying and erasure; and their local steps map naturally to pointer-rewiring implementations.

Clarity

A candidate is an interaction-net system only if all of these questions have satisfactory answers:

1. What is the signature, and what fixed arity belongs to each agent symbol?
2. Which port is the unique principal port of every agent occurrence?
3. Are edges linear—at most one edge incident to each port—and which free ports form the interface?
4. Does rewriting trigger only on principal–principal active pairs?

Manages Complexity

Interaction nets manage rewriting complexity by making critical overlap impossible at the primitive level. In a general rewrite system, proving confluence may require enumerating and joining critical pairs. Here the one-principal-port restriction prevents one agent from participating in two active pairs, while the one-rule-per-symbol-pair restriction removes ambiguity at a redex. The calculus obtains local diamond behavior from representation design rather than a global theorem proved separately for each program.

Abstract Reasoning

Redex-independence inference. If two applicable active pairs are distinct, they share no agent. Their one-step reductions commute. An evaluator may schedule either first or execute both in parallel without changing the joined semantic state.

Unique-normal-form inference. Strong confluence implies at most one normal form when one is reachable. It does not prove that reduction terminates, that a normal form exists, or that a scheduler will reach it under an unfair strategy.

Knowledge Transfer

Literal transfer occurs among interaction-net systems with different signatures. Arithmetic agents, lambda-calculus agents, linear-logic connectives, universal interaction combinators, process-network nodes, and implementation-oriented instructions preserve the same one-principal-port, active-pair, unique-rule, interface-preserving rewrite skeleton. The domain vocabulary changes while the model of computation remains identical.

Transfer also occurs between graphical and textual presentations. A name can represent a wire, a term can represent an agent tree rooted at a port, and an equation can connect two roots.

Relationships to Other Abstractions

Current abstraction Interaction Nets Domain-specific

Parents (1) — outgoing typed relations

• Interaction Nets is a kind of Network Prime

  The broader abstraction is live prime:network.

Hierarchy path (1) — routes to 1 parentless root

• Interaction Nets → is a kind of Network

Neighborhood in Abstraction Space

Interaction Nets sits in a sparse region of the domain-specific corpus (94^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

• Node graph architecture — 0.78
• Two-Terminal Series–Parallel Graph — 0.78
• Activity Diagram — 0.77
• Interface segregation principle — 0.77
• Multi-User Dungeon — 0.77

Computed from structural-signature embeddings · 2026-10-25