Interaction Nets

Projects

• HVM/Bend website, orga, repo, discord
  • interaction combinators as a backend of a Python/Haskell-like language
  • focus on efficient, parallel, and optimal reduction of the lambda calculus without oracle
• Vine website, orga, repo, discord
  • interaction nets as a backend of a Rust-like language
  • focus on concurrency and interoperation between functional and imperative patterns
  • WIP FPGA hardware target ("Tendrils Compute", discord announcement)
• Inpla repo
  • focus on custom interaction rules and interaction calculus
• ∆-Nets website, repo
  • interactive translator from lambda calculus to ∆-Nets (variation of interaction nets)
• inet-forth repo
  • focus on custom interaction rules and interaction calculus in forth
• optiscope repo
  • efficient implementation of lambdascope
• GoI-Visualizer website, repo
  • interactive translator from lambda calculus to an interaction net-like token-passing encoding (GoI)
  • focus on enforcing reduction strategies by various applicator-token interactions
• PELCR repo
  • parallel environment for optimal lambda calculus reduction
• ingpu repo
  • an experimental GPU-based interaction nets evaluator
• Linr website
  • lightweight parallel computation server for interaction net reductions

Blog Posts

• 20XX: Buliga, Graphic Lambda Calculus, Universality of Interaction Combinators, more
• 20XX: Taelin, Symmetric Interaction Calculus, Optimal Evaluation in 10 Minutes, more
• 2023: Zicklag, Interaction Nets, Combinators, and Calculus
• 2025: Borba, Lazy and Strict Evaluation, Polarized Interaction Net Systems, Lambda Calculus Normalization with Interaction Nets
• 2025: Kidd, Interaction Nets and Cellular Automata

Videos

• 2023: Taelin, HVM: um Runtime Paralelo [English Subtitles]
• 2024: Higher-Order Company (Taelin, Carman, Abril and Borba), HVM2: Interaction Combinator Evaluator (FProPer24)
• 2024: Wolfram Institute (Murzin and Wiles), Introduction to Interaction Nets
• 2025: Coll, MLIR Interaction Networks Dialect
• 2025: Christopher and Marvin, Interaction Combinators: The Hidden Patterns of Computation

Research

General

• 1990: Lafont, "Interaction Nets." url
• 1991: Gay, "Interaction Nets." url
• 1994: Asperti and Laneve, "Interaction Systems I." url
• 1996: Asperti and Laneve, "Interaction Systems II." url
• 1997: Lafont, "Interaction Combinators." url
• 1998: Fernández and Mackie, "Coinductive techniques for operational equivalence of interaction nets." url
• 2003: Fernández and Mackie, "Operational Equivalence for Interaction Nets." url
• 2006: Ehrhard and Regnier, "Differential Interaction Nets." url
• 2013: Gimenez and Moser, "The Structure of Interaction." url
• 2016: Mackie and Sato, "In-place Graph Rewriting with Interaction Nets." url
• 2016: Mackie and Sato, "Parallel Evaluation of Interaction Nets: Case Studies and Experiments." url
• 2016: Gimenez and Moser, "The Complexity of Interaction." url

Implementation

• 2000: Pinto, "Sequential and Concurrent Abstract Machines for Interaction Nets." url
• 2000: Pedicini and Quaglia, "A parallel implementation for optimal lambda-calculus reduction." url
• 2002: Lippi, "in2: A Graphical Interpreter for Interaction Nets." url
• 2003: Pinto, "Weak Reduction and Garbage Collection in Interaction Nets." url
• 2007: Pedicini and Quaglia, "PELCR: parallel environment for optimal lambda-calculus reduction." url
• 2008: Hassan, Mackie and Sato, "Interaction Nets: Programming language design and implementation." url
• 2009: Hassan, Mackie and Sato, "Compilation of Interaction Nets." url
• 2010: Hassan, Mackie and Sato, "A lightweight abstract machine for interaction nets." url
• 2011: Mackie, "An Interaction Net Implementation of Closed Reduction." url
• 2015: Kahl, "A Simple Parallel Implementation of Interaction Nets in Haskell." url
• 2015: Sato, "Design and Implementation of a Low-Level Language for Interaction Nets." url
• 2015: Hassan, Mackie and Sato, "An Implementation Model for Interaction Nets." url
• 2016: Mackie, "Compiling process networks to interaction nets." url
• 2020: Accattoli, Lago and Vanoni, "The Abstract Machinery of Interaction." url
• 2024: Taelin, "HVM2: A Parallel Evaluator For Interaction Combinators." url
• 2025: Huber and Yi, "An Encoding of Interaction Nets in Ocaml." url

Geometry

• 1989: Girard, "Geometry of Interaction 1." url
• 1992: Gonthier, Abadi and Lévy, "The Geometry of Optimal Lambda Reduction." url
• 1995: Mackie, "The Geometry of Interaction Machine." url
• 2002: Fernández and Mackie, "Call-by-Value λ-Graph Rewriting without Rewriting." url
• 2018: Muroya and Ghica, "The Dynamic Geometry of Interaction Machine." url
• 2016: Solieri, "Sharing, Superposition and Expansion." url

Hard Combinators

• 2008: Béchet and Lippi, "Hard Combinators." url
• 2009: Lippi, "Universal Hard Interaction for Clockless Computation." url

Syntax

• 1990: Lafont, "Interaction Nets." url
• 1999: Fernández and Mackie, "A Calculus for Interaction Nets." url
• 2005: Mackie, "Towards a Programming Language for Interaction Nets." url
• 2010: Hassan, Mackie and Sato, "A lightweight abstract machine for interaction nets." url

Non-Determinism

• 1999: Alexiev, "Non-Deterministic Interaction Nets." url
• 2002: Fernández and Khalil, "Interaction Nets with McCarthy’s Amb." url
• 2006: Mazza, "Interaction Nets: Semantics and Concurrent Extensions." url

IO

• 2001: Maribel, Mackie and Pinto, "Combining Interaction Nets with Externally Defined Programs." url
• 2012: Jiresch, "Extending Interaction Nets towards the Real World." url
• 2024: Taelin, "HVM2: A Parallel Evaluator For Interaction Combinators." url
• 2025: Borner, "Optimal Interaction with the Real World." url

Cellular Automata

• 2016: Gimenez and Obwaller, "Interaction Automata and the ia2d Interpreter." url

Lambda Calculus

Efficiency

• 1996: Lawall and Mairson, "Optimality and Inefficiency." url
• 1997: Asperti and Chroboczek, "Safe Operators." url
• 1998: Mackie, "YALE: Yet Another Lambda Evaluator Based on Interaction Nets." url
• 2003: Coppola and Martini, "Optimizing Optimal Reduction." url
• 2003: Pinto, "Weak Reduction and Garbage Collection in Interaction Nets." url
• 2004: Mackie, "Efficient λ-Evaluation with Interaction Nets." url
• 2006: Sinot, "Stratégies Efficaces et Modèles d'Implantation pour les Langages Fonctionnels." url
• 2007: Pedicini and Quaglia, "PELCR: parallel environment for optimal lambda-calculus reduction." url
• 2011: Mackie, "An Interaction Net Implementation of Closed Reduction." url
• 2013: Fernández, Mackie and Walker, "Bigraphical Nets." url
• 2017: Asperti, "About the Efficient Reduction of Lambda Terms." url
• 2020: Muroya, "Hypernet semantics of programming languages." url

Optimality

• 1980: Lévy, "Optimal Reductions in the Lambda Calculus." url
• 1990: Lamping, "An Algorithm for Optimal Lambda Calculus Reduction." url
• 1990: Kathail, "Optimal interpreters for lambda-calculus based functional languages." url
• 1992: Gonthier, Abadi and Lévy, "The Geometry of Optimal Lambda Reduction." url
• 1996: Lawall and Mairson, "Optimality and Inefficiency." url
• 1996: Asperti, Giovannetti and Naletto, "The Bologna Optimal Higher-Order Machine." url
• 1996: Danos and Regnier, "Reversible, Irreversible and Optimal λ-Machines." url
• 1998: Asperti and Guerrini, "The Optimal Implementation of Functional Programming Languages." url
• 1999: Thyer, "Lazy Specialization." url
• 2000: Asperti, Coppola and Martini, "(Optimal) Duplication Is Not Elementary Recursive." url
• 2004: van Oostrom, van de Looij and Zwitserlood, "Lambdascope: Another Optimal Implementation of the Lambda-Calculus." url
• 2005: Guerrini, "Sharing Implementations of Graph Rewriting Systems." url
• 2007: Zwitserlood, "End-of-Scope, Locally." url
• 2007: Pedicini and Quaglia, "PELCR: parallel environment for optimal lambda-calculus reduction." url
• 2010: Fernández and Siafakas, "Labelled Lambda-calculi with Explicit Copy and Erase." url
• 2012: Guerrini, Leventis and Solieri, "Deep into Optimality." url
• 2013: Balabonski, "Weak Optimality, and the Meaning of Sharing." url
• 2014: Pedicini, Pellitta and Piazza, "Sequential and Parallel Abstract Machines for Optimal Reduction." url
• 2017: Lai, Pedicini and Piazza, "Abstract Machines, Optimal Reduction, and Streams." url
• 2017: Barenbaum and Bonelli, "Optimality and the Linear Substitution Calculus." url
• 2025: Salvadori, "Δ-Nets." url

Non-Optimality

• 1998: Mackie, "YALE: Yet Another Lambda Evaluator Based on Interaction Nets." url
• 2001: Lippi, "Encoding left reduction in the λ-calculus with interaction nets." url
• 2003: Pinto, "Weak Reduction and Garbage Collection in Interaction Nets." url
• 2005: Ariola and Blom, "Cyclic Lambda Calculi." url
• 2007: Lippi, "The Graphical Krivine Machine." url
• 2011: Mackie, "An Interaction Net Implementation of Closed Reduction." url

Tokens

• 1995: Mackie, "The Geometry of Interaction Machine." url
• 2005: Sinot, "Call-by-Name and Call-by-Value as Token-Passing Interaction Nets." url
• 2006: Sinot, "Token-Passing Nets: Call-by-Need for Free." url
• 2008: Almeida, Pinto and Vilaça, "Token-Passing Nets for Functional Languages." url
• 2016: Salikhmetov, "Token-Passing Optimal Reduction with Embedded Read-Back." url
• 2017: Lago, Tanaka and Yoshimizu, "The Geometry of Concurrent Interaction: Handling Multiple Ports by Way of Multiple Tokens." url
• 2018: Muroya and Chica, "Efficient Implementation of Evaluation Strategies via Token-Guided Graph Rewriting." url

Reduction Strategies

• 2005: Mackie, "Encoding Strategies in the Lambda Calculus with Interaction Nets." url
• 2005: Sinot, "Call-by-Name and Call-by-Value as Token-Passing Interaction Nets." url
• 2006: Sinot, "Token-Passing Nets: Call-by-Need for Free." url
• 2018: Muroya and Chica, "Efficient Implementation of Evaluation Strategies via Token-Guided Graph Rewriting." url

Theory

• 1997: Asperti, "P = NP, up to Sharing." url
• 1998: Asperti and Mairson, "Parallel Beta Reduction Is Not Elementary Recursive." url
• 2002: Mairson, "From Hilbert Spaces to Dilbert Spaces." url
• 2003: Beckmann, "Exact Bounds For Lengths of Reductions in Typed λ-Calculus." url
• 2004: Baillot and Terui, "A Feasible Algorithm for Typing in Elementary Affine Logic." url
• 2005: Ariola and Blom, "Cyclic Lambda Calculi." url
• 2007: Terui, "Light Affine Lambda Calculus and Polynomial Time Strong Normalization." url
• 2013: David, Grygiel, Kozic, Raffalli, Theyssier and Zaionc, "Asymptotically Almost All λ-Terms Are Strongly Normalizing." url
• 2014: Accattoli and Dal Lago, "Beta Reduction Is Invariant, Indeed." url
• 2022: Lago, "Implicit Computation Complexity in Higher-Order Programming Languages." url

Functional Programming

• 2007: Cirstea, Faure, Fernández, Mackie and Sinot, "From functional programs to interaction nets via the Rewriting Calculus." url
• 2008: Almeida, Pinto and Vilaça, "Token-Passing Nets for Functional Languages." url
• 2009: Mackie, Pinto and Vilaça, "Iterators, Recursors and Interaction Nets." url
• 2009: Fernández, Mackie, Sato and Walker, "Recursive Functions with Pattern Matching in Interaction Nets." url
• 2010: Hassan, Jiresch and Sato, "An Implementation of Nested Pattern Matching in Interaction Nets." url
• 2014: Mackie, Pinto and Vilaça, "Functional Programming and Program Transformation with Interaction Nets." url

Linear Logic & Sequent Calculus

• 2000: Asperti, Coppola and Martini, "(Optimal) Duplication Is Not Elementary Recursive." url
• 2000: Mackie, "Interaction Nets for Linear Logic." url
• 2001: Mackie, "Implantation parallele avec la logique lineaire (application des reseaux d'interaction et de la geometrie d'interaction)" url
• 2002: Mackie and Pinto, "Encoding Linear Logic with Interaction Combinators." url
• 2009: Gimenez, "Programmer, calculer et raisonner avec les réseaux de la logique linéaire." url
• 2013: Gimenez and Moser, "The Structure of Interaction." url
• 2019: Aschieri and Genco, "Par Means Parallel." url

Term Rewriting System

• 1998: Fernández and Mackie, "Interaction Nets and Term-Rewriting Systems." url