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