I've tried several times to grasp the concept of continuations and call/cc. Every single attempt was a failure. Can somebody please explain me these concepts, ideally with more realistic examples than these on Wikipedia or in other SO posts.
I have background in web programming and OOP. I also understand 6502 assembly and had a minor randez-vous with Erlang. However still, I can't wrap my head around call/cc.
To compare it to C, the current continuation is like the current state of the stack. It has all the functions waiting for the result of the current function to finish so they can resume execution. The variable captured as the current continuation is used like a function, except that it takes the provided value and returns it to the waiting stack. This behavior is similar to the C function longjmp where you can return to lower portions of the stack immediately.
One key difference between the C stack and a continuation is that a continuation can be used at any point in the program, even if the state of the stack has changed. This means that you can essentially restore earlier versions of the stack and use them again and again, leading to some unique program flow.
The ability to save and restore the state of a program has much in common with multithreading. In fact, you can implement your own thread scheduler using continuations, as I've attempted to illustrate here.
The best explanation I've seen is in Paul Graham's book, On Lisp.
When I was trying to understand call/cc, I found this call-with-current-continuation-for-C-programmers page was helpful.
Imagine your script is a video-game stage. Call/cc is like a bonus stage.
As soon as you touch it you are transfered to the bonus stage (i.e. the definition of the function passed as argument to call/cc [f in this case]).
Bonus stages are different from ordinary stages because usually they have an element (i.e. the argument of the function passed to call/cc) that if you touch it you lose and are transported back to the normal stage.
So it doesnt matter if there are many
args
, when you reach one of them its over. So our execution reaches(arg 42)
and returns it to the sum(+ 42 10)
.Also there are some remarks worth noticing:
(define f (lambda (k) (+ k 42))
, because you cannotsum
a function.(define f (lambda (k) (f 42 10)))
because the continuation expects only one argument.touching
any exit, in this case the function proceeds like any ordinary function (e.g.(define f (lambda (k) 42)
finishes and returns 42).A trivial example of using continuation would be implementing a thread (fiber if you wish) manager on a single-processor machine. The scheduler would interrupt the execution flow periodically (or, in the case of fibers, be invoked at various strategic points in the code), save the continuation state (corresponding to the current thread), then switch to a different continuation state (corresponding to a different thread whose state was saved previously.)
Referring to your assembly background, the continuation state would capture such details as instruction pointer, registers, and stack context (pointer), to be saved and restored at will.
Another way of using continuation would be to think of replacing method calls with several thread-like entities that co-exist in parallel (either running or suspended) passing control to each other using continuation contexts instead of the 'classic'
call
paradigm. They would operate on global (shared) data instead of relying on parameters. This is to some extent more flexible thancall
in the sense that stack does not have to wind up then down (calls
are nested), but control can pass around arbitrarily.Attempting to visualize this concept in a language such a C, imagine having one big loop with a single
switch(continuation_point) { case point1: ... }
statement, where eachcase
corresponds to a continuation-savepoint, and where the code inside eachcase
can alter the value ofcontinuation_point
and relinquish control to thatcontinuation_point
bybreak
ing from theswitch
and engaging the next iteration in the loop.What is the context of your question? Any particular scenarios you are interested in? Any particular programming language? Is the thread/fibre example above sufficient?
Look, i've found this Continuation Passing Style best description on this topic.
Here's stripped of details copy of that article: