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.
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 than call 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 each case corresponds to a continuation-savepoint, and where the code inside each case can alter the value of continuation_point and relinquish control to that continuation_point by breaking from the switch 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?
Cheers, V.
Look, i've found this Continuation Passing Style best description on this topic.
The best explanation I've seen is in Paul Graham's book, On Lisp.
The thing that helped me is the idea that in a traditional language with function calls you implicitly pass a continuation any time you make a function call.
Before jumping to a function's code you save some state on the stack (i.e. you push your return address and the stack already contains your locals). This is essentially a continuation. When the function has finished it has to determine where to send the flow of execution. It uses the continuation stored on the stack, popping the return address and jumping to it.
Other languages generalise this idea of continuations allowing you to specify explicitly where to continue the code execution, rather than implicitly continuing on from where the function call was made.
EDIT based on comment:
The continuation is the complete execution state. At any point of execution you can divide the program into two parts (in time, not space) - that which has run to this point, and everything that's going to run from here. The "current continuation" is the "everything that's going to run from here" (you can think of it kind of like a function that will do everything the rest of your program would've done). So the function you supply to call/cc gets passed the continuation that was current when call/cc was invoked. The function can use the continuation to return execution to the call/cc statement (more likely though it'll pass the continuation around to something else, because if it used it directly it could do a simple return instead).
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.
(define x 0) ; dummy value - will be used to store continuation later
(+ 2 (call/cc (lambda (cc)
(set! x cc) ; set x to the continuation cc; namely, (+ 2 _)
3))) ; returns 5
(x 4) ; returns 6
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.
(* 123 (+ 345 (* 789 (x 5)))) ; returns 7
reason: it is because (x 5) replaces the existing continuation,
(* 123 (+ 345 (* 789 _))), with x, (+ 2 _), and returns
5 to x, creating (+ 2 5), or 7.
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.
There are multiple levels to understanding call/cc. First you need to understand the terms and the how the mechanism works. Then an understanding of how and when call/cc is used in "real life" programming is needed.
The first level can be reached by studying CPS, but there are alternatives.
For the second level I recommend the following classic by Friedman.
Daniel P. Friedman. "Applications of Continuations: Invited Tutorial". 1988 Principles of Programming Languages (POPL88). January 1988.
When I was trying to understand call/cc, I found this call-with-current-continuation-for-C-programmers page was helpful.