lambda - What is call/cc?

Question

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.

Answer 1

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.

Here's a Scheme REPL interaction to illustrate:

> (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
5

> (x 4)                 ; returns 6
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.