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))))

Sat May 8 16:42:57 EDT 1999