Abstract:
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 
-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.
-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.