My blog does explain what reset
and shift
do, so you may want to read that again.
Another good source, which I also point in my blog, is the Wikipedia entry on continuation passing style. That one is, by far, the most clear on the subject, though it does not use Scala syntax, and the continuation is explicitly passed.
The paper on delimited continuations, which I link to in my blog but seems to have become broken, gives many examples of usage.
But I think the best example of the concept of delimited continuations is Scala Swarm. In it, the library stops the execution of your code at one point, and the remaining computation becomes the continuation. The library then does something -- in this case, transferring the computation to another host, and returns the result (the value of the variable which was accessed) to the computation that was stopped.
Now, you don't understand even the simple example on the Scala page, so do read my blog. In it I'm only concerned with explaining these basics, of why the result is 8
.
Try something simpler to see how this works. For example, here's a version of a list-sum
function that receives a continuation argument (which is often called k
):
(define (list-sum l k)
(if (null? l)
???
(list-sum (cdr l) ???)))
The basic pattern is there, and the missing parts are where the interesting things happen. The continuation argument is a function that expects to receive the result -- so if the list is null, it's clear that we should send it 0
, since that is the sum:
(define (list-sum l k)
(if (null? l)
(k 0)
(list-sum (cdr l) ???)))
Now, when the list is not null, we call the function recursively with the list's tail (in other words, this is an iteration), but the question is what should the continuation be. Doing this:
(define (list-sum l k)
(if (null? l)
(k 0)
(list-sum (cdr l) k)))
is clearly wrong -- it means that k
will eventually receive the the sum of (cdr l)
instead of all of l
. Instead, use a new function there, which will sum up the first element of l
too along with the value that it receives:
(define (list-sum l k)
(if (null? l)
(k 0)
(list-sum (cdr l) (lambda (sum) (+ (car l) sum)))))
This is getting closer, but still wrong. But it's a good point to think about how things are working -- we're calling list-sum
with a continuation that will itself receive the overall sum, and add the first item we see now to it. The missing part is evident in the fact that we're ignoring k
. What we need is to compose k
with this function -- so we do the same sum operation, then send the result to k
:
(define (list-sum l k)
(if (null? l)
(k 0)
(list-sum (cdr l) (compose k (lambda (s) (+ s (car l)))))))
which is finally working. (BTW, remember that each of these lambda
functions has its own "copy" of l
.) You can try this with:
(list-sum '(1 2 3 4) (lambda (x) x))
And finally note that this is the same as:
(define (list-sum l k)
(if (null? l)
(k 0)
(list-sum (cdr l) (lambda (s) (k (+ s (car l)))))))
if you make the composition explicit.
(You can also use this code in the intermediate+lambda student language, and click the stepper button to see how the evaluation proceeds -- this will take a while to go over, but you'll see how the continuation functions get nested, each with it's own view of the list.)
Best Answer
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,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 thecall/cc
point.Let's look at some examples:
In the above, the result of
call/cc
is the result of thelambda
which is 3. The continuation wasn't invoked.Now let's invoke the continuation:
By invoking the continuation we skip anything after the invocation and continue right at the
call/cc
point. With(cont 10)
the continuation returns10
which is added to 2 for 12.Now let's save the continuation.
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.