Interaction nets are a model of computation (developed by Lafont in 1990s) based on paradigm of interaction, they are an inherently distributed form of computation.

Agents

Agents are nodes with:

• one principal port (outgoing edge depicted with arrow)
• set of $n$ auxiliary ports (other connected edges, ordered)
• a type that determines its interactions (node symbol)

Agents correspond with functions.

Nets

An interaction net is a graph of agents, where agents are connected at their ports. Ports are connected 1-to-1. If a port is not connected to another agent, we say it is free. The interface of a net is its set of free ports. Nets correspond with programs.

There are two special nets:

• the empty net
• wirings (nets with only edges)

Active Pairs

A pair of agents which are connected by their primary ports are called an active pair. (we draw a parallel to redexes)

Interaction Rules

An interaction rule replaces an active pair of agents $(\alpha ,\beta )$ by a new net $N$. The new net must have the same interface as the active pair. There can be at most one interaction rule for each pair of agent types. The reduction is local so only agents in the active pair are rewritten.

Natural Numbers

We can define natural numbers over a 0 agent and the successor agent $S$.

Addition

Example: addition in practice

Erasing Agent

The erasing agent is helpful to erase sub-nets (e.g. $x_1$ to $x_n$)

Duplication Agent

The duplicating agent is helpful to copy the same operation (e.g. $\alpha$) to two sub-nets (e.g. $d_1$ and $d_2$)

Multiplication

Rule 2: $\text{mult}(x,y)=\text{mult}(x,y-1)+x$

Slides 13-15

Normal Forms

When do we stop applying interaction rules to a net? Normal form: stop when there are no more active pairs

Not all nets have a normal form, some can be non-terminating:

Confluence

Interactions nets have strong confluence (the diamond property).

If $A$ and $B$ are interaction nets, we use $A\Rightarrow B$ to denote that $B$ can be obtained through a single interaction rule from $A$.

The property of strong confludence tells us that if $M\Rightarrow M_1$ and $M\Rightarrow M_2$ then there exists a term $M_3$ such that $M_1\Rightarrow M_3$ and $M_2\Rightarrow M_3$.

This property makes interaction nets suitable for representing distributed computations, since computational steps can take place in parallel.

Non-deterministic extension

Interaction nets are inherently deterministic, even with many active pairs, each is reduced in isolation.

Possible non-deterministic extensions include:

1. allowing multiple interaction rules for each pair of agents, from which one will be chosen at random for each active pair
2. allowing edges that connect more than two ports, where branch is chosen at random
3. allowing agents to have multiple principal ports - ambiguous agents

amb agent

The amb agent has two principal ports. If an amb agent forms two active pairs, then the interaction is to be resolved at random.

Computational power of Interaction Nets

Any computation that can be encoded by Turing Machines or Lambda Calculus can be encoded by Interaction Nets. Therefore, Interaction Nets are a computationally equivalent model of computation.