Continuations In Mozilla

I came upon two interesting subjects recently:

• Lambda the Ultimate's Continuations discussion
• Aspect-oriented-programming in JavaScript in 20 lines of code

In the spirit of Roman Porotinkov's AOP posting, I'd like to add this attempt to explain continuations with a short implementation in JavaScript. Here's are three sample functions that we'll work with...

function capitalize(str) {

  // #a - next line to be explained soon.

  capitalizeReturns[capitalizeReturns.length] = __cont__; 

  return str.charAt(0).toUpperCase() + str.substring(1);

}



function prettify(firstName, lastName) {

  // #b - next line to be explained soon.

  prettifyReturn = __cont__; 

  firstName = capitalize(firstName);

  lastName = capitalize(lastName);

  return firstName + " " + lastName;

}



function formalName(personName, prefix) {

  var parts = personName.split(',');

  personName = prettify(parts[1], parts[0]);

  return prefix + " " + personName

}



// #c - the following vars will be explained soon

var __cont__          = null;

var prettifyReturn    = null;

var capitalizeReturns = []; 

Here are some sample invocations...

formalName("yen,steve", "Mr.");          // returns "Mr. Steve Yen"

formalName("bush,george", "President");  // returns "President George Bush"

Up to this point, the __cont__ value has been null. Let's make __cont__ useful by introducing some continuation conversion functions...

function continuate(funcName) {

  var funcText = uneval(this[funcName]);

  if (funcText.charAt(0) == '(')

      funcText = funcText.slice(1, -1);

  funcText = funcText.replace(/return\s*(.*?);/g, "return __cont__($1);");

  while (true) {

      var newStr = funcText.replace(/(var\s+)?(\w+)\s*=\s*(\w+)\s*\((.*?)\);/,

                                    "return $3($4, function($2) {");

      if (newStr == funcText) break;

      funcText = newStr + ")}";

  }

  funcText = funcText.replace(/\{/, "{ var __cont__ = getContinuation(arguments); ");   

  return this[funcName] = eval("(" + funcText + ")");

}



function getContinuation(args) {

  var cont = args[args.length - 1];

  if (cont != null && typeof cont == "function")

      return cont;

  return function(res) { return res; }; // An identity function.

}

That's it! Next, we'll convert our sample functions by "continuate"-ing them...

continuate("formalName");

continuate("prettify");

continuate("capitalize");

Now, let's go get some continuations...

var prettifyReturn    = null; // holds the continuation to prettify()

var capitalizeReturns = [];   // holds the continuations for capitalize()



formalName("bush,george", "President"); // returns "President George Bush"

prettifyReturn("Bill Clinton");         // returns "President Bill Clinton"

capitalizeReturns[0]("George H");       // returns "President George H Bush"

capitalizeReturns[1]("Washington");     // returns "President George Washington"

How does it work? The calls to continuate() transformed the original three sample functions to look like...

function capitalize(name) {

  var __cont__ = getContinuation(arguments);

  capitalizeReturns[capitalizeReturns.length] = __cont__; // same line #a as above

  return __cont__(name.charAt(0).toUpperCase() + name.substring(1));

}



function prettify(firstName, lastName) {

  var __cont__ = getContinuation(arguments);

  prettifyReturn = __cont__; // same line #b as above

  return capitalize(firstname, function(firstName) {

    return capitalize(lastName, function(lastName) {

      return __cont(firstname + " " + lastName);

    })

  })

}



function formalName(personName, prefix) {

  var __cont__ = getContinuation(arguments);

  var parts = personName.split(",");

  return prettify(parts[1], parts[0], function(personName) {

    return __cont__(prefix + " " + personName);

  })

}

This is just a poor-man's continuation-passing style transformation. The function invocations of capitalize() and prettify() have been converted to take an extra closure parameter -- the continuation. Of course, JavaScript supports first-class lexical closures. Way to go Brendan.

The getContinuation() function works because JavaScript supports variable number of function call arguments (varargs). So, we can also tack on a continuation closure as the last argument to our function calls and retrieve it using arguments[arguments.length - 1].

At line #b in the sample functions, the variable prettifyReturns is assigned the continuation closure for the prettify() invocation. At line #a, since capitalize() is invoked twice, first on "george", second on "bush", we use an array (capitalizeReturns) that records those 2 continuation closures.

About continuate():

We don't have Lisp-style macros in JavaScript, which would have made this more powerful (but harder to understand?). But, modern versions of JavaScript (JavaScript 1.5, in Mozilla Firebird) support uneval(). With that, we can apply the popular bag-o-regular-expressions to do our function text munging. The regexps I put into continuate() really only scratch the surface of possible transformations. So far, they only convert the following function call styles: var x = foo(args...) and x = foo(args). I'm sure if you had a real JavaScript parser (maybe even one written in JavaScript), you could try a full continuation transformation approach that Paul Graham sketches out in On Lisp. But, none of us have that much free time.

Anton van Straaten on Lambda-the-Ultimate says that "a continuation *is* a closure". And, we've just walked through continuations implemented as closures. A lot of closures. Just see how unpretty the prettify() code became, and while easy to understand, it'll be even slower to run.

Finally, with my understanding to continuations and how much state and resources they can chew up, I don't see how continuation-based web programming (like Seaside) can scale up.

Other caveats:

• I developed this using standard Rhino, the JavaScript 1.5 implementation in Java.
• It only works in JavaScript 1.5, hence this will (likely) work in Mozilla Firebird and (definitely) not in IE, because of uneval().
• By using varargs in this toy implementation, it means that your functions can't also use varargs cleanly.