Interaction nets (Ofer Abarbanel online library)

Interaction nets are a graphical model of computation devised by Yves Lafont in 1990[1] 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[2] and optimal, in Lévy’s sense, Lambdascope.[3]

References

  1. ^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. ISBN 0897913434.
  2. ^Mackie, Ian (2008). “An Interaction Net Implementation of Closed Reduction”. Implementation and Application of Functional Languages: 20th International Symposium. Lecture Notes in Computer Science. 5836: 43–59. doi:10.1007/978-3-642-24452-0_3. ISBN 978-3-642-24451-3.
  3. ^van Oostrom, Vincent; van de Looij, Kees-Jan; Zwitserlood, Marijn (2010). “Lambdascope: Another optimal implementation of the lambda-calculus” (PDF).
  4. ^Fernández, Maribel; Mackie, Ian (1999). “A calculus for interaction nets”. Principles and Practice of Declarative Programming. Lecture Notes in Computer Science. Springer. 1702: 170–187. doi:10.1007/10704567. ISBN 978-3-540-66540-3.
  5. ^Lafont, Yves (1997). “Interaction Combinators”. Information and Computation. Academic Press, Inc. 137 (1): 69–101. doi:10.1006/inco.1997.2643.
  6. ^Fernández, Maribel; Khalil, Lionel (2003). “Interaction Nets with McCarthy’s Amb: Properties and Applications”. Nordic Journal of Computing. 10 (2): 134–162.

Ofer Abarbanel – Executive Profile

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library