Continuations by example: Exceptions, time-traveling search, generators, threads, and coroutines

More resources

If you like this, you might also like:

• My recommended reading for programming languages.
• Compiling with Continuations.
• MIT's Structure and Interpretation of Computer Programs.

Teasers: Omniscience, SAT-solving

Using first-class continuations, it is possible to add a "non-deterministic (or ambiguous) choice" procedure to a language: amb. The amb procedure takes a list of values, and chooses one of them. The catch here is that amb must choose a value so that all assert statements encountered in the future of the computation are true. For example, the following Scheme code:

(let ((a (amb (list 1 2 3 4 5 6 7)))
      (b (amb (list 1 2 3 4 5 6 7)))
      (c (amb (list 1 2 3 4 5 6 7))))
  
  ; We're looking for dimensions of a legal right
  ; triangle using the Pythagorean theorem:
  (assert (= (* c c) (+ (* a a) (* b b))))
  
  ; And, we want the second side to be the shorter one:
  (assert (< b a))

  ; Print out the answer:
  (display (list a b c))
  (newline))

prints out (4 3 5). The amb procedure chose these values so that when the assertions were encountered later on, they were true.

With amb available, it's trivial to write a SAT-solving macro, so that:

 (sat-solve (and (implies a (not b))
                 (not a)
                 c)
            (list a b c))

evaluates to (#f #f #t). That is, the macro (sat-solve formula body) binds the free variables in the formula so that the formula evaluates to true, and then it evaluates the body expression in the context of these satisfying assigments.

What are continuations?

Concretely, a continuation is a procedure that represents the remaining steps in a computation. For the expression 3 * (f() + 8), think about the remaining steps in the compuation after evaluating the expression f(). For example, in C/Java, the procedure current_continuation is the continuation of the call to f():

void current_continuation(int result) {
 result += 8 ;
 result *= 3 ;
 (continuation of 3 * (f() + 8))(result) ;
}

The value passed to the continuation is the return value of the call.

Some languages (like Scheme and SML/NJ) provide a way to capture the current continuation as a first-class value. In Scheme, the procedure call-with-current-continuation (often abbreviated call/cc) takes a procedure, and passes it the current continuation of the computation.

The standard idiom for call/cc has an explicit lambda term as its argument:

 (call/cc (lambda (current-continuation)
  body))

During the execution of the expression body, the variable current-continuation is bound to the current continuation. If invoked, current-continuation immediately returns from the call to call/cc, and call/cc returns whatever value was passed to current-continuation.

For example, the code:

(display
  (call/cc (lambda (cc)
            (display "I got here.\n")
            (cc "This string was passed to the continuation.\n")
            (display "But not here.\n"))))

will display:

I got here.
This string was passed to the continuation.

What makes first-class continuations so powerful is that the continuation may still be called even after the call to call/cc is finished. For example, the following causes an infinite loop that prints Going to invoke (start) forever:

(let ((start #f))
  
  (if (not start)
      (call/cc (lambda (cc)
                 (set! start cc))))

  (display "Going to invoke (start)\n")
  
  (start))

An idiom for continuation programming

By itself, call/cc can do anything you might need to do with continuations, but it is not the most convenient API. When programming with continuations, I recommend using the a helper procedure, current-continuation:

(define (current-continuation)
 (call/cc (lambda (cc) (cc cc))))

The procedure current-continuation returns the continuation in which it was evaluated.

Then, you can use a conditional pattern to detect whether the continuation was just created, or the continuation has been invoked from some later point:

 (let ((cc (current-continuation)))
  (cond
   ((procedure? cc)    body)
   ((future-value? cc) handling-body)
   (else               (error "Contract violation!"))))

The user-defined predicate future-value? should be able to identify the value passed to the continuation. (Some Scheme implementations support continuation?, which should be used instead of procedure? if it's available.)

Implementing go-when and right-now

An alternative interface for interacting with continuations consists of two procedures: go-when and right-now:

• (right-now) returns the current moment in the computation; and
• (go-when moment) returns the computation to a previously captured moment.

Some applications of continuation may be naturally expressed with just these two procedures.

Time-traveling search

Now we can expose how it was possible to write the teaser examples in the introduction. Under the hood, the procedures amb and assert communicate with each other through a "fail stack." The top of the fail stack contains the next continuation to be invoked whenever an assertion fails. When an assertion fails, it invokes the procedure fail, which pops the fail stack and invokes the result. The amb procedure pushes a new continuation on top of the fail stack, selects the first value in the list, and then removes it. If the list is empty, then the procedure amb invokes the procedure fail.

Exceptions

Exceptions are easily implemented with continations. When an exception is thrown, control needs to return to the first enclosing try form.

To create this behavior with continuations, try forms capture the current continuation before evaluating their body. In Scheme, an implementation of try will also use dynamic-wind to maintain a stack of exception handlers.

When evaluating (dynamic-wind before-thunk do-thunk after-thunk), the run-time will ensure that before-thunk is called whenever execution enters the "dynamic extent" of the computation within do-thunk, and after-thunk is called whenever execution leaves the "dynamic extent" of the computation.

The try block can exploit this behavior by using the before-thunk to push the exception handler, and the after-thunk to pop the exception handler.

Generators

Generators are an elegant solution to the problem of iterating over complex data structures like trees and graphs. Imagine you want to write a for loop like the following:

 for (node n in tree t) {
  do something with n
 }

Some languages (like Java) allow custom iterators, so you could write something like:

 for (Node n : t) {
  do something with n
 }

But, how do you write the iterator t? You could do a walk over the tree and turn it into an array or a list, but this is inefficient--you allocate more than you need to, and you essentially end up iterating twice. The efficient solution (in a language like Java) is to write an iterator that remembers where it is in the search of the tree. This is difficult to get right, and it doesn't feel natural. (Try writing it!)

A simple tree walk is easier to write. If the language supports first-class continuations, then you can use the tree walk approach to iterate without the overhead of an intermediate data structure.

A generator is a procedure that accepts a yield procedure as an argument, with the expectation that it will iterate over some data structure and call yield on every element within the data structure. With continuations, we can instrument a generator to make it suitable for overheadless for-style iteration.

The key idea is to toggle between two continuations--one in the loop, and the other in the generator. When the loop needs another value, it will switch to the continuation inside the generator (passing it a continuation for the loop), and once the generator has a value, it will pass a value back (plus a new continuation for the generator).

Cooperative threads (coroutines)

Continuations make it straightforward to implement cooperative multi-threading (and with macros, it is not difficult to simulate preemptive multithreading.)

In cooperative multithreading, a thread must yield control manually; it will not be preemptively switched out.

The API for cooperative multithreading has five functions:

• (spawn thunk) puts a thread for thunk into the thread queue.
• (quit) kills the current thread and removes it from the thread queue.
• (yield) hands control from the current thread to another thread.
• (start-threads) starts executing threads in the thread queue.
• (halt) exits all threads.

---