lambdaschemecontinuationslambda-calculuscallcc

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.


Solution

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