2013 · 30 citations · 35 references
ComputingComputer ScienceProgramming LanguagesSyntaxTheory Of ComputationAbstract Syntax TreesFunctional ProgrammingRecursion TheoryType SystemsCall SemanticsFluent CalculusLambda CalculusLanguage SemanticsLazy EvaluationOperational CalculusOperational SemanticsStructural Operational Semantics
We present the first operational account of call by need that connects syntactic theory and implementation practice. Syntactic theory: the storeless operational semantics using syntax rewriting to account for demand-driven computation and for caching intermediate results. Implementational practice: the store-based operational technique using memo-thunks to implement demand-driven computation and to cache intermediate results for subsequent sharing. The implementational practice was initiated by Landin and Wadsworth and is prevalent today to implement lazy programming languages such as Haskell. The syntactic theory was initiated by Ariola, Felleisen, Maraist, Odersky and Wadler and is prevalent today to reason equationally about lazy programs, on par with Barendregt et al.'s term graphs. Nobody knows, however, how the theory of call by need compares to the practice of call by need: all that is known is that the theory of call by need agrees with the theory of call by name, and that the practice of call by need optimizes the practice of call by name.
35
Call-by-name, call-by-value and the λ-calculus
Gordon Plotkin · Theoretical Computer Science · 1975 · 1.2K citations
Definitional interpreters for higher-order programming languages
John Reynolds · 1972 · 668 citations