ISSN:
1573-0557
Keywords:
Call-by-need
;
Continuation-passing Style
;
Continuations
;
Lazy Evaluation
;
Functional Programming
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract This paper examines the transformation of call-by-need λ terms into continuation-passing style (CPS). It begins by presenting a simple transformation of call-by-need λ terms into program graphs and a reducer for such graphs. From this, an informal derivation is carried out, resulting in a translation from λ 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 λ 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01019945
Permalink
