(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.