A functional correspondence between call-by-need evaluators and lazy abstract machines

摘要: We bridge the gap between compositional evaluators and abstract machines for lambda-calculus, using closure conversion, transformation into continuation-passing style, defunctionalization of continuations. This article is a followup our at PPDP 2003, where we consider call by name value. Here, however, need.We derive lazy machine from an ordinary call-by-need evaluator that threads heap updatable cells. In this resulting machine, continuation fragment updating cell naturally appears as 'update marker', implementation technique was invented Three Instruction Machine subsequently used to construct variants Krivine's machine. Tuning leads other techniques such unboxed values. The correctness corollary original program transformations in derivation.