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

Continuations are the least understood of all control-flow constructs. This lack of understanding (or awareness) is unfortunate, given that continuations permit the programmer to implement powerful language features and algorithms, including exceptions, backtracking search, threads, generators and coroutines.

I think part of the problem with continuations is that they're always explained with quasi-metaphysical phrases: "time travel," "parallel universes," "the future of the computation." I wrote this article so that my advanced compilers students could piece together how continuations worked by example.

## More resources

If you like this, you might also like:

## 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))

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

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