Continuations

So our evaluator is now implemented in “continuation passing style”, and all our functions, be them defined in the new λanguage, or primitives defined in JavaScript, take as first argument a callback to invoke with the result (although, that argument is explicit for primitives, but invisible for functions defined in λanguage).

That callback represents the whole future of the program. A complete representation of what to do next. We'll call it “the current continuation”, and we'll use the name k for that variable in the code.

For one thing, if we never call the continuation then the program stops. We cannot do that from λanguage, because make_lambda creates functions that always invoke their continuation. But we can do it from a primitive. I included the following primitive in this page to illustrate that:

globalEnv.def("halt", function(k){});

It's a do-nothing function. It receives a continuation (k) but it doesn't call it.

If you delete the halt(), the output is foo / bar / ***Result: false (because the last println returns a false). But with the halt(), the output is only "foo". There's not even a result in that case, because halt() does not invoke the continuation—so the callback that we pass to evaluate, the one that displays the ***Result line, is not reached. The caller function never notices that the program stopped. If you're doing NodeJS you might have already shot yourself in the foot with this gun.

Let's say we would like to write a “sleep” function, which delays the program but without freezing the browser (so, no dirty loops). We can trivially implement it as a primitive:

globalEnv.def("sleep", function(k, milliseconds){
  setTimeout(function(){
    Execute(k, [ false ]); // continuations expect a value, pass false
  }, milliseconds);
});

A minor inconvenient is that we have to use Execute, since setTimeout will abandon the current stack frame. Calling k(false) directly wouldn't be wrapped in our loop and would fail on the first Continuation exception. Here's how we can use it: (also, try clicking Run a few times quickly, to see that invocations run “in parallel”):

That's something you can't do in plain JavaScript, except by rewriting your code in continuation-passing style manually (and you cannot use a for loop):

(function loop(n){
  if (n < 10) {
    console.log(n);
    setTimeout(function(){
      loop(n + 1);
    }, 250);
  } else {
    println("And we're done"); // rest of the program goes here.
  }
})(0);

Imagine some primitives wrapping around the NodeJS filesystem API, i.e.:

globalEnv.def("readFile", function(k, filename){
  fs.readFile(filename, function(err, data){
    // error handling is a bit more complex, ignoring for now
    Execute(k, [ data ]); // hope it's clear why we need the Execute
  });
});
globalEnv.def("writeFile", function(k, filename, data){
  fs.writeFile(filename, data, function(err){
    Execute(k, [ false ]);
  });
});

Having them, we could do this in λanguage:

copyFile = λ(source, dest) {
  writeFile(dest, readFile(source));
};
copyFile("foo.txt", "bar.txt");

and that's asynchronous. No more callback hell.

Here's a more puzzling example. I wrote the following primitive:

globalEnv.def("twice", function(k, a, b){
  k(a);
  k(b);
});

It takes two arguments a and b and it invokes the continuation twice, once for each argument. Let's run an example:

The output is weird if you never dealt with continuations before, and I'll let you figure it out yourself. Just a short hint: when you click "Run", this program runs once; but it returns twice to its caller!

So far we managed to play with fire only by writing primitive functions (in JS). There isn't a way to intercept the current continuation from the λanguage. The CallCC primitive fills this gap. The name is an abbreviation for Scheme's call-with-current-continuation (which is also commonly spelled call/cc in Scheme).

globalEnv.def("CallCC", function(k, f){
    f(k, function CC(discarded, ret){
        k(ret);
    });
});

It “reifies” the current continuation into a function that can be called directly from the new λanguage. That function will ignore its own continuation (discarded) and will invoke instead the original continuation that CallCC had.

Using this tool we can implement (directly in λanguage, not as primitives!) a wide range of control operators that were previously unthinkable, from exceptions to return. Let's start with the latter.

An implementation for return

Our foo function receives an argument that effectively acts as JS's return statement (only it's invoked like a plain function, because that's, kinda, what it is). It abandons its own current continuation (which would have been to print "bar") and exits early from the function, with the given return value ("DONE"). Of course, that only works if you nest it in a CallCC, to pass the continuation as return. We could provide a wrapper for this:

The advantage being that now we don't need to use CallCC when we invoke foo. It would be nice, of course, if we didn't have to even name the return as a function argument, or to use with-return in the first place, but our λanguage does not allow syntactic extension from itself, so we would need to modify at least the parser (+1 for Lisp).

Easy backtracking

Let's say we want to make a program that finds all pairs of two positive integers upto 100 that multiply to 84. It's not a hard problem and you might be tempted to imagine two nested loops for solving it, but here we'll take a different approach. We'll implement two functions, guess and fail. The former will pick a number, and the latter tells it “try another value”. We're going to use them this way:

a = guess(1);  # returns some number >= 1
b = guess(a);  # returns some number >= a
if a * b == 84 {
  # we have a solution:
  print(a); print(" x "); println(b);
};
fail();  # go back to the last `guess` and try another value

We could do further optimization now by noticing that it's pointless to continue when a is bigger than the square root of 84, or when b is bigger than 84 / a. For this to work we could make guess take two arguments, the start and end, and only pick numbers within that range. But I rest this case, let's move on with continuations.

ES6 yield

EcmaScript 6 will introduce a magic yield operator whose semantics are impossible to implement in the current JavaScript… except by turning code inside-out into continuation passing style. In our new λanguage, explicit continuations give us a way to implement yield.

BUT deriving yield is not exactly a walk in the park. It ended up more subtle than I expected, so I moved the discussion about yield into a separate page. It's advanced and not required for understanding the rest of this material, but I do recommend it if you want more insight into continuations.

Common Lisp's catch and throw

We'll implement two constructs, catch and throw. They can be used like this:

f1 = λ() {
  throw("foo", "EXIT");
  print("not reached");
};
println(catch("foo", λ() {
  f1();
  print("not reached");
}));  # prints EXIT

So to explain, catch(TAG, function) will install a hook that catches TAG “exceptions”, and invoke the function. And throw(TAG, value) will jump back to the most nested catch for that TAG, and make it return value. Whether the catch function exits normally or via a throw, the hook is uninstalled after the “dynamic extent” of the catch finished.

I'll sketch an implementation below.

## with no catch handlers, throw just prints an error.
## even better would be to provide an `error` primitive
## which throws a JavaScript exception. but I'll skip that.
throw = λ(){
  println("ERROR: No more catch handlers!");
  halt();
};

catch = λ(tag, func){
  CallCC(λ(k){
    let (rethrow = throw, ret) {
      ## install a new handler that catches the given tag.
      throw = λ(t, val) {
        throw = rethrow;  # either way, restore the saved handler
        if t == tag then k(val)
                    else throw(t, val);
      };
      ## then call our function and store the result
      ret = func();
      ## if our function returned normally (not via a throw)
      ## then we will get here.  restore the old handler.
      throw = rethrow; # XXX
      ## and return the result.
      ret;
    };
  });
};

You can test below:

The Dark Side of the Force

In the description of catch above, I stated the hook is uninstalled after the “dynamic extent” of the catch finished. That seems to be the case if you look at the code, but the power of CallCC allows one to circumvent that. Philosophically, there are two positions there. I'm all for “Power to the people”—allowing users to subvert the language might not be a bad idea. But in this particular case, I think it is, because it'll be rather confusing than helpful for the user if catch / throw don't stand to their promises.

The way to foul it is simple. You'd call a continuation stored outside the catch. Then the previous throw handler will not be reinstated, because catch won't even know that you exited the block. For example:

The above code displays "After catch" twice, and then "ERROR: No more catch handlers!". The correct operation would be to display "After catch" only once, and then the error. But by exiting the function with a continuation saved outside the dynamic extent of the catch, the line marked "XXX" in the definition of catch never gets reached, so the old throw handler doesn't get restored, and the throw call outside the catch will simply jump back.

(To properly implement exceptions we need delimited continuations. They are discussed in the implementation of yield.)

This is one of the many valid arguments against CallCC (emphasis: against undelimited continuations as provided by CallCC). As much as I like CallCC, I believe it's best if undelimited continuations remain at the primitive level and there is no CallCC to expose them as first-class citizens. Still, I do find continuations fascinating and I think a good understanding of the concept is essential for being able to implement other constructs that are truly useful in practice.

Next we'll start working on the compiler — let's make this thing fast!