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.

Answer 2

Look, i've found this Continuation Passing Style best description on this topic.

Here's stripped of details copy of that article:

Author: Marijn Haverbeke Date: July 24th 2007

Scheme's call-with-current-continuation function makes it possible to capture a computation, a state of the call stack as it were, and resume that same state at a later time. On top of such a primitive, various form of exception handling and C-like longjmp tricks can be implemented.

function traverseDocument(node, func) {
  func(node);
  var children = node.childNodes;
  for (var i = 0; i < children.length; i++)
    traverseDocument(children[i], func);
}   

function capitaliseText(node) {
  if (node.nodeType == 3) // A text node
    node.nodeValue = node.nodeValue.toUpperCase();
}

traverseDocument(document.body, capitaliseText);

This can be transformed as follows: We add an extra argument to every function, which will be used to pass the function's continuation. This continuation is a function value representing the actions that must happen after the function 'returns'. The (call) stack becomes obsolete in continuation-passing style ― when a function calls another function, that is the last thing it does. Instead of waiting for the called function to return, it puts any work it wants to do afterwards into a continuation, which it passes to the function.

function traverseDocument(node, func, c) {
  var children = node.childNodes;
  function handleChildren(i, c) {
    if (i < children.length)
      traverseDocument(children[i], func,
                       function(){handleChildren(i + 1, c);});
    else
      c();
  }
  return func(node, function(){handleChildren(0, c);});
}

function capitaliseText(node, c) {
  if (node.nodeType == 3)
    node.nodeValue = node.nodeValue.toUpperCase();
  c();
}

traverseDocument(document.body, capitaliseText, function(){});

Imagine we have a huuuuge document to capitalise. Just traversing it in one go takes five seconds, and freezing the browser for five seconds is rather bad style. Consider this simple modification of capitaliseText (don't pay attention to the ugly global):

var nodeCounter = 0;
function capitaliseText(node, c) {
  if (node.nodeType == 3)
    node.nodeValue = node.nodeValue.toUpperCase();

  nodeCounter++;
  if (nodeCounter % 20 == 0)
    setTimeout(c, 100);
  else
    c();
}

Now, every twenty nodes, the computation is interrupted for a hundred milliseconds to give the browser interface a moment to respond to user input. A very primitive form of threading ― you can even run multiple computations at the same time like this.

A more commonly useful application of this is related to XMLHttpRequests, or the various IFRAME and SCRIPT tag hacks used to simulate them. These always require one to work with some kind of call-back mechanism to handle the data that the server sends back. In simple cases, a trivial function will do, or a few globals can be used to store the state of the computation that must be resumed after the data comes back. With complex cases, for example when the data is being used by a function that must return some value to its caller, continuations simplify things considerably. You just register the continuation as the call-back, and your computation is resumed when the request finishes.

Answer 3

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:

• Not all functions can be used with call/cc. Since it expects a continuation (that is a function), you cannot have an f like this: (define f (lambda (k) (+ k 42)) , because you cannot sum a function.
• Also you cannot have (define f (lambda (k) (f 42 10))) because the continuation expects only one argument.
• You may finish without touching any exit, in this case the function proceeds like any ordinary function (e.g. (define f (lambda (k) 42) finishes and returns 42).

Answer 4

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?

Answer 5

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).

Answer 6

When I was trying to understand call/cc, I found this call-with-current-continuation-for-C-programmers page was helpful.

Answer 7

Take a look at the description and implementation of call/cc for FScheme

Answer 8

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.

Answer 9

You're probably familiar with the idea of "transfer of control", which - in languages like C - manifests itself in statements such as break, continue, return and goto, or - in languages that support exceptions - the try and catch statements.

You can imagine that break and continue could be implemented using goto (i.e. for every piece of code that uses break or continue, you could easily write equivalent code that uses goto with appropriately placed labels).

So for now let's focus on goto, which - as you should know from your experience with assembly - is the most basic control transfer operation (you can imagine that it would be hard to transform return to use goto - but we'll get on to this).

So let's suppose that you have a program (say, in C) that looks like this:

instruction1;
instruction2;
...
instructionN;

where instructionK could either be an assignment or a function call or the statement if (condition) goto some_label.

You could prepend each line with a unique label for goto:

line1: instruction1;
line2: instruction2;
...
lineN: instructionN;

In languages that support first-class continuations, there is a special function call/cc, which works like this: suppose that instructionK has the form

...
lineK: call/cc(function(continuation) { ... })
lineK+1: instructionK+1;
...

I have used JavaScript's notation for anonymous functions here, because C does not support anonymous functions. You can see that the function has one argument, which I have called continuation.

The body of the function is executed immediately when call/cc is invoked, and the value of the continuation argument will be the address of lineK+1 (roughly speaking). Or, in other words, the current continuation in lineK is the lineK+1 - this is how you could think about it.

However, the typical interface is that it's not just address: the continuation argument is a procedure which, when invoked, performs a jump to the lineK+1. This is how call/cc allows to implement a return statement.

So you could think of call/cc as a kind of a goto on steroids. The thing is, that you can not only call the continuation argument, but you can also store it in variables or other data structures.

The most interesting use of call/cc that I have seen is the implementation of the Amb evaluator from Dorai Sitaram's book Teach Yourself Scheme in Fixnum Days (you can compare it with the version from Structure and Interpretation of Computer Programs which doesn't use call/cc).

I have once also implemented my own mechanism for resource management using continuations, as described here.

But other than that, first-class continuations were subject to criticism, and I wouldn't recommend using them in production code (they are very similar to the setjmp/longjmp mechanism available in C, which I would also discourage. But if you'd like to see some usage example, here's how you could use it to implement multitasking in 100 lines od code).

Answer 10

The model I used for understanding continuations from an imperative standpoint is that it is a copy of the call-stack combined with the a pointer to the next instruction.

Call/cc calls a function (passed as an argument) with the continuation as an argument.