\Lambda

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. 1. Introduction One of the trends in compiler construction has been the use of * terms written in continuation-passing style (CPS) as an intermediate representation [1, 19, 25]. Transformations into CPS for call-by-name and call-byvalue languages are well known [8, 23, 24], but we are unaware of a similar transformation for languages implemented with a call-by-need evaluation strategy (also known as "lazy evaluation"). We find it natural to consider such a transformation. After all, one of the motivations for the use of CP