Continuation Patterns

What makes Scheme Scheme? Any list of features purporting to answer that question would surely include

• lexical scoping,
• tail recursion, and
• first class continuations

The first two are familiar to all Lisp programmers and are also features of Common Lisp either as part of the language definition (lexical scoping) or as a practical matter (tail recursion). Continuations are less well understood but are one of the features that make Scheme so powerful. They represent, to my mind, the epitome of the familiar Scheme mantra that languages are made powerful not by piling on features, but by removing weaknesses and restrictions that make the new features seem necessary.

As a practical application of this principle, consider exceptions: Scheme doesn't have any (at least prior to R6RS), but they are easily implemented with continuations. That's a facile statement, of course, but it doesn't rise to the level of "Scheme is Turing complete so …" Instead, it should be understood in the sense that one can easily write an exception library using continuations without needing to make changes to the Scheme compiler or interpreter. Rather than imposing a single exception handling mechanism on all users, Scheme allows each user to define one suited specifically to his or her needs. Here's a nice example from Dan Friedman, Chris Haynes, and Kent Dybvig that shows how easily this can be done.

The problem, as I hinted above, is that continuations are tricky to understand and as a result aren't understood at all by many Scheme programmers. I just stumbled across an old (2001) paper by Darrell Ferguson and Dwight Deugo that might help. They begin by explaining continuations in terms of contexts and escape procedures. To be sure, this is a conceptual definition that may or may not have anything to do with an actual implementation, but it does serve to help beginning Scheme programmers get their heads around the notion of continuations.

The meat of the paper is an examination of several continuations usage patterns. They begin with showing how to use continuations to escape from a loop and discuss why this technique can be preferable to the usual naive method of setting an "end" value that gets checked each time through the loop. From there they move on to the related pattern of breaking out of a recursion discarding any partial results that have been built up.

Next they consider control structures by showing how to implement a loop with continuations and how to escape from and then reenter into a recursion. Finally, they consider the more complicated patterns that implement coroutines, non-blind backtracking, and multitasking.

This is a useful paper for someone who is looking for examples of how call/cc can be used to solve real problems. Unless you're completely familiar and comfortable with continuations, it's definitely worth a read.