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 

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 Scheme-base example is given in Section 13.9.

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, catch-expr with an id. id is a symbol. Within the expression, or within a function called directly or indirectly in catch-expr, we may encounter a throw form, which mention the id of the catch. The value of the thrown expression, throw-expr, 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 catch-expr.

(catch id catch-expr)

(throw id throw-expression)

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 non-local exists [cltl-non-local-exists].

13.3.  A catch and throw example
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

We now study an concrete, real-life example of catch and throw. This is not a Scheme example.

The function list-length 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 improper-list. In order to provide for this we set of a catcher around the a local function, list-length1, which does the real job. The function list-length calls list-length1. If list-length1 encounters an improper termination of the list, it throws the symbol improper-list 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 (list-length lst)
  (catch 'exit
    (letrec ((list-length1
               (lambda (lst) 
                 (cond ((null? lst) 0)
                   ((pair? lst) (+ 1 (list-length1 (cdr lst))))
                   (else (throw 'exit 'improper-list))))))
       (list-length1 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.

(+ 5 (* 4 3))

(cons 1 (cons 2 (cons 3 '())))

(define x 5)
(if (= 0 x)
    'undefined
    (remainder (* (+ x 1) (- x 1)) x))

13.5.  Being more precise
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

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.

(+ 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))

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 

We will use the brief form call/cc in our examples.

(+ 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))

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 cont-remember. We assume that cont-remember 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.

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 cont-remember, and the value of the application. We explain the rightmost column below the table.

(+ 5 
 (call/cc 
  (lambda (e) 
   (set! cont-remember e)
   (* 4 3))))

17

(cont-remember 3)

8

(cons 1 
 (cons 2 
  (cons 3 
   (call/cc 
    (lambda (e) 
     (set! cont-remember e)
     '())))))

(1 2 3)

(cont-remember '(7 8))

(1 2 3 7 8)

(define x 5)
(if (= 0 x)
    'undefined
    (remainder 
     (* (call/cc 
         (lambda (e) 
          (set! cont-remember e)
          (+ x 1) ))
        (- x 1))
     x))

4

(cont-remember 3)

2

First we explain the first row in the table. The application (cont-remember 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, (cont-remember '(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 (cont-remember 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.

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.

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

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 improper-list.

It is easy to program the escaping version of list-length with continuations, see Program 13.2. At the outer level we capture the continuation that immediately returns from list-length. We can freely name the continuation, and we chose the name do-exit. Within the scope of the continuation we define a local helping function list-length1, which does the real counting job. We follow the cdr chain in the recursion of list-length1. 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 improper-list to do-exit. 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 (list-length l)
  (call-with-current-continuation
   (lambda (do-exit)
     (letrec ((list-length1
                (lambda (l)
                   (cond ((null? l) 0)
                         ((pair? l) (+ 1 (list-length1 (cdr l))))
                         (else (do-exit 'improper-list))))))
       (list-length1 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.

The function find-in-tree 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 find-in-tree. 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 find-in-tree1 is a recursive pre-order 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 (subtree-list ...) 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 (find-in-tree tree pred)
 (call-with-current-continuation
  (lambda (found)
   (letrec
    ((find-in-tree1
       (lambda (tree pred)
            (if (pred tree)
                (found tree)
                (let ((subtrees (subtree-list tree)))
                   (for-each
                      (lambda (subtree) (find-in-tree1 subtree pred))
                      subtrees)))
            #f)))
    (find-in-tree1 tree pred)))  ))