Continuations

Let us write a function which takes an s-expression and adds up all its terminals:
(define sumtree
  (lambda (x)
    (cond ((null? x) 0)
          ((number? x) x)
	  (else
	   (+ (sumtree (car x))
	      (sumtree (cdr x)))))))
Now, assume we want the function to ``escape'' if it finds a -1 at a terminal, returning the symbol negative in this case. If we have some non-local escape mechanism (like call/cc or catch/throw or setjmp/longjmp or some exception mechanism), then we can just use that:
(define sumtree
  ;; internal definition
  (define sumtree0
    (lambda (x e)
      (cond ((null? x) 0)
            ((eq? x -1) (e 'negative))
	    ((number? x) x)
	    (else
	     (+ (sumtree0 (car x) e)
		(sumtree0 (cdr x) e))))))

  (call/cc (lambda (e)
              (sumtree0 x e))))
But let us assume no such escape mechanism is available. We could handle this as an out-of-band return token:
(define sumtree
  (lambda (x)
    (cond ((null? x) 0)
          ((eq? x -1) (e 'negative))
          ((number? x) x)
	  (else
	   (let ((a (sumtree (car x))))
             (if (eq? a 'negative)
	         'negative
		 (let ((d (sumtree (cdr x))))
		   (if (eq? d 'negative)
		       'negative
		       (+ a d)))))))))
but this slows down the general case, and is not the technique we are interested in here. Instead, we will use continuations to implement a real escape mechanism, even though the language does not provide one.

The basic insight is this: instead of doing things to the values returned by the recursive calls, we will tail-recurse while passing along an extra argument telling the function what it should do with the result it has calculated.

First, we add this without the escape mechanism:

(define sumtree
  ;; internal definition
  (define sumtree0
    (lambda (x c)
      (cond ((null? x) (c 0))
	    ((number? x) (c x))
	    (else
	      (sumtree0 (car x)
	                (lambda (a)
			  (sumtree0 (cdr x)
			            (lambda (d)
				      (+c a d c)))))))))

  (sumtree0 x (lambda (a) a)))

(define +c (lambda (a d c) (c (+ a d))))
Now that we have made this rather tortuous rewrite, an escape clause comes naturally. We carry along not one but two continuations:
(define sumtree
  ;; internal definition
  (define sumtree0
    (lambda (x c e)
      (cond ((null? x) (c 0))
            ((eq? x -1) (e))
	    ((number? x) (c x))
	    (else
	      (sumtree0 (car x)
	                (lambda (a)
			  (sumtree0 (cdr x)
			            (lambda (d)
				      (+c a d c))
				    e))
			e)))))

  (sumtree0 x
           (lambda (a) a)
	   (lambda () 'negative)))

(define +c (lambda (a d c) (c (+ a d))))
This technique is particularly useful in distributed systems, where logical flow of control moves from machine to machine across a network, and where the available language and control structures are usually rather primitive, and where exception handling and other kinds of escapes and unusual control regimes are often critical.


Barak Pearlmutter <bap@cs.unm.edu>