LISP and Symbolic Computation, 7(1)57-82
Call-by-Need and Continuation-Passing StyleChris Okasaki, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213
Peter Lee, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213
David Tarditi, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213
|
Abstract: This paper examines the transformation of
call-by-need lambda terms into continuation-passing style (CPS). It
begins by presenting a simple transformation of call-by-need lambda
terms into program graphs and a reducer for such graphs. From this, an
informal derivation is carried out, resulting in a translation from
lambda terms into self-reducing program graphs, where the graphs are
represented as CPS terms involving storage operations. Though
informal, the derivation proceeds in simple steps, and the resulting
translation is taken to be our canonical CPS transformation for
call-by-need lambda terms. In order to define the CPS transformation more formally, two alternative presentations are given. The first takes the form of a continuation semantics for the call-by-need language. The second presentation follows Danvy and Hatcliff's two-stage decomposition of the call-by-name CPS transformation, resulting in a similar two-stage CPS transformation for call-by-need. Finally, a number of practical matters are considered, including an improvement to eliminate the so-called administrative redexes, as well as to avoid unnecessary memoization and take advantage of strictness information. These improvements make it feasible to consider potential applications in compilers for call-by-need programming languages. Keywords: call-by-need, continuation-passing style, continuations, lazy evaluation, functional programming |
[local copy]
![[picture of journal cover]](../LISP.JPG)