The essence of compiling with continuations

TLDR

Compilers for higher‑order languages often use a first‑phase continuation‑passing style transformation to produce an intermediate representation where every procedure receives a continuation argument, but the naive CPS form inflates program size, so a second‑phase reduction compacts the representation and the code generator further optimizes continuation handling. Analysis of the CPS abstract machine shows that the code generator’s actions reverse the naive CPS translation, making the combined three phases equivalent to a source‑to‑source transformation that allows fully developed CPS compilers to omit the CPS step entirely.

Abstract

In order to simplify the compilation process, many compilers for higher-order languages use the continuation-passing style (CPS) transformation in a first phase to generate an intermediate representation of the source program. The salient aspect of this intermediate form is that all procedures take an argument that represents the rest of the computation (the “continuation”). Since the nai¨ve CPS transformation considerably increases the size of programs, CPS compilers perform reductions to produce a more compact intermediate representation. Although often implemented as a part of the CPS transformation, this step is conceptually a second phase. Finally, code generators for typical CPS compilers treat continuations specially in order to optimize the interpretation of continuation parameters. A thorough analysis of the abstract machine for CPS terms show that the actions of the code generator invert the nai¨ve CPS translation step. Put differently, the combined effect of the three phases is equivalent to a source-to-source transformation that simulates the compaction phase. Thus, fully developed CPS compilers do not need to employ the CPS transformation but can achieve the same results with a simple source-level transformation.