Continuation-Passing Style

and why JavaScript developers might be interested in it

Topic: JavaScript, 'AJAX', continuations
Audience: JavaScript programmers
Author: Marijn Haverbeke
Date: July 24th 2007

Most programmers, at least those whose interests go beyond just Java or PHP, will at some point have come across the concept of continuations. When I read the Scheme Revised Report for the first time, I was rather bewildered by that part of the language. To recap: 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.

In most real Scheme programs I have seen, stack-unwinding tricks that other languages would handle with try/catch or similar are the only applications of call-with-current-continuation. The canonical example application of continuations, 'non-deterministic programming' ― basically a way to abstract backtracking in a search algorithm ― is not something that is very hard to do without continuations. Some people even advocate removing continuations from the Scheme standard entirely, on the basis that they are hard to implement efficiently. They conflict with the 'call stack' model of computation, and combine very poorly with dynamically-scoped cleanup code such as C++ destructors or other languages' finally clauses.

Because of these things, I used to consider continuations mostly a toy. But a very cute toy. I was delighted to see, for example, that in a language that does not support call-with-current-continuation but does have closures, any code can be converted to continuation-passing style by a rather simple transformation. If we have a JavaScript program...

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

Of course, the transformation does not have to effect every function. The toUpperCase method, for example, is a built-in JavaScript function, and we can not transform it. Nor do we really have to ― it always returns normally. A function in continuation-passing style can call regular functions with no ill effects.

The transformed version of the above code might make a few things clear. For brevity, continuation arguments are called simply c.

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(){});

So, we've created code that does exactly the same as the earlier version, but is twice as confusing. Not much gain so far. But bear with me. 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.

function doXHR(url, succeed, fail) {
  var xhr = new XMLHttpRequest(); // or ActiveX equivalent
  xhr.open("GET", url, true);
  xhr.send(null);
  xhr.onreadystatechange = function() {
    if (xhr.readyState == 4) {
      if (xhr.status == 200)
        succeed(xhr.responseText);
      else
        fail(xhr);
    }
  };
}

function tryLogin(name, password, c) {
  doXHR("login?name=" + encodeURIComponent(name) +
        "&password=" + encodeURIComponent(password),
    function(response) {
      c(response == "ok");
    },
    function(xhr) {
      warn("Could not get login information from server. (" +
           xhr.statusText + ").");
      c(null);
    });
}

Note how doXHR takes two continuations, one for failure and one for success. Also note that values that would normally be returned by functions are now passed to their continuations instead.

You can also see that tryLogin passes null to its continuation when it fails. JavaScript with continuation-passing style is not all beauty and sunshine. For one thing, it breaks exception handling. Since the stack is no longer a reliable indication of the current computation, the stack unwinding that an exception does will no longer work as expected. The same goes for finally clauses. When necessary, a function can abort a computation entirely by not calling its continuation. And if you really want to you can implement a simple substitute for exception handling by storing a stack of 'catch' continuations in a global array ― a function that would normally throw an exception now just calls the continuation on the top of that stack, and functions that would normally catch exceptions now push a function onto that stack, and pop it off when they are done.

Another issue that you should be aware of is that, since continuation-passing functions never really return, and JavaScript implementations do not typically provide 'tail-call' optimisation, it is possible to blow the call stack when you have too many such functions calling each other without resetting the stack through setTimout or a callback. In my experience this rarely becomes a problem, but when it does you can add a strategic setTimout of zero milliseconds to reset the stack manually.

Finally, JavaScript is notoriously sluggish about function calls, and all these extra calls will not exactly make your scripts run faster. Most JavaScript programs do not take up a noticeable amount of CPU time, but for some heavy-handed scripts this extra overhead might be a problem.

So I do not recommend anyone to go ahead and convert his entire code-base to continuation-passing style. There are scripts, however, especially those making lots of requests to a server, that will benefit from such a transformation. It is never necessary to convert every function. Only those that might get 'interrupted' (or call other functions that might get interrupted) benefit from having a first-class continuation.

Other good approaches to the same problem include Narrative JavaScript, a system that compiles a JavaScript-like language down to regular JavaScript. This language adds some event-based syntax, which allows you to write 'interruptable' code without manually transforming your functions. (It doesn't use actual continuations, so you don't have the stack issues.) Jwacs is a similar approach, but this one does use real continuations, with a trampoline calling system to prevent stack overflows.

Deferred objects, as seen in MochiKit, Dojo, and the Python library Twisted are a less invasive, but still nicely structured way to write code that has to wait for something. Instead of returning the actual result, a function will return a Deferred object that encapsulates this result. Callers can register callbacks on this object to handle it further, but if they need to return something to their own callers, they also have the possibility of just adding a function to the deferred that somehow transforms the result, and then returning it, and so on. This requires a bit of glue code, but does keep the handling of incoming results local to the functions that are concerned with them.

If you have any comments related to the above, drop me an e-mail at marijnh@gmail.com. If you say something generally interesting, I'll include your reaction here at the bottom of the page.

[ home - eloquent javascript - codemirror ]