Programming Praxis

Continuation passing style is a programming style in which the continuation of a function — what happens when the function returns — is made explicit. Wikipedia has a good explanation of continuation passing style. For example, the normal factorial function looks like this:

(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))

When it is written in continuation passing style, all of the continuations (lambdas) are made explicit:

(define (factorial& n k)
  ((cps =) n 0 (lambda (b)
                 (if b 
                     (k 1)
                     ((cps -) n 1 (lambda (n-1)
                                    (factorial& n-1 (lambda (f)
                                                      ((cps *) n f k)))))))))

Here k is the continuation of the factorialfunction. The =, - and * operators must be written in continuation passing style; function cps, which we will see momentarily, converts an operator from normal style to continuation passing style. The three lambdas, with arguments b, n-1 and f, are intermediate steps in the expansion of the tree representation of the code. You can call the continuation-passing style version of the factorial function like this, where the continuation is the identity function:

> (factorial& 5 (lambda (x) x))
120

Of course, the factorial functions shown above are non-tail recursive, meaning that the stack grows with each recursive call. Here is a tail-recursive version of the factorial function:

(define (factorial n)
  (fact n 1))

(define (fact n a)
  (if (= n 0)
      a
      (fact (- n 1) (* n a))))

Parameter a of the auxiliary function is an accumulator, initialized to 1 when the auxiliary function is called. Here is the continuation passing style version of the tail-recursive function:

(define (factorial& n k)
  (fact& n 1 k))

(define (fact& n a k)
  ((cps =) n 0 (lambda (b)
                 (if b
                     (k a)
                     ((cps -) n 1 (lambda (n-1) 
                                    ((cps *) n a (lambda (n*a)
                                                   (fact& n-1 n*a k)))))))))

> (factorial& 5 (lambda (x) x))
120

Now fact& is in tail position and the function consumes bounded stack space, which is what we want. The only thing left is to specify that mysterious cps function:

(define (cps f)
  (lambda args
    (let ((f-args (but-last args)) (k (last args)))
      (k (apply f f-args)))))

The cps function takes a function f and returns a new function that takes args, which includes the arguments to f plus the continuation, and calls the continuation k on the result of applying f to its non-continuation arguments.

Writing in continuation passing style obviously isn’t the most transparent thing in the world, and it’s not something most people do. But compilers work beautifully with continuation passing style, because everything, even the control flow, is explicit. Many functional languages are compiled by transforming the program to continuation passing style, and there is even a book, by Andrew Appel, about using continuations to compile programs.

There’s more to continuation passing style than we have discussed here. A huge advantage of continuation passing style is that, since the continuation is explicit, you can give a function more than one continuation, say k-pass and k-fail, and have the program choose which one to execute. Explicit continuations also make it easy to perform tail-call elimination in those cases where it is possible and to handle multiple-value returns. And compilers are able to aggressively optimize programs written in continuation passing style because everything the compiler needs to know about a function is available in the continuation.

Your task is to experiment with continuation passing style and to write at least one function, anything you like, in continuation passing style. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2