On One-Pass CPS Transformations

Olivier Danvy
Lasse R. Nielsen

January 2002


We bridge two distinct approaches to one-pass CPS transformations, i.e., CPS transformations that reduce administrative redexes at transformation time instead of in a post-processing phase. One approach is compositional and higher-order, and is due to Appel, Danvy and Filinski, and Wand, building on Plotkin's seminal work. The other is non-compositional and based on a syntactic theory of the $\lambda$-calculus, and is due to Sabry and Felleisen. To relate the two approaches, we use Church encoding, Reynolds's defunctionalization, and an implementation technique for syntactic theories, refocusing, developed in the second author's PhD thesis.

This work is directly applicable to transforming programs into monadic normal form.

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.