文章基本信息

标题：A Functional Correspondence between Call-by-Need Evaluators and Lazy Abstract Machines
本地全文：下载
作者：Mads Sig Ager ; Olivier Danvy ; Jan Midtgaard 等
期刊名称：BRICS Report Series
印刷版ISSN：0909-0878
出版年度：2004
卷号：11
期号：3
出版社：Aarhus University
摘要：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.