The Dynamic Geometry of Interaction Machine: A Token-Guided Graph Rewriter

Abstract

In implementing evaluation strategies of the lambda-calculus, both correctness and efficiency of implementation are valid concerns. While the notion of correctness is determined by the evaluation strategy, regarding efficiency there is a larger design space that can be explored, in particular the trade-off between space versus time efficiency. Aiming at a unified framework that would enable the study of this trade-off, we introduce an abstract machine, inspired by Girard's Geometry of Interaction (GoI), a machine combining token passing and graph rewriting. We show soundness and completeness of our abstract machine, called the \emph{Dynamic GoI Machine} (DGoIM), with respect to three evaluations: call-by-need, left-to-right call-by-value, and right-to-left call-by-value. Analysing time cost of its execution classifies the machine as ``efficient'' in Accattoli's taxonomy of abstract machines.

arXiv admin note: text overlap with arXiv:1802.06495

References in corpus (4)

• (Leftmost-Outermost) Beta Reduction is Invariant, Indeed
• Pictures of Processes: Automated Graph Rewriting for Monoidal Categories and Applications to Quantum Computing
• The Geometry of Parallelism. Classical, Probabilistic, and Quantum Effects
• The Complexity of Abstract Machines

Cited by in corpus (2)

• Operational Semantics with Hierarchical Abstract Syntax Graphs
• Transparent Synchronous Dataflow