Interaction nets

Interaction nets are a graphical model of computation devised by French mathematician Yves Lafont in 1989 as a generalisation of the proof structures of linear logic. An interaction net system is specified by a set of agent types and a set of interaction rules. Interaction nets are an inherently distributed model of computation in the sense that computations can take place simultaneously in many parts of an interaction net, and no synchronisation is needed. The latter is guaranteed by the strong confluence property of reduction in this model of computation. Thus interaction nets provide a natural language for massive parallelism. Interaction nets are at the heart of many implementations of the lambda calculus, such as efficient closed reduction and optimal, in Lévy's sense, Lambdascope.

Interaction nets are a graphical model of computation devised by French mathematician Yves Lafont in 1989 as a generalisation of the proof structures of linear logic. An interaction net system is specified by a set of agent types and a set of interaction rules. Interaction nets are an inherently distributed model of computation in the sense that computations can take place simultaneously in many parts of an interaction net, and no synchronisation is needed. The latter is guaranteed by the strong confluence property of reduction in this model of computation. Thus interaction nets provide a natural language for massive parallelism. Interaction nets are at the heart of many implementations of the lambda calculus, such as efficient closed reduction and optimal, in Lévy's sense, Lambdascope. An agent of type \alpha and with arity \text{ar}(\alpha) = n \ge 0 has one principal port and n auxiliary ports. Any port can be connected to at most one edge. Any edge is connected to exactly two ports. 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. 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. 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 \vec 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' . 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 . Agent \epsilon can be seen as an eraser, deleting resources; \delta as a duplicator; \gamma as a constructor, taking two resources and returning some third one- it can represent anything from binary operations, as addition and multiplication, up to general function application in the lambda calculus, taking terms f and x to produce f\, x . 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{align} &\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{align}

Text derived from https://en.wikipedia.org/w/index.php?oldid=1353990207 under CC BY-SA 4.0; modifications have been made.