A Functional Correspondence between Call-by-Need Evaluators and Lazy Abstract Machines

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Department of Computer Science
We bridge the gap between compositional evaluators and abstract machines for the lambda-calculus, using closure conversion, transformation into continuation-passing style, and defunctionalization of continuations. This article is a followup of our article at PPDP 2003, where we consider call by name and call by value. Here, however, we consider call by need.

We derive a lazy abstract machine from an ordinary call-by-need evaluator that threads a heap of updatable cells. In this resulting abstract machine, the continuation fragment for updating a heap cell naturally appears as an ‘update marker’, an implementation technique that was invented for the Three Instruction Machine and subsequently used to construct lazy variants of Krivine's abstract machine. Tuning the evaluator leads to other implementation techniques such as unboxed values. The correctness of the resulting abstract machines is a corollary of the correctness of the original evaluators and of the program transformations used in the derivation.
Original languageEnglish
JournalInformation Processing Letters
Volume90
Issue5
Pages (from-to)223-232
Number of pages10
ISSN0020-0190
DOIs
Publication statusPublished - 2004

    Research areas

  • Functional programming, Program derivation, Interpreters, Abstract machines, Closure conversion, CPS transformation, Defunctionalization

See relations at Aarhus University Citationformats

ID: 279897