3.4. Continuation Passing Style

As we discussed in the preceding section, a continuation waits for the value of each expression. In particular, a continuation is associated with each procedure call. When one procedure invokes another via a nontail call, the called procedure receives an implicit continuation that is responsible for completing what is left of the calling procedure's body plus returning to the calling procedure's continuation. If the call is a tail call, the called procedure simply receives the continuation of the calling procedure.

We can make the continuations explicit by encapsulating "what to do" in an explicit procedural argument passed along on each call. For example, the continuation of the call to f in

 (letrec ((f (lambda (x) (cons 'a x)))          (g (lambda (x) (cons 'b (f x))))          (h (lambda (x) (g (cons 'c x)))))   (cons 'd (h '()))) ⇒ (d b a c)

conses the symbol b onto the value returned to it, then returns the result of this cons to the continuation of the call to g. This continuation is the same as the continuation of the call to h, which conses the symbol d onto the value returned to it. We can rewrite this in continuation-passing style, or CPS, by replacing these implicit continuations with explicit procedures.

 (letrec ((f (lambda (x k) (k (cons 'a x))))          (g (lambda (x k)               (f x (lambda (v) (k (cons 'b v))))))          (h (lambda (x k) (g (cons 'c x) k))))   (h '() (lambda (v) (cons 'd v))))

Like the implicit continuation of h and g in the preceding example, the explicit continuation passed to h and on to g,

 (lambda (v) (cons 'd v))

conses the symbol d onto the value passed to it. Similarly, the continuation passed to f,

 (lambda (v) (k (cons 'b v)))

conses b onto the value passed to it, then passes this on to the continuation of g.

Expressions written in CPS are more complicated, of course, but this style of programming has some useful applications. CPS allows a procedure to pass more than one result to its continuation, because the procedure that implements the continuation can take any number of arguments.

 (define car&cdr   (lambda (p k)     (k (car p) (cdr p)))) (car&cdr '(a b c)   (lambda (x y)      (list y x))) ⇒ ((b c) a) (car&cdr '(a b c) cons) ⇒ (a b c) (car&cdr '(a b c a d) memv) ⇒ (a d)

(This can be done with multiple values as well; see Section 5.7.) CPS also allows a procedure to take separate "success" and "failure" continuations, which may accept different numbers of arguments. An example is integer-divide below, which passes the quotient and remainder of its first two arguments to its third, unless the second argument (the divisor) is zero, in which case it passes an error message to its fourth argument.

 (define integer-divide   (lambda (x y success failure)     (if (= y 0)         (failure "divide by zero")         (let ((q (quotient x y)))           (success q (- x (* q y))))))) (integer-divide 10 3 list (lambda (x) x)) ⇒ (3 1) (integer-divide 10 0 list (lambda (x) x)) ⇒ "divide by zero"

The procedure quotient, employed by integer-divide, returns the quotient of its two arguments, truncated toward zero.

Explicit success and failure continuations can sometimes help to avoid the extra communication necessary to separate successful execution of a procedure from unsuccessful execution. Furthermore, it is possible to have multiple success or failure continuations for different avors of success or failure, each possibly taking different numbers and types of arguments. See Sections 9.10 and 9.11 for extended examples that employ continuation-passing style.

At this point you may be wondering about the relationship between CPS and the continuations obtained via call/cc. It turns out that any program that uses call/cc can be rewritten in CPS without call/cc, but a total rewrite of the program (sometimes including even system-defined primitives) may be necessary. Try to convert the product example on page 72 into CPS before looking at the version below.

 (define product   (lambda (ls k)     (let ((break k))       (let f ((ls ls) (k k))         (cond           ((null? ls) (k 1))           ((= (car ls) 0) (break 0))           (else (f (cdr ls)                    (lambda (x)                      (k (* (car ls) x)))))))))) (product '(1 2 3 4 5) (lambda (x) x)) ⇒ 120 (product '(7 3 8 0 1 9 5) (lambda (x) x)) ⇒ 0

Exercise 3.4.1.

Rewrite the reciprocal example first given in Section 2.1 to accept both success and failure continuations, like integer-divide above.

Exercise 3.4.2.

Rewrite the retry example from page 73 to use CPS.

Exercise 3.4.3.

Rewrite the following expression in CPS to avoid using call/cc.

 (define reciprocals   (lambda (ls) (call/cc     (lambda (k)       (map (lambda (x)              (if (= x 0)                  (k "zero found")                  (/ 1 x)))            ls))))) (reciprocals '(2 1/3 5 1/4)) ⇒ (1/2 3 1/5 4) (reciprocals '(2 1/3 0 5 1/4)) ⇒ "zero found"

[Hint: A single-list version of map is defined on page 44.]