What is call/cc?

问题:

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.

回答1:

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.

回答2:

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.

回答3:

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?

回答4:

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

回答5:

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

回答6:

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

回答7:

The best explanation I've seen is in Paul Graham's book, On Lisp.

回答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.

回答9:

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.

回答10:

Take a look at the description and implementation of call/cc for FScheme: http://blogs.msdn.com/b/ashleyf/archive/2010/02/11/turning-your-brain-inside-out-with-continuations.aspx