Programming Language Features
Via Continuations
Andrew Tucker
CSE 583
January 2000
In this paper I will analyze programming language features that can be implemented with continuations. We will first define what continuations are and then list the features that have taken advantage of them in the past . I will then look at built in and user provided continuation features in Common Lisp and Scheme, followed by a similar analysis of the rather obscure language (but interesting from a continuation standpoint) Io. In closing I will discuss a few of the drawbacks of continuations that have lead to them not being more popular and useful.[1]
Continuations can be defined as functions that represent the remainder of a computation. Actually, that definition is a little too simplistic. As we will see later, some languages also include a context in which the computation should be executed. In these cases continuations closely resemble a closure for the computation. Continuations are not always treated as first class objects, but when they are it enables features that are not otherwise available. Some languages such as Scheme treat continuations as a feature that can be used or ignored, while others, such as Io, use it as a main foundation that cannot be ignored.
It is interesting to note the array of possible features that have been implemented with continuations over the years. This list includes, but is not limited to, coroutines[2], exception handling[3], context switches[4], lazy evaluation10, backtracking[5], procedure calls10, operating system trap handlers[6], unwind protection[7], conditional operators10, references[8], and tail recursion[9]. There are actually two types of backtracking available – blind and non-blind. As we will see only blind backtracking can be implemented if continuations are not treated as first-class objects.
While Common Lisp and Scheme have common roots in their history, they are very different when it comes to continuations. The biggest difference is that Common Lisp does not treat continuations as first-class objects while Scheme does. This additional feature in Scheme allows continuations to be returned from functions and embedded in data structures.
The biggest use of continuations in Common Lisp is as a generic exception handling mechanism. For example, in the expression7
(+ 1 ( catch ‘k (* (throw ‘k 2) 3)))
the catch subexpression evaluates to 2 without having ever performed the multiplication. The plus operator is then evaluated and the expression returns 3. The important thing to understand there is that after the catch expression has returned, either via a throw or normal flow of execution, it’s no longer possible to invoke it’s continuation. The result is that it is not possible to return ‘k as a marker for later execution. The primary uses of exception handling such as this are for error exits and blind backtracking.
Backtracking is a method of trying a possible solution to a problem and then, when it is not successful, giving up and trying a different alternative. Blind backtracking means that you cannot return to the point which initiated the backtracking. The flip side is non-blind backtracking which does allow you to return to the initiation point. To demonstrate non-blind backtracking we need continuations to be first-class objects, so we’ll switch to Scheme.
A feature of Scheme that simplifies using continuations is the built-in procedure call-with-current-continuation, abbreviated call/cc. Call/cc makes continuation objects directly accessible to the programmer by packaging up the current continuation as a first-class procedure of one argument and passes it to a procedure passed as a parameter. This continuation can then be invoked at any time in the future with any value as the parameter. The exception handling example given above can be rewritten in Scheme with call/cc like this7:
(+ 1 (call/cc (lambda (k) (* (k 2) 3))))
The continuation k is passed to the anonymous function and is then evaluated as the first argument to the multiplication operator. This causes the value 2 to be returned and the expression returns 3 without having ever executed the multiplication. This example shows how to emulate exception handling, but it does not take advantage of the fact that continuations in Scheme are first-class. To demonstrate this here is an example of non-blind backtracking7:
(let ([backtrack-k any]
[non-blind-k any])
(if (call/cc
(lambda (k)
(set! backtrack-k k)
(backtrack-k #t)))
(begin
(begin first approach
(when time-to-backtrack
(call/cc
(lambda (k)
(set! non-blind-k k)
(backtrack-k #f))))
continue first approach)
(begin
try another approach
(if have-answer
answer
(non-blind-k any)))))
Any is simply used to indicate a value that is unimportant for this demonstration. The continuation of backtrack-k conditionally branches on the argument passed to it. It is first invoked with #t which causes the first attempt to be executed. If, somewhere down the road, this doesn’t look promising, the current continuation is saved in non-blind-k and backtrack-k is invoked with #f which causes the second approach to be tried. If this attempt also turns out to be a loser, we then execute non-blind-k with a dummy parameter, thus continuing the first approach. This is an example of a language feature that can only be implemented when continuations are treated as first-class objects.
There are many other features that can be implemented in Scheme by using call/cc in the manner demonstrated. One of these, unwind protection, is used to guard against unwanted side effects of exception handling. For example, if you want to make sure a resource is released regardless of whether the routine exits normally or via a throw clause, unwind protection provides this. Given the form:
(unwind-protect (body) (postlude))
postlude is guaranteed to execute even if body exits via a throw clause or by calling a continuation in an outer context. For examples of using continuations to implement unwind protection and several other features, see [7].
Another language that takes a very different approach to continuations is Io10. Unlike Scheme and Common Lisp where continuations were an available feature that could be used as necessary, Io uses continuations as the basis almost every feature, including procedure calls, arithmetic operations, conditional operators, and coroutines. Similar to Scheme, Io treats continuations as first-class objects but that is about the only similarity between the two languages.
Io separates continuation into two distinct types: statements and expressions. Statement continuations, in fact, represent an entire Io program. Rather then specifying a sequence of statements, an Io program is represented as a procedure call that takes the rest of the program as a statement continuation parameter. Procedures in Io never actually return, instead they call the passed continuation. When used in this manner, continuations are treated as closures and include the procedure to execute, its environment, and the procedure’s parameters. An Io program like[10]
write 10;
write 11;
terminate
prints the numbers 10 and 11, but it is not executed a s three statements. Instead Io views it as the statement
write 10 (write 11 (terminate))
where 10 is an argument to write and the second parameter is a statement continuation containing the rest of the program. The program ends when the built in procedure terminate is called as the last statement continuation.
An expression continuation is similar to a statement continuation, but takes a parameter that is the value of the expression. An Io program such as10:
+ 2 3 -> Number;
write Number;
terminate
Adds it’s parameters and passes it to the expression continuant (-> Number; write Number; terminate). Conditional operators defined in a similar manner, taking two statement continuations corresponding to a Boolean true false. The Io syntax hides the details, but under the hood continuations are used to do all the real work.
By building on a foundation of continuations as first-class objects, Io provides a wealth of opportunity for user implemented language features. For examples of implementing coroutines, lazy evaluation and linked lists in Io see [10].
Continuations are a powerful and useful feature – so why aren’t they available in more languages? There are two main reasons10. The first problem is that continuations can be very confusing. It is difficult to follow the flow of control and code that makes heavy use of continuations can be difficult to debug. In this way, continuations are similar to the infamous goto statement and are a deterrent to structured programming. The second reason that continuations aren’t used more often is that, in general, they are difficult to implement. Since procedures may be executed any time after they are created, flow of execution does not lend itself well to stack allocation of activation records. Creating records on the heap makes it more difficult to implement efficient garbage collection and, for languages like Io, a distinction must be made between those continuations that are bound to parameters (statement) and those that aren’t (expression).
[1] The main references for this paper are items [7] and [10]
[2] Haynes, Friedman, and Wand Obtaining Coroutines with Continuations, Comput. Lang. 11, ¾ (1986)
[3] Steele Common Lisp: The Language, Digital Press, 1984
[4] Wand Continuation-based Multiprocessing, 1980 Lisp Conference, ACM, New York, 1980
[5] Haynes Logic Continuations, J. Log. Programming 4, (June 1987)
[6] Haynes and Friedman Abstracting timed preemption with engines, Comput. Lang. 12, (1987)
[7] Haynes and Friedman Embedding Continuations in Procedural Objects, ACM TOPLS Vol. 9 Number 4, (October 1987)
[8] Gunter, Remy, and Riecke Return Types for Functional Continuations, Bell Labs, 1997
[9] Appel Compiling With Continuations, Cambridge University Press, 1992
[10] Finkel Advanced Programming Language Design, Addison-Wesley, 1995