Muroya, Koko and Ghica, Dan R. - The Dynamic Geometry of Interaction Machine: A Token-Guided Graph Rewriter

lmcs:4340 - Logical Methods in Computer Science, October 30, 2019, Volume 15, Issue 4
The Dynamic Geometry of Interaction Machine: A Token-Guided Graph Rewriter

Authors: Muroya, Koko and Ghica, Dan R.

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.


Source : oai:arXiv.org:1803.00427
Volume: Volume 15, Issue 4
Published on: October 30, 2019
Submitted on: March 2, 2018
Keywords: Computer Science - Logic in Computer Science,Computer Science - Programming Languages


Share