call-with-current-continuation-for-C-programmers


If you're a C programmer then you've probably read the various introductions and tutorials on call-with-current-continuation (call/cc) and come out not much wiser about what it all really means. Here's the secret: it's setjmp/longjmp.

But on no account say that to any Scheme programmers you know, it'll send them into paroxysms of rage as they tell you you don't know what you're talking about. Oh, and if you're a Scheme programmer who's accidentally stumbled on this page then please, please, stop reading now, for the sake of your blood pressure. (Or in any case remember this page is for refugee C programmers, not for you.)

C versus Scheme

Basically call/cc is like setjmp. It records a dynamic point in the program execution, one which you can return to, ie. jump to, later if you want. setjmp does its thing by filling in a jmp_buf you supply, but call/cc creates a continuation object and calls your nominated bit of code with it.

The way call/cc calls a function to give you the continuation can be confusing. Essentially it's just a clean way to get the continuation to you and keep out of the way of subsequent jumps back to the saved point. It's typical to do no more that save away the continuation object

     (call/cc (lambda (cont) 
                (set! my-saved-cont cont))) 

In the name "call-with-current-continuation", "call" refers to the way a function is called to hand over the continuation. Don't be confused by the fact the continuation object is later invoked by calling it, that's entirely separate.

Once you've got a continuation object, calling it as say (cont 123) is like a C code longjmp(jbuf, 123). It's a jump back to the original call/cc point, and the return value from the call/cc is the 123 in the invoking call, just like setjmp returns the value passed to longjmp. In Scheme of course any object can be "returned" in this way (and even values? for more than one object), not just a single int.

This "multiple returning" by the call/cc shouldn't be any more confusing that the multiple returning of a setjmp. However because Scheme is more flexible it's easy to be creative with what's returned and when and why, to create confusion where it shouldn't exist. The key idea though remains a dynamic goto with a value passed.

In C it's only possible to jump up the stack, to a point in the current function or a higher calling function. But in Scheme you can jump back down as well, or even "sideways". To do this call/cc effectively saves the whole stack. In fact in some Scheme implementations (for example Guile) a block copy of the stack is exactly how it's done.

This downwards/sideways jumping is a powerful feature. Genuine co-routines can be implemented. Or a long-running "job" can be suspended and resumed periodically, even becoming a cooperative (and portable) multi-tasking system. Such things are not really possible (or only with some difficulty) in C with setjmp/longjmp.

An important note should be added about the way variables are saved in a continuation. In C if you were to copy the stack then you copy the values in local variables (automatics), and restoring would put back the values copied. But effectively in Scheme it's just "what variables are visible" which is saved and restored, the actual locations holding the values are separate. So if you have a continuation, jump into it and change some values, and jump in again later then the changes you made are still there. This is much the same as in the notion of a closure: the variables visible to it keep their values between invocations.

Not a goto

When Scheme folks get hot and bothered about continuations not being gotos what they normally mean is that the idea of a continuation is much more fundamental.

A continuation represents the "what thing(s) to do next" for a program and execution proceeds by manipulating that. A function call expands the continuation with the body of the function (with its parameters bound to the called values). A return reduces it back to the receiver of the result in question, etc.

This is an abstract idea about what program execution means, but in fact various Scheme implementations do it exactly this way, using the heap to record the current continuation. At its simplest the current continuation in such systems is like a list grown by consing onto the front, and reduced by cdring down. In such a system capturing a continuation is merely saving a reference to the list, and jumping to it just plugs that back in as the current "what to do". (And it can be seen that method is fast, where a stack copy is slow, though both have advantages.)


category-learning-scheme