next up previous contents index
Next: The engine transformation Up: The transformer Previous: The transformer

Continuation passing style

One may partition the events in a computation into two sets: those that have already happened, and those that have yet to happen.

Continuation passing style is a style of writing programs where the events in the future, i.e. the rest of the computation, is passed as an explicit parameter. The value passed as this parameter is the continuation. A continuation is a procedure that takes the value of the current expression and computes the rest of the computation. Procedures do not return values; instead, they invoke the continuation with the result. If a program is fully CPS converted then there are no subproblem procedure calls. Every procedure call is tail call, and the program's `control memory' is not stored in some invisible stack but explicity as the continuation.

A program can be converted to CPS relatively easily. This transformation is well understood as it is the basis for several optimizing compilers [2].

Consider the Fibonacci function, fib.

(define (fib n)
  (if (< n 2)
      1
      (+ (fib (- n 1))
         (fib (- n 2)))))

We CPS convert fib, adding k as the additional continuation parameter. We do not CPS convert the primitive procedure calls to <, + and -:

(define (fib k n)
  (if (< n 2)
      (k 1)
      (fib (lambda (fib-of-n-1)
             (fib (lambda (fib-of-n-2)
                    (k (+ fib-of-n-1 fib-of-n-2)))
                  (- n 2)))
           (- n 1))))


Erik Rauch
Sat May 8 16:42:57 EDT 1999