13  Jumps

One of the signal features of Scheme is its support for jumps or nonlocal control. Specifically, Scheme allows program control to jump to arbitrary locations in the program, in contrast to the more restrained forms of program control flow allowed by conditionals and procedure calls. Scheme’s nonlocal control operator is a procedure named call‑with‑current‑continuation. We will see how this operator can be used to create a breathtaking variety of control idioms.

13.1  call‑with‑current‑continuation

The operator call‑with‑current‑continuation calls its argument, which must be a unary procedure, with a value called the “current continuation”. If nothing else, this explains the name of the operator. But it is a long name, and is often abbreviated call/cc.1

The current continuation at any point in the execution of a program is an abstraction of the rest of the program. Thus in the program

(+ 1 (call/cc
       (lambda (k)
         (+ 2 (k 3)))))

the rest of the program, from the point of view of the call/cc-application, is the following program-with-a-hole (with [] representing the hole):

(+ 1 [])

In other words, this continuation is a program that will add 1 to whatever is used to fill its hole.

This is what the argument of call/cc is called with. Remember that the argument of call/cc is the procedure

(lambda (k)
  (+ 2 (k 3)))

This procedure’s body applies the continuation (bound now to the parameter k) to the argument 3. This is when the unusual aspect of the continuation springs to the fore. The continuation call abruptly abandons its own computation and replaces it with the rest of the program saved in k! In other words, the part of the procedure involving the addition of 2 is jettisoned, and k’s argument 3 is sent directly to the program-with-the-hole:

(+ 1 [])

The program now running is simply

(+ 1 3)

which returns 4. In sum,

(+ 1 (call/cc
       (lambda (k)
         (+ 2 (k 3)))))
=> 4

The above illustrates what is called an escaping continuation, one used to exit out of a computation (here: the (+ 2 []) computation). This is a useful property, but Scheme’s continuations can also be used to return to previously abandoned contexts, and indeed to invoke them many times. The “rest of the program” enshrined in a continuation is available whenever and how many ever times we choose to recall it, and this is what contributes to the great and sometimes confusing versatility of call/cc. As a quick example, type the following at the listener:

(define r #f)

(+ 1 (call/cc
       (lambda (k)
         (set! r k)
         (+ 2 (k 3)))))
=> 4

The latter expression returns 4 as before. The difference between this use of call/cc and the previous example is that here we also store the continuation k in a global variable r.

Now we have a permanent record of the continuation in r. If we call it on a number, it will return that number incremented by 1:

(r 5)
=> 6

Note that r will abandon its own continuation, which is better illustrated by embedding the call to r inside some context:

(+ 3 (r 5))
=> 6

The continuations provided by call/cc are thus abortive continuations.

13.2  Escaping continuations

Escaping continuations are the simplest use of call/cc and are very useful for programming procedure or loop exits. Consider a procedure list‑product that takes a list of numbers and multiplies them. A straightforward recursive definition for list‑product is:

(define list-product
  (lambda (s)
    (let recur ((s s))
      (if (null? s) 1
          (* (car s) (recur (cdr s)))))))

There is a problem with this solution. If one of the elements in the list is 0, and if there are many elements after 0 in the list, then the answer is a foregone conclusion. Yet, the code will have us go through many fruitless recursive calls to recur before producing the answer. This is where an escape continuation comes in handy. Using call/cc, we can rewrite the procedure as:

(define list-product
  (lambda (s)
    (call/cc
      (lambda (exit)
        (let recur ((s s))
          (if (null? s) 1
              (if (= (car s) 0) (exit 0)
                  (* (car s) (recur (cdr s))))))))))

If a 0 element is encountered, the continuation exit is called with 0, thereby avoiding further calls to recur.

13.3  Tree matching

A more involved example of continuation usage is the problem of determining if two trees (arbitrarily nested dotted pairs) have the same fringe, i.e., the same elements (or leaves) in the same sequence. E.g.,

(same-fringe? '(1 (2 3)) '((1 2) 3))
=> #t

(same-fringe? '(1 2 3) '(1 (3 2)))
=> #f

The purely functional approach is to flatten both trees and check if the results match.

(define same-fringe?
  (lambda (tree1 tree2)
    (let loop ((ftree1 (flatten tree1))
               (ftree2 (flatten tree2)))
      (cond ((and (null? ftree1) (null? ftree2)) #t)
            ((or (null? ftree1) (null? ftree2)) #f)
            ((eqv? (car ftree1) (car ftree2))
             (loop (cdr ftree1) (cdr ftree2)))
            (else #f)))))

(define flatten
  (lambda (tree)
    (cond ((null? tree) '())
          ((pair? (car tree))
           (append (flatten (car tree))
                   (flatten (cdr tree))))
          (else
           (cons (car tree)
                 (flatten (cdr tree)))))))

However, this traverses the trees completely to flatten them, and then again till it finds non-matching elements. Furthermore, even the best flattening algorithms will require conses equal to the total number of leaves. (Destructively modifying the input trees is not an option.)

We can use call/cc to solve the problem without needless traversal and without any consing. Each tree is mapped to a generator, a procedure with internal state that successively produces the leaves of the tree in the left-to-right order that they occur in the tree.

(define tree->generator
  (lambda (tree)
    (let ((caller '*))
      (letrec
          ((generate-leaves
            (lambda ()
              (let loop ((tree tree))
                (cond ((null? tree) 'skip)
                      ((pair? tree)
                       (loop (car tree))
                       (loop (cdr tree)))
                      (else
                       (call/cc
                        (lambda (rest-of-tree)
                          (set! generate-leaves
                            (lambda ()
                              (rest-of-tree 'resume)))
                          (caller tree))))))
              (caller '()))))
        (lambda ()
          (call/cc
           (lambda (k)
             (set! caller k)
             (generate-leaves))))))))

When a generator created by tree‑>generator is called, it will store the continuation of its call in caller, so that it can know who to send the leaf to when it finds it. It then calls an internal procedure called generate‑leaves which runs a loop traversing the tree from left to right. When the loop encounters a leaf, it will use caller to return the leaf as the generator’s result, but it will remember to store the rest of the loop (captured as a call/cc continuation) in the generate‑leaves variable. The next time the generator is called, the loop is resumed where it left off so it can hunt for the next leaf.

Note that the last thing generate‑leaves does, after the loop is done, is to return the empty list to the caller. Since the empty list is not a valid leaf value, we can use it to tell that the generator has no more leaves to generate.

The procedure same‑fringe? maps each of its tree arguments to a generator, and then calls these two generators alternately. It announces failure as soon as two non-matching leaves are found:

(define same-fringe?
  (lambda (tree1 tree2)
    (let ((gen1 (tree->generator tree1))
          (gen2 (tree->generator tree2)))
      (let loop ()
        (let ((leaf1 (gen1))
              (leaf2 (gen2)))
          (if (eqv? leaf1 leaf2)
              (if (null? leaf1) #t (loop))
              #f))))))

It is easy to see that the trees are traversed at most once, and in case of mismatch, the traversals extend only upto the leftmost mismatch. cons is not used.

13.4  Coroutines

The generators used above are interesting generalizations of the procedure concept. Each time the generator is called, it resumes its computation, and when it has a result for its caller returns it, but only after storing its continuation in an internal variable so the generator can be resumed again. We can generalize generators further, so that they can mutually resume each other, sending results back and forth amongst themselves. Such procedures are called coroutines [18].

We will view a coroutine as a unary procedure, whose body can contain resume calls. resume is a two-argument procedure used by a coroutine to resume another coroutine with a transfer value. The macro coroutine defines such a coroutine procedure, given a variable name for the coroutine’s initial argument, and the body of the coroutine.

(define-macro coroutine
  (lambda (x . body)
    `(letrec ((+local-control-state
               (lambda (,x) ,@body))
              (resume
               (lambda (c v)
                 (call/cc
                  (lambda (k)
                    (set! +local-control-state k)
                    (c v))))))
       (lambda (v)
         (+local-control-state v)))))

A call of this macro creates a coroutine procedure (let’s call it A) that can be called with one argument. A has an internal variable called +local‑control‑state that stores, at any point, the remaining computation of the coroutine. Initially this is the entire coroutine computation. When resume is called — i.e., invoking another coroutine B — the current coroutine will update its +local‑control‑state value to the rest of itself, stop itself, and then jump to the resumed coroutine B. When coroutine A is itself resumed at some later point, its computation will proceed from the continuation stored in its +local‑control‑state.

13.4.1  Tree-matching with coroutines

Tree-matching is further simplified using coroutines. The matching process is coded as a coroutine that depends on two other coroutines to supply the leaves of the respective trees:

(define make-matcher-cor
  (lambda (tree-cor-1 tree-cor-2)
    (coroutine dummy-init-arg
      (let loop ()
        (let ((leaf1 (resume tree-cor-1 'get-a-leaf))
              (leaf2 (resume tree-cor-2 'get-a-leaf)))
          (if (eqv? leaf1 leaf2)
              (if (null? leaf1) #t (loop))
              #f))))))

The leaf-generator coroutines remember who to send their leaves to:

(define make-leaf-gen-cor
  (lambda (tree matcher-cor)
    (coroutine dummy-init-arg
      (let loop ((tree tree))
        (cond ((null? tree) 'skip)
              ((pair? tree)
               (loop (car tree))
               (loop (cdr tree)))
              (else
               (resume matcher-cor tree))))
      (resume matcher-cor '()))))

The same‑fringe? procedure can now almost be written as

(define same-fringe?
  (lambda (tree1 tree2)
    (letrec ((tree-cor-1
              (make-leaf-gen-cor
               tree1
               matcher-cor))
             (tree-cor-2
              (make-leaf-gen-cor
               tree2
               matcher-cor))
             (matcher-cor
              (make-matcher-cor
               tree-cor-1
               tree-cor-2)))
      (matcher-cor 'start-the-ball-rolling))))

Unfortunately, Scheme’s letrec can resolve mutually recursive references amongst the lexical variables it introduces only if such variable references are wrapped inside a lambda. And so we write:

(define same-fringe?
  (lambda (tree1 tree2)
    (letrec ((tree-cor-1
              (make-leaf-gen-cor
               tree1
               (lambda (v) (matcher-cor v))))
             (tree-cor-2
              (make-leaf-gen-cor
               tree2
               (lambda (v) (matcher-cor v))))
             (matcher-cor
              (make-matcher-cor
               (lambda (v) (tree-cor-1 v))
               (lambda (v) (tree-cor-2 v)))))
      (matcher-cor 'start-the-ball-rolling))))

Note that call/cc is not called directly at all in this rewrite of same‑fringe?. All the continuation manipulation is handled for us by the coroutine macro.

13.4.2  Getting wet

In the same‑fringe? program, the coroutines for the two trees report back to one managing coroutine, which takes care to call them alternately, as many times as needed. The two tree coroutines don’t interact with each other. Let’s now explore a scenario where all the managed coroutines can resume each other: i.e., the managing coroutine is hands-off and doesn’t micromanage the dispatching at all, simply reporting the final result when the work is done.

An absent-minded Professor F [27] wants to conserve fossil fuel and get some exercise in the bargain. He decides to walk to work in the morning and back home in the evening, and he plans to stick to this routine for five years. The walk is short enough that if the weather is clear when he sets out he will make it to his destination without threat of rain. But if it is raining, which it can be with a certain probability *rain‑prob*, he can’t go out without an umbrella.

(define *rain-prob* 0.4)
(define *max-num-walks* (* 365 2 5)) ;2 walks/day for 5 years

To prepare for this, Prof F decides to keep an umbrella at both home and office. Unfortunately, the smart prof is also absent-minded, so if the weather is clear, he invariably neglects to take an umbrella along, so there is a possibility that when it does rain, both his umbrellas are at the other place and he is stranded. How many walks can he hope to make before being stranded?

We can model each location (home, office) as a coroutine that keeps track of the number of umbrellas it has. Each walk is simulated by one location resuming the other. The resumption’s arguments include whether Prof F is carrying an umbrella (i.e., it is raining) and the number of walks so far (including the current one). When Prof F gets stranded, one of the location coroutines resumes the manager coroutine with the number of walks achieved.

The two location coroutines are just two instances of the same kind, and as such can be generated by a single procedure. We will have this procedure take the other location and the walk-manager as parameters.

(define make-location-cor
  (lambda (other-location-cor manager-cor)
    (coroutine v
      (let ((num-umbrellas 1))
        (let loop ((umbrella? (car v))
                   (walks-so-far (cadr v)))
          (when umbrella?
            (set! num-umbrellas (+ num-umbrellas 1)))
          (cond ((>= walks-so-far *max-num-walks*)
                 (resume manager-cor walks-so-far))
                ((< (random) *rain-prob*)
                 (cond ((> num-umbrellas 0)
                        (set! num-umbrellas
                          (- num-umbrellas 1))
                        (apply loop
                          (resume other-location-cor
                                  (list #t
                                        (+ walks-so-far 1)))))
                       (else
                         (apply loop
                           (resume manager-cor walks-so-far)))))
                (else
                  (apply loop
                    (resume other-location-cor
                            (list #f (+ walks-so-far 1)))))))))))

Each location starts off with one umbrella (num‑umbrellas = 1). Each resumption to the location (whether at the start, or after a walk from the other location) comes with the following info: Whether an umbrella arrived with the latest walk, and the tally of the walks achieved so far. The former causes the location to update its num‑umbrellas. Next, the location uses random to figure out if it’s raining. If it is, it further checks if has an umbrella to spare. If so, it resumes the other location, sending the umbrella; if not, it resumes the manager with the walks‑so‑far. If it isn’t raining, it resumes the other location without an umbrella.

(There is another, not very probable, possibility: The walks‑so‑far have reached the maximum, in which case, the location in question resumes the manager with that number. We need this to avoid an experiment that takes forever.)

The managing coroutine starts off one of the location coroutines, say the home. Since it refers to the home coroutine, we’ll use a coroutine-genertor procedure for it too, taking the home coroutine as paramter:

(define make-manager-cor
  (lambda (home-cor)
    (coroutine dummy-init-arg
      (resume home-cor (list #f 0)))))

All it does is start off the professor at his home, and waits until one of the locations resumes it when the prof has stranded himself.

To start off the process, we need to actually generate the three coroutines, and link them together.

(letrec ((home-cor (make-location-cor
                     (lambda (v) (office-cor v))
                     (lambda (v) (manager-cor v))))
         (office-cor (make-location-cor
                       (lambda (v) (home-cor v))
                       (lambda (v) (manager-cor v))))
         (manager-cor (make-manager-cor
                        (lambda (v) (home-cor v)))))
  ;...

Note that we use lambda-wrapping, so the argument coroutines have a chance to be created before being used.

The body of the letrec then runs the manager

   ;...
   (manager-cor 'start-the-ball-rolling)
   )

This should give the number of walks the prof manages before getting stranded. We’d like to run this simulation multiple times, plus we’d like to vary the rain probability.2 Let’s wrap the letrec inside a procedure that takes these parameters and returns a thunk that can be run as one trial.

(define umbrella-trial
  (lambda (rain-prob)
    (lambda ()
      (when (number? rain-prob) (set! *rain-prob* rain-prob))

      ; the letrec expression goes here
      )))

We can now call, say

((umbrella-trial 0.4))

and this will output the number of walks before strandedness.

To estimate the expected value of the achieved walks, we can use the monte‑carlo procedure we’ve already defined in chapter 6:

(monte-carlo (umbrella-trial 0.4))

You will find that Prof F gets stranded in a matter of mere days, way before the 5-year goal he set himself. What do you think the result will be if the probability of rain is 0 or 1? What if it is a little more than 0 or a little less than 1? Well, you don’t have to puzzle over it. Just call monte‑carlo on umbrella‑trial with the appropriate argument!


1 If your Scheme does not already have this abbreviation, include (define call/cc call‑with‑current‑continuation) in your initialization code and protect yourself from RSI.

2 We could, if we wanted, vary the maximum number of walks too, in the same way. While we’ve used globals *rain‑prob* and *max‑num‑walks* here to avoid complicating the presentation of the code, ideally these parameters should be lexically visible only to the body of umbrella‑trial, with the definitions of the coroutine-generators moving into umbrella‑trial’s body so they can access these parameters.