call/cc

``What is call/cc?'', you ask. Well, first, consider the notion of ``what the program is going to do next''. This is the basis behind a continuation. In a function, the continuation is the context to which the function will return. There is an intermediate representation, often used in compiling functional langauges, called `continuation-passing style' that basically makes every function call into a tail call, possibly along with an additional argument indicating where the tail call will go. But I digress.

In scheme, call/cc is a function that takes as its sole argument a second function of a single argument (call it `foo'). It calls foo with an argument (call it `bar') which is itself a function of a single argument (confused yet? it gets better). foo can proceed as though it had been called normally. When it calls bar (say with argument `baz'), however, control returns to the original caller of call/cc, and it is as though call/cc returned with the value baz.

As described above, this would be useful for implementing break, throw/catch, etc., but without any of that annoying clarity. Here's the cool part: the continuation created (that's `bar' above) has indefinite extent. That means you can store it in a variable somewhere and call it much later, possibly after foo has returned normally, or has called already called bar N times. It is useful for, among other things, implementing coroutines.

I believe it was Guy L. Steele who proved that any traditional control structure could be implemented with call/cc, but I may be mistaking him for someone else.

For more information on continuations, see Compiling with Continuations by Andrew Appel. For more information on call/cc as it exists in Scheme, see R5RS.

A great way to think about the "current continuation" is as a function which, if called, would execute the rest of the program. For example, in a program like this:

1. x = 7
2. print(x)
3. y = 13

between line 2 and line 3 the current continuation is a function which assigns 13 to y.

So, when "print" is called on line 2, it's passed somewhere to come back to when it's done. And that "somewhere" is the current continuation just after the print. Simple, eh? The clever bit is to treat the current continuation as a function just like any other.

Now it's easy to understand call/cc. Take a look at this program:

1. x = 7
2. call/cc(g)
3. y = 13

All that's happening is that the function g get passed the continuation as a parameter. If it calls it, the rest of the program runs from just after the call/cc. Just as if it had "returned".

Programmers who feel more comfortable with C and assembly than with lambda calculus might find the following description helpful: call/cc captures the function call stack that was in effect when it was invoked, and encapsulates it in an object that can be passed around in the program, later to be reinstated. It saves only the stack (and conceptually the processor state, although in practice that can be kept implicit) - the state of of memory and i/o is unaffected by an invocation of a continuation.

Of course, since the actual stack changes all the time, this typically involves making a copy of it, rather than just a pointer. This is expensive, so Scheme implementations typically try to minimize it, for example by storing activation records in a linked list of small stacks, or (in the extreme case) on the heap with no stack at all.

This facility is precisly what is needed to implement various language features:

• Non-local returns (C's setjmp/longjmp), where a procedure skips some part of the call stack and returns to a procedure higher up, can be trivially implemented by capturing the stack before invoking a series of function calls. (see Teach Yourself Scheme: 13.2 Escaping continuations)
• C++-style exceptions is the above non-local returns, combined with a list of places to return to when various things are thrown, so call/cc goes a long way towards implementing them too.
• nondeterminism and backtracking can eloquently be expressed at the langage level by allowing a single function invocation to return several times, until a suitable value has been found. (see Teach Yourself Scheme: 14 Nondeterminism)
• Multiprocessing, allowing several different computations to apparently take place simultaneously, is often implemented on a uni-processor system by storing more than one processor state and function call stack, and periodically switch which one the processor actually uses (so-called threads of control). Since this is precisly what call/cc captures, one can implement multiprocessing on top of it. Co-operative threads only takes a few lines of code; for preemtive threads you also need a way to respond to timer interrupts. (see Teach Yourself Scheme: 15 Engines)

C's closest counterpart to call/cc is the setjmp/longjmp facility, which marks a place in the call stack but does not save a copy of it. Therefore, you cannot use these macros to restore a stack state once the function it was saved in has returned, so they are not as useful. You can implement threads in terms of setjmp/longjmp, but in that case you need some non-portable code to set up multiple stacks to switch between.