Lazy evaluation and delimited control

DOI10.1145/1480881.1480903MaRDI QIDQ5261514zbMATH OpenOpenAlexFDO

Authors Ronald Garcia, Andrew Lumsdaine, Amr Sabry

Publication date 3 July 2015

Published in Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1003.5197

zbMATH Keywords

lambda calculusabstract machinescall-by-needreduction semanticsdelimited continuations

Mathematics Subject Classification ID

Functional programming and lambda calculus (68N18)

Abstract: The call-by-need lambda calculus provides an equational framework for reasoning syntactically about lazy evaluation. This paper examines its operational characteristics. By a series of reasoning steps, we systematically unpack the standard-order reduction relation of the calculus and discover a novel abstract machine definition which, like the calculus, goes "under lambdas." We prove that machine evaluation is equivalent to standard-order evaluation. Unlike traditional abstract machines, delimited control plays a significant role in the machine's behavior. In particular, the machine replaces the manipulation of a heap using store-based effects with disciplined management of the evaluation stack using control-based effects. In short, state is replaced with control. To further articulate this observation, we present a simulation of call-by-need in a call-by-value language using delimited control operations.

Recommendations

• Lazy evaluation and delimited control
• A functional correspondence between call-by-need evaluators and lazy abstract machines
• The call-by-need lambda calculus
• An operational semantics of sharing in lazy evaluation
• The Call-by-Need Lambda Calculus, Revisited

Cited in

(12)

• Defunctionalized interpreters for call-by-need evaluation
• Three Syntactic Theories for Combinatory Graph Reduction
• Deriving an abstract machine for strong call by need
• scientific article; zbMATH DE number 549962 (Why is no real title available?)
• Lazy evaluation and delimited control
• Obtaining lazy evaluation with continuations in SCHEME
• Preliminary arrangements of arguments in lazy evaluation
• Classical call-by-need and duality
• scientific article; zbMATH DE number 7204429 (Why is no real title available?)
• A calculus of expandable stores. Continuation-and-environment-passing style translations
• Logic Programming
• Inter-deriving semantic artifacts for object-oriented programming

This page was built for publication: Lazy evaluation and delimited control

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5261514)