Interaction nets
Encyclopedia
Interaction nets are a low level graphical computation paradigm first proposed by Yves Lafont and based on Jean-Yves Girard
's proof net
s 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, 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, evaluator
s for lambda calculus
available today.
Software See also on its package on HackageDB.
Jean-Yves Girard
Jean-Yves Girard is a French logician working in proof theory. His contributions include a proof of strong normalization in a system of second-order logic called system F; the invention of linear logic; the geometry of interaction; and ludics...
Proof net
In proof theory, proof nets are a geometrical method of representing proofs thateliminates two forms of bureaucracy that differentiates proofs: irrelevant syntactical features of regular proof calculi such as the natural deduction calculus and the sequent calculus, and the order of rules applied...
s for linear logic
Linear logic
Linear logic is a substructural logic proposed by Jean-Yves Girard as a refinement of classical and intuitionistic logic, joining the dualities of the former with many of the constructive properties of the latter...
. 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, interaction nets enforce linearity -- each resource is used exactly once --, from which we can derive strong confluence
Confluence (term rewriting)
In computer science, confluence is a property of rewriting systems, describing that terms in this system can be rewritten in more than one way, to yield the same result. This article describes the properties in the most abstract setting of an abstract rewriting system.- Motivating example :Consider...
. Thus, they provide a natural language for massive parallelism.
They are also at the heart of the efficient and optimal, in Levy's sense, evaluator
Evaluation strategy
In computer science, an evaluation strategy is a set of rules for evaluating expressions in a programming language. Emphasis is typically placed on functions or operators: an evaluation strategy defines when and in what order the arguments to a function are evaluated, when they are substituted...
s for lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
available today.
External links
Assisted drawing in LaTeX See also examples on http://www.fauskes.net/pgftikzexamples/interaction-nets/.Software See also on its package on HackageDB.