Interaction nets

Interaction nets are a low level graphical computation paradigm first proposed by Yves Lafont and based on Jean-Yves Girard's proof nets for linear logic. An interaction net system comprises: a set of agents, each with one principal port and zero or more auxiliary ports; a set of rules between agents (there is at most one rule for every pair of agents); and a net on which the rules are to be applied. Compared to traditional term syntax and linear graph grammars, interaction nets enforce linearity -- each resource is used exactly once --, from which we can derive strong confluence. Thus, they provide a natural language for massive parallelism.

They are also at the heart of the efficient and optimal, in Levy's sense, evaluators for lambda calculus available today.

Definitions

Interactions nets are graph-like structures consisting of agents and edges.

An agent of type $\alpha$ and with arity ${\text{ar}}(\alpha )=n\geq 0$ has one principal port and $n$ auxiliary ports. Any port can be connected to at most one edge. Ports that are not connected to any edge are called free ports. Free ports together form the interface of an interaction net. All agent types belong to a set $\Sigma$ called signature.

An interaction net that consists solely of edges is called a wiring and usually denoted as $\omega$. A tree $t$ with its root $x$ is inductively defined either as an edge $x$, or as an agent $\alpha$ with its free principal port $x$ and its auxiliary ports $x_{i}$ connected to the roots of other trees $t_{i}$.

Graphically, the primitive structures of interaction nets can be represented as follows:

When two agents are connected to each other with their principal ports, they form an active pair. For active pairs one can introduce interaction rules which describe how the active pair rewrites to another interaction net. An interaction net with no active pairs is said to be in normal form. A signature $\Sigma$ (with ${\text{ar}}:\Sigma \rightarrow \mathbb {N}$ defined on it) along with a set of interaction rules defined for agents $\alpha \in \Sigma$ together constitute an interaction system.

Interaction calculus

Textual representation of interaction nets is called the interaction calculus and can be seen as a programming language.

Inductively defined trees correspond to terms $t::=\alpha (t_{1},\dots ,t_{n})\ |\ x$ in the interaction calculus, where $x$ is called a name.

Any interaction net $N$ can be redrawn using the previously defined wiring and tree primitives as follows:

which in the interaction calculus corresponds to a configuration

$c\equiv \langle t_{1},\dots ,t_{m}\ |\ v_{1}=w_{1},\dots ,v_{n}=w_{n}\rangle$,

where $t_{i}$, $v_{i}$, and $w_{i}$ are arbitrary terms. The ordered sequence $t_{1},...,t_{m}$ in the left-hand side is called an interface, while the right-hand side contains an unordered multiset of equations $v_{i}=w_{i}$. Wiring $\omega$ translates to names, and each name has to occur exactly twice in a configuration.

Just like in the $\lambda$-calculus, the interaction calculus has the notions of $\alpha$-conversion and substitution naturally defined on configurations. Specifically, both occurrences of any name can be replaced with a new name if the latter does not occur in a given configuration, and configurations are considered equivalent up to $\alpha$-conversion. In turn, substitution $t[x:=u]$ is the result of replacing the name $x$ in a term $t$ with another term $u$ if $x$ has exactly one occurrence in the term $t$.

Any interaction rule can be graphically represented as follows:

where $\alpha ,\beta \in \Sigma$, and the interaction net $N$ on the right-hand side is redrawn using the wiring and tree primitives in order to translate into the interaction calculus as $\alpha [v_{1},\dots ,v_{m}]\bowtie \beta [w_{1},\dots ,w_{n}]$ using Lafont's notation.

The interaction calculus defines reduction on configurations in more details than seen from graph rewriting defined on interaction nets. Namely, if $\alpha [v_{1},\dots ,v_{m}]\bowtie \beta [w_{1},\dots ,w_{n}]$, the following reduction:

$\langle {\vec {t}}\ |\ \alpha (t_{1},\dots ,t_{m})=\beta (u_{1},\dots ,u_{n}),\Delta \rangle \rightarrow \langle {\vec {t}}\ |\ t_{1}=v_{1},\dots ,t_{m}=v_{m},u_{1}=w_{1},\dots ,u_{n}=w_{n},\Delta \rangle$

is called interaction. When one of equations has the form of $x=u$, indirection can be applied resulting in substitution of the other occurrence of the name $x$ in some term $t$:

$\langle \dots t\dots \ |\ x=u,\Delta \rangle \rightarrow \langle \dots t[x:=u]\dots \ |\ \Delta \rangle$ or $\langle t\ |\ x=u,t=w,\Delta \rangle \rightarrow \langle {\vec {t}}\ |\ t[x:=u]=w,\Delta \rangle$.

An equation $x=t$ is called a deadlock if $x$ has occurrence in term $t$. Generally only deadlock-free interaction nets are considered. Together, interaction and indirection define the reduction relation on configurations. The fact that configuration $c$ reduces to its normal form $c'$ with no equations left is denoted as $c\downarrow c'$.

Properties

Interaction nets benefit from the following properties:

• locality (only active pairs can be rewritten);
• linearity (each interaction rule can be applied in constant time);
• strong confluence also known as one-step diamond property (if $c\rightarrow c_{1}$ and $c\rightarrow c_{2}$, then $c_{1}\rightarrow c'$ and $c_{2}\rightarrow c'$ for some $c'$).

These properties together allow massive parallelism.

Interaction combinators

One of the simplest interaction systems that can simulate any other interaction system is that of interaction combinators. Its signature is $\Sigma =\{\epsilon ,\delta ,\gamma \}$ with ${\text{ar}}(\epsilon )=0$ and ${\text{ar}}(\delta )={\text{ar}}(\gamma )=2$. Interaction rules for these agents are:

• $\epsilon \bowtie \alpha [\epsilon ,\dots ,\epsilon ]$ called erasing;
• $\delta [\alpha (x_{1},\dots ,x_{n}),\alpha (y_{1},\dots ,y_{n})]\bowtie \alpha [\delta (x_{1},y_{1}),\dots ,\delta (x_{n},y_{n})]$ called duplication;
• $\delta [x,y]\bowtie \delta [x,y]$ and $\gamma [x,y]\bowtie \gamma [y,x]$ called annihilation.

Graphically, the erasing and duplication rules can be represented as follows:

with an example of a non-terminating interaction net that reduces to itself. Its infinite reduction sequence starting from the corresponding configuration in the interaction calculus is as follows:

${\begin{aligned}&\langle \varnothing \ |\ \delta (\epsilon ,x)=\gamma (x,\epsilon )\rangle \rightarrow \\&\langle \varnothing \ |\ \epsilon =\gamma (x_{1},x_{2}),\ x=\gamma (y_{1},y_{2}),\ x=\delta (x_{1},y_{1}),\ \epsilon =\delta (x_{2},y_{2})\rangle \rightarrow ^{*}\\&\langle \varnothing \ |\ x_{1}=\epsilon ,\ x_{2}=\epsilon ,\ x=\gamma (y_{1},y_{2}),\ x=\delta (x_{1},y_{1}),\ x_{2}=\epsilon ,\ y_{2}=\epsilon \rangle \rightarrow ^{*}\\&\langle \varnothing \ |\ \delta (\epsilon ,x)=\gamma (x,\epsilon )\rangle \rightarrow \dots \end{aligned}}$

Non-deterministic extension

Interaction nets are essentially deterministic and cannot model non-deterministic computations directly. In order to express non-deterministic choice, interaction nets need to be extended. In fact, it is sufficient to introduce just one agent ${\text{amb}}$ with two principal ports and the following interaction rules:

This distinguished agent represents ambiguous choice and can be used to simulate any other agent with arbitrary number of principal ports. For instance, it allows to define a ${\text{ParallelOr}}$ boolean operation that returns true if any of its arguments is true, independently of the computation taking place in the other argument.

References

• Lafont, Yves (1990). "Interaction nets". Proceedings of the 17th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM: 95–108. doi:10.1145/96709.96718.
• Lafont, Yves (1997). "Interaction Combinators". Information and Computation. 137 (1). Academic Press, Inc.: 69–101. doi:10.1006/inco.1997.2643.
• Asperti, Andrea; Guerrini, Stefano (1998). The Optimal Implementation of Functional Programming Languages. Cambridge Tracts in Theoretical Computer Science. Vol. 45. Cambridge University Press. ISBN 9780521621120.
• Fernández, Maribel; Mackie, Ian (1999). "A calculus for interaction nets". Principles and Practice of Declarative Programming. Springer: 170–187. doi:10.1007/10704567.
• Fernández, Maribel; Khalil, Lionel (2003). "Interaction Nets with McCarthy's Amb: Properties and Applications". Nordic Journal of Computing. 10 (2): 134–162.
• Béchet, Denis; Lippi, Sylvain (2008). "Hard combinators". Electronic Notes in Theoretical Computer Science. 203 (1): 31–48. doi:10.1016/j.entcs.2008.03.032.
• Mackie, Ian (2008). "An Interaction Net Implementation of Closed Reduction". Implementation and Application of Functional Languages: 20th International Symposium: 43–59. doi:10.1007/978-3-642-24452-0_3.
• Fernández, Maribel (2009). "Interaction-Based Models of Computation". Models of Computation: An Introduction to Computability Theory. Springer Science & Business Media. pp. 107–130. ISBN 9781848824348.
• van Oostrom, Vincent; van de Looij, Kees-Jan; Zwitserlood, Marijn (2010). "Lambdascope: Another optimal implementation of the lambda-calculus" (PDF). {{cite journal}}: Cite journal requires |journal= (help)

External links

• de Falco, Marc. "tikz-inet. A set of tikz-based macros for drawing interaction nets".
• de Falco, Marc. "INL. Interaction Nets Laboratory".
• Vilaça, Miguel. "INblobs. An editor and interpreter for Interaction Nets".
• Asperti, Andrea. "The Bologna Optimal Higher-Order Machine".
• Salikhmetov, Anton. "JavaScript Engine for Interaction Nets".