|
A Functional Correspondence between Call-by-Need Evaluators and Lazy
Abstract Machines
Mads Sig Ager
June 2003 |
Abstract:
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 spin-off 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 and the push-enter model. 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.
This report is superseded by the later report BRICS RS-04-3. |