lisp - scheme continuations for dummies

Question

For the life of me, I can't understand continuations. I think the problem stems from the fact that I don't understand is what they are for. All the examples that I've found in books or online are very trivial. They make me wonder, why anyone would even want continuations?

Here's a typical impractical example, from TSPL, which I believe is quite recognized book on the subject. In english, they describe the continuation as "what to do" with the result of a computation. OK, that's sort of understandable.

Then, the second example given:

(call/cc
  (lambda (k)
    (* 5 (k 4)))) => 4 

How does this make any sense?? k isn't even defined! How can this code be evaluated, when (k 4) can't even be computed? Not to mention, how does call/cc know to rip out the argument 4 to the inner most expression and return it? What happens to (* 5 .. ?? If this outermost expression is discarded, why even write it?

Then, a "less" trivial example stated is how to use call/cc to provide a nonlocal exit from a recursion. That sounds like flow control directive, ie like break/return in an imperative language, and not a computation.

And what is the purpose of going through these motions? If somebody needs the result of computation, why not just store it and recall later, as needed.

Answer 1

Forget about call/cc for a moment. Every expression/statement, in any programming language, has a continuation - which is, what you do with the result. In C, for example,

x = (1 + (2 * 3)); 
printf ("Done");

has the continuation of the math assignment being printf(...); the continuation of (2 * 3) is 'add 1; assign to x; printf(...)'. Conceptually the continuation is there whether or not you have access to it. Think for a moment what information you need for the continuation - the information is 1) the heap memory state (in general), 2) the stack, 3) any registers and 4) the program counter.

So continuations exist but usually they are only implicit and can't be accessed.

In Scheme, and a few other languages, you have access to the continuation. Essentially, behind your back, the compiler+runtime bundles up all the information needed for a continuation, stores it (generally in the heap) and gives you a handle to it. The handle you get is the function 'k' - if you call that function you will continue exactly after the call/cc point. Importantly, you can call that function multiple times and you will always continue after the call/cc point.

Let's look at some examples:

> (+ 2 (call/cc (lambda (cont) 3)))
5

In the above, the result of call/cc is the result of the lambda which is 3. The continuation wasn't invoked.

Now let's invoke the continuation:

> (+ 2 (call/cc (lambda (cont) (cont 10) 3)))
12

By invoking the continuation we skip anything after the invocation and continue right at the call/cc point. With (cont 10) the continuation returns 10 which is added to 2 for 12.

Now let's save the continuation.

> (define add-2 #f)
> (+ 2 (call/cc (lambda (cont) (set! add-2 cont) 3)))
5
> (add-2 10)
12
> (add-2 100)
102

By saving the continuation we can use it as we please to 'jump back to' whatever computation followed the call/cc point.

Often continuations are used for a non-local exit. Think of a function that is going to return a list unless there is some problem at which point '() will be returned.

(define (hairy-list-function list)
  (call/cc
    (lambda (cont)
       ;; process the list ...

       (when (a-problem-arises? ...)
         (cont '()))

       ;; continue processing the list ...

       value-to-return)))