Programming Languages: Concepts and Implementation

13.10 CPS Transformation

A program written using recursive control behavior can be mechanically rewritten in CPS (i.e., iterative control behavior), and that mechanical process is called CPS conversion. The main idea in CPS conversion is to transform the program so that implicit continuations are represented as closures manipulated by the program. The informal steps involved in this process are:

1. Add a formal parameter representing the continuation to each lambda expression.

2. Pass an anonymous function representing a continuation in each function call.

3. Use the passed continuation in the body of each function definition to return a value.

The CPS conversion involves a set of rewrite rules from a variety of syntactic constructs (e.g., conditional ...