Name binding, Recursion, Iteration, and Continuations 
Continuations represent one of the advanced concepts in Scheme. In this section we will introduce continuations, and we will show some examples of their use within the functional programming paradigm.
13.1. Introduction and motivation
Contents Up Previous Next Slide Subject index Program index Exercise index
It is sometimes necessary to escape from a deep expression, for instance in an exceptional case We are interested in a primitive which allows us to control the remaining part of a calculation  a socalled continuation. 

Scheme support first class continuations dressed as functions 
Both needs mentioned above are handled by first class continuations in Scheme.
13.2. The catch and throw idea
Contents Up Previous Next Slide Subject index Program index Exercise index
In this section, and section Section 13.3 we explore a catch and throw escape mechanism. This mechanism is used in Common Lisp, but it is not directly available in Scheme. As we will see in Section 13.8 first class continuations can easily play the role of catch and throw. A similar Schemebase example is given in Section 13.9.
Catch and throw provides for an intuitively simple escape mechanism on functional ground 
We introduce an imaginary syntax of catch and throw, see Syntax 13.1 and Syntax 13.2. The meaning is intended to be that catch identifies an expression, catchexpr with an id. id is a symbol. Within the expression, or within a function called directly or indirectly in catchexpr, we may encounter a throw form, which mention the id of the catch. The value of the thrown expression, throwexpr, is passed back along the chain of calls to the catcher, and it becomes the return value of the catch form. If no throw form with an appropriate id is met during the evaluation of the catch form, the value of the catch form just becomes the value of catchexpr.
 

 

Scheme does not support catch and throw Rather Scheme supports a much more powerful mechanisms based on continuations 
In case you are interested in more precise details of catch and throw in Common Lisp, you should consult the book about Common Lisp, [cltl], (full text on the web). More specifically you should consult the chapter about dynamic nonlocal exists [cltlnonlocalexists].
13.3. A catch and throw example
Contents Up Previous Next Slide Subject index Program index Exercise index
We now study an concrete, reallife example of catch and throw. This is not a Scheme example.
Exit from a list length function in case it discovers a nonempty tail of the list 
The function listlength returns the length of the list. The function counts the cons cells. If we encounter an improper list (a list without an empty list in the end of the cdr chain, see Section 6.2) we wish to return the symbol improperlist. In order to provide for this we set of a catcher around the a local function, listlength1, which does the real job. The function listlength calls listlength1. If listlength1 encounters an improper termination of the list, it throws the symbol improperlist to the catcher, which returns it. If not, it just returns the count, which also is returned by catch via the letrec form.
1 2 3 4 5 6 7 8  (define (listlength lst) (catch 'exit (letrec ((listlength1 (lambda (lst) (cond ((null? lst) 0) ((pair? lst) (+ 1 (listlength1 (cdr lst)))) (else (throw 'exit 'improperlist)))))) (listlength1 lst))))  

13.4. The intuition behind continuations
Contents Up Previous Next Slide Subject index Program index Exercise index
The rest of this chapter is about concepts that are fully supported in Scheme.
We start with an overall definition of a continuations. Then follows some intuitive examples of continuations of given expressions within given contexts (surrounding expressions).

It may very well be difficult to grasp the intuition of continuations. We hope the following table will help you. It is intended to explain the intuitive understanding of the continuations of the blue, emphasized expressions in the leftmost column.
Context C and expression E  Intuitive continuation of E in C 
(+ 5 (* 4 3))  The adding of 5 to the value of E 
(cons 1 (cons 2 (cons 3 '())))  The consing of 3, 2 and 1 to the value of E 
(define x 5) (if (= 0 x) 'undefined (remainder (* (+ x 1) ( x 1)) x))  The multiplication of E by x  1 followed by a division by x 
Table 13.1 An intuitive understanding of continuations of an expression in some context. 
13.5. Being more precise
Contents Up Previous Next Slide Subject index Program index Exercise index
We can form a lambda expression that to some degree represents a continuation 
The continuation of the expression (* 3 4) within (+ 5 (* 3 4)) is a function that adds 5. Written precisely, it is the function (lambda (e) (+ 5 e)). The other two examples of Table 13.2 (corresponding to the second and third rows) are similar.
Context C and expression E  The continuation of E in C 
(+ 5 (* 4 3))  (lambda (e) (+ 5 e)) 
(cons 1 (cons 2 (cons 3 '())))  (lambda (e) (cons 1 (cons 2 (cons 3 e)))) 
(define x 5) (if (= 0 x) 'undefined (remainder (* (+ x 1) ( x 1)) x))  (lambda (e) (remainder (* e ( x 1)) x)) 
Table 13.2 A more precise notation of the continuations of E 
The representation of continuations with lambda expressions is part of the truth, but not the whole truth. The problem is that if we activate the continuation, by calling the function that represents it, it will return the normal way, and its calling context will finish the evaluation the normal way. We do not want that. Therefore a mechanism known as escape functions are invented and used. An escape function ignores its context in every call. We will not go into the technical details of escape functions in this text. The interested reader should consult [Springer89].
13.6. The capturing of continuations
Contents Up Previous Next Slide Subject index Program index Exercise index
Scheme provides a primitive that captures a continuation of an expression E in a context C The primitive is called callwithcurrentcontinuation, or call/cc as a short alias call/cc takes a parameter, which is a function of one parameter. The parameter of the function is bound to the continuation, and the body of the function is E 
We will use the brief form call/cc in our examples.
Context C and the capturing 
(+ 5 (call/cc (lambda (e) (* 4 3)) )) 
(cons 1 (cons 2 (cons 3 (call/cc (lambda (e) '()) )))) 
(define x 5) (if (= 0 x) 'undefined (remainder (* (call/cc (lambda (e) (+ x 1)) ) ( x 1)) x)) 
Table 13.3 Use of call/cc and capturing of continuations. 
We elaborate the examples from Table 13.1 and Table 13.2. In the first line of Table 13.3 we capture the continuation of (* 4 3) in (+ 5 (* 4 3)). In the second line we capture the continuation of '() in (cons 1 (cons 2 (cons 3 '()))). And in the third line we capture the continuation of (+ x 1) in the if expression. This is the same as the continuation of the (+ x 1) in the remainder expression.
One thing is capturing continuations. Another is to make good use of them. Table 13.3 does not illustrate the latter aspect at all. This is seen by the fact the the continuations, bound to the names e in all three examples, are not used.
It should be noticed that a captured continuation is dressed like a function. Somehow we can think of a continuation as a 'wolf in sheep's clothing'. A continuation is activated in the same way as a function is called. However, the continuation is defined (captured) differently than the way functions are defined. Notice also that continuations inherit their first class status from functions, see Section 8.6.
13.7. Capturing, storing, and applying continuations
Contents Up Previous Next Slide Subject index Program index Exercise index
In this section we will illustrate applications of the captured continuations. Once captured, we assign the continuations to a global variable contremember. We assume that contremember has been defined before any of the expressions in table Table 13.4 are evaluated. Use of assignments is of course not functional programming, but it provides an easy way to illustrate the working and the nature the captured continuations. Later in this section we will show uses of continuations in functional programming. For a brief review of imperative programming in Scheme the reader is referred to Chapter 30.
We here show capturing, imperative assignment, and a subsequent application of a continuation 
In table Chapter 30 below we show the context expression C, its value, the application of the captured continuation that we have stored in the variable contremember, and the value of the application. We explain the rightmost column below the table.
Context C and expression E  Value of C  Application of continuation  Value 
(+ 5 (call/cc (lambda (e) (set! contremember e) (* 4 3))))  17  (contremember 3)  8 
(cons 1 (cons 2 (cons 3 (call/cc (lambda (e) (set! contremember e) '())))))  (1 2 3)  (contremember '(7 8))  (1 2 3 7 8) 
(define x 5) (if (= 0 x) 'undefined (remainder (* (call/cc (lambda (e) (set! contremember e) (+ x 1) )) ( x 1)) x))  4  (contremember 3)  2 
Table 13.4 Capturing and applying continuations. The captured continuations are stored in a global variable. The application of the continuation is shown in the third column, and the result of the application of the continuation is shown in the fourth column. 
First we explain the first row in the table. The application (contremember 3) passes 3 to the continuation e. It means that we fuel the expression (+ 5 X) with an X which is 3. The result is 8.
In the second row, (contremember '(7 8)) passes the list (7 8) into the innermost point Y of (cons 1 (cons 2 (cons 3 Y))). The result is the list (1 2 3 7 8).
In the last row, we activate (contremember 3). It implies that 3 is passed into the Z of (remainder (* Z ( x 1)) x), where x is 5. The value is (remainder 12 5) = 2. Notice in particular that the if has made the choice of the 'else part'. If is not a function, but a special form with special evaluation rules. Once it the choice of the if is made, there is no trace left of it in the continuation. For more details of the evaluation of if special forms see Chapter 19 to Chapter 21, and in particular Section 20.10.
13.8. Use of continuations for escaping purposes
Contents Up Previous Next Slide Subject index Program index Exercise index
In this section we will illustrate how to apply the captured continuations for escaping purposes.
We here illustrate applications of the continuations for escaping purposes 
In Table 13.5 we basically show the same expressions as in Table 13.1, Table 13.2, Table 13.3, and Table 13.4. In the light blue fragments, of the form (e X) we send a value X to the continuation, which is bound to e. In the first row we send 5 to the addition, and the value of the context becomes 15. In the second row we send the symbol x to the continuation, whereby the value of the context is the pair (1 . x). (Notice that the second example captures a continuation at a more outer level than in the other tables). In the second row we send the integer 111 to the else part of the if form, and hereby the value of the context becomes 111.
Context C, capturing, and escape call  Value 
(+ 5 (call/cc (lambda (e) (* 4 (e 10)))) )  15 
(cons 1 (call/cc (lambda (e) (cons 2 (cons 3 (e 'x))))) )  (1 . x) 
(define x 5) (if (= 0 x) 'undefined (call/cc (lambda (e) (remainder (* (+ x 1) ( x (e 111))) x))) )  111 
Table 13.5 Capturing and use of a continuation for escaping purposes 
13.9. Practical example: Length of an improper list
Contents Up Previous Next Slide Subject index Program index Exercise index
Now that we have seen how to capture and use continuations for escaping purposes we will study a number of real examples. The first is similar to the catch throw example in Program 13.1. Like the examples in Section 13.8 we also deal with escape values in this example.
Recall from Program 13.1 that we are about to program a list length function. If we, during the element counting, realize that we deal with an improper list (a list not terminated by the empty list) we want some special result, namely the symbol improperlist.
The length of an improper list is undefined We chose to return the symbol improperlist if listlength encounters an improper list This example is similar to the catch and throw example shown earlier in this section 
It is easy to program the escaping version of listlength with continuations, see Program 13.2. At the outer level we capture the continuation that immediately returns from listlength. We can freely name the continuation, and we chose the name doexit. Within the scope of the continuation we define a local helping function listlength1, which does the real counting job. We follow the cdr chain in the recursion of listlength1. If we encounter a data object which is not a cons pair or the empty list we have identified an improper list. In this situation we send the symbol improperlist to doexit. The effect is that we immediately return this symbol, and the count of of cons pairs is not used.
1 2 3 4 5 6 7 8 9  (define (listlength l) (callwithcurrentcontinuation (lambda (doexit) (letrec ((listlength1 (lambda (l) (cond ((null? l) 0) ((pair? l) (+ 1 (listlength1 (cdr l)))) (else (doexit 'improperlist)))))) (listlength1 l))) ))  

13.10. Practical example: Searching a binary tree
Contents Up Previous Next Slide Subject index Program index Exercise index
The next example is about traversal of a tree, with the purpose of finding a subtree which satisfy a given predicate.
Searching a binary tree involves a recursively defined tree traversal If we find the node we are looking for it is convenient to throw the out of the tree traversal 
The function findintree is shown in Program 13.3. As in the list length example in Program 13.2 we set up a continuation at the outer level of findintree. The continuation is called found. This is not a continuation used for an exceptional value, but for the expected 'normal' value of the function.
The local function findintree1 is a recursive preorder tree traversal function. In case the predicate holds on a subtree, it is passed to the continuation found. If not, the subtrees are searched recursively. The recursion stops when we reach the leaves, on which (subtreelist ...) returns the empty list. In case we finish the traversal without ever finding a subtree that satisfies pred we drop through the if form. In that case we will have to return #f. Notice that this is a rare example of having two expression in sequence in the body of a functional abstraction.
1 2 3 4 5 6 7 8 9 10 11 12 13 14  (define (findintree tree pred) (callwithcurrentcontinuation (lambda (found) (letrec ((findintree1 (lambda (tree pred) (if (pred tree) (found tree) (let ((subtrees (subtreelist tree))) (foreach (lambda (subtree) (findintree1 subtree pred)) subtrees))) #f))) (findintree1 tree pred))) ))  

13.11. References[Springer89] George Springer and Daniel P. Friedman, Scheme and the art of programming. The MIT Press and McGrawHill Book Company, 1989. [Cltl] Common Lisp the Language, 2nd Edition.
http://www.ida.liu.se/imported/cltl/cltl2.html[Cltlnonlocalexists] Dynamic Nonlocal exists (Common Lisp)
http://www.ida.liu.se/imported/cltl/clm/node96.html