On One-Pass CPS Transformations

Forfattere

  • Olivier Danvy
  • Kevin Millikin
  • Lasse R. Nielsen

DOI:

https://doi.org/10.7146/brics.v14i6.21929

Resumé

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 independently due to Appel, Danvy and Filinski, and Wand, building on Plotkin's seminal work. The other is non-compositional and based on a reduction semantics for the lambda-calculus, and is due to Sabry and Felleisen. To relate the two approaches, we use three tools: Reynolds's defunctionalization and its left inverse, refunctionalization; a special case of fold-unfold fusion due to Ohori and Sasano, fixed-point promotion; and an implementation technique for reduction semantics due to Danvy and Nielsen, refocusing.

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

Downloads

Publiceret

2007-03-12

Citation/Eksport

Danvy, O., Millikin, K., & Nielsen, L. R. (2007). On One-Pass CPS Transformations. BRICS Report Series, 14(6). https://doi.org/10.7146/brics.v14i6.21929