2014 · 77 citations · 37 references
ComputingComputer ScienceFormal MethodsProgramming LanguagesSyntaxRecursion TheoryType SystemsAbstract MachinesAbstract SemanticsKam TheorySubstitutions
It is well-known that many environment-based abstract machines can be seen as strategies in lambda calculi with explicit substitutions (ES). Recently, graphical syntaxes and linear logic led to the linear substitution calculus (LSC), a new approach to ES that is halfway between small-step calculi and traditional calculi with ES. This paper studies the relationship between the LSC and environment-based abstract machines. While traditional calculi with ES simulate abstract machines, the LSC rather distills them: some transitions are simulated while others vanish, as they map to a notion of structural congruence. The distillation process unveils that abstract machines in fact implement weak linear head reduction, a notion of evaluation having a central role in the theory of linear logic. We show that such a pattern applies uniformly in call-by-name, call-by-value, and call-by-need, catching many machines in the literature. We start by distilling the KAM, the CEK, and a sketch of the ZINC, and then provide simplified versions of the SECD, the lazy KAM, and Sestoft's machine. Along the way we also introduce some new machines with global environments. Moreover, we show that distillation preserves the time complexity of the executions, i.e. the LSC is a complexity-preserving abstraction of abstract machines.
37
Call-by-name, call-by-value and the λ-calculus
Gordon Plotkin · Theoretical Computer Science · 1975 · 1.2K citations
The Mechanical Evaluation of Expressions
P. J. Landin · The Computer Journal · 1964 · 932 citations · Full text
Deriving a lazy abstract machine
Peter Sestoft · Journal of Functional Programming · 1997 · 199 citations · Full text
The call-by-need lambda calculus
Zena M. Ariola, Matthias Felleisen · Journal of Functional Programming · 1997 · 173 citations · Full text
A call-by-name lambda-calculus machine
Jean-Louis Krivine · LISP and Symbolic Computation · 2007 · 172 citations · Full text