Ronald Garcia ; Andrew Lumsdaine ; Amr Sabry - Lazy Evaluation and Delimited Control

lmcs:1013 - Logical Methods in Computer Science, July 11, 2010, Volume 6, Issue 3 -
Lazy Evaluation and Delimited Control

Authors: Ronald Garcia ; Andrew Lumsdaine ; Amr Sabry

    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.

    Volume: Volume 6, Issue 3
    Published on: July 11, 2010
    Accepted on: June 25, 2015
    Submitted on: October 12, 2009
    Keywords: Computer Science - Programming Languages,D.3.1
    Fundings :
      Source : OpenAIRE Research Graph
    • Collaborative Research: Modular Metaprogramming; Funder: National Science Foundation; Code: 0702717
    • Collaborative Research: CSR/EHS: Building Physically Safe Embedded Systems; Funder: National Science Foundation; Code: 0720857
    • Computing Innovation Fellows Project; Funder: National Science Foundation; Code: 0937060

    Linked data

    Source : ScholeXplorer IsReferencedBy DOI 10.1007/978-3-030-17184-1_15
    • 10.1007/978-3-030-17184-1_15
    • 10.1007/978-3-030-17184-1_15
    • 10.1007/978-3-030-17184-1_15
    Types by Need
    Accattoli, Beniamino ; Guerrieri, Giulio ; Leberle, Maico ;

    3 Documents citing this article


    Consultation statistics

    This page has been seen 727 times.
    This article's PDF has been downloaded 439 times.