CPS Evaluator

Our language has two problems: (1) recursion is limited by the JS stack, so there is no effective way to do iteration; and (2) it's slow. We'll solve the first problem here, unfortunately at the cost of making it even slower. We're going to rewrite our evaluator in “continuation-passing style” (CPS).

What is CPS

You do it in NodeJS all the time. For example:

fs.readFile("file.txt", "utf8", function CC(error, data){
  // this callback is the "continuation"
  // instead of returning a value by using `return`,
  // readFile will invoke our callback with the data.
});

At each step of the way, there's some callback you need to invoke in order to continue. Continuation-passing style makes control flow “explicit” — you don't return, you don't throw, you don't break or continue. No arbitrary jumps. You can't even use for or while loops with asynchronous functions. If that's the case, why would we even have all those keywords in the language?

Manually writing programs in CPS is unintuitive and error-prone, but we'll have to rewrite our evaluator this way.

The evaluate function

The CPS evaluate will receive three arguments: the expression (AST), the environment, and a callback to invoke with the result. Here's the code and I'll comment on each case, as before:

function evaluate(exp, env, callback) {
    switch (exp.type) {

For constants, we just need to return their value. But remember, there's no return—instead we're invoking the callback with the value.

      case "num":
      case "str":
      case "bool":
        callback(exp.value);
        return;

"var" is also simple: fetch the variable from the environment, pass it to the callback.

      case "var":
        callback(env.get(exp.value));
        return;

For "assign" nodes we need to evaluate the "right" expression first. For this we're calling evaluate, passing a callback that will get the result (as right). And then we just invoke our original callback with the result of setting the variable (which will be the value, in fact).

      case "assign":
        if (exp.left.type != "var")
            throw new Error("Cannot assign to " + JSON.stringify(exp.left));
        evaluate(exp.right, env, function(right){
            callback(env.set(exp.left.value, right));
        });
        return;

Similarly, for "binary" nodes we need to evaluate the "left" node, then the "right" node, and then invoke the callback with the result of applying the operator. Same as before, we call evaluate recursively and pass a callback that carries on the next steps.

      case "binary":
        evaluate(exp.left, env, function(left){
            evaluate(exp.right, env, function(right){
                callback(apply_op(exp.operator, left, right));
            });
        });
        return;

"let" looks a little more complicated, but it's very simple. We have a number of variable definitions. Their "def" (initial value) can be missing, in which case we make them false by default; but when the value is present, we need to call evaluate recursively in order to compute it.

If you worked in NodeJS you might have solved similar problems many times already. Because of the callback, we can't use a straight for, so we need to compute those expressions one by one (imagine the evaluate function might not return immediately, but asynchronously). The loop function below (immediately invoked) receives an environment and the index of the current definition to compute.

• If that index is equal to vars.length that means we finished and the environment has all the defs, hence we evaluate(exp.body, env, callback). Note that this time we're not invoking the callback ourselves, but just pass it to evaluate as the next thing to do after running exp.body.

• If the index is smaller then evaluate the current definition and pass a callback that will loop(scope, i + 1), after extending the environment with the definition that we just computed.

      case "let":
        (function loop(env, i){
            if (i < exp.vars.length) {
                var v = exp.vars[i];
                if (v.def) evaluate(v.def, env, function(value){
                    var scope = env.extend();
                    scope.def(v.name, value);
                    loop(scope, i + 1);
                }); else {
                    var scope = env.extend();
                    scope.def(v.name, false);
                    loop(scope, i + 1);
                }
            } else {
                evaluate(exp.body, env, callback);
            }
        })(env, 0);
        return;

Again, we'll handle the "lambda" in a separate function that I'll describe below.

      case "lambda":
        callback(make_lambda(env, exp));
        return;

For executing an "if", we evaluate the condition. If it's not false then evaluate the "then" branch, otherwise evaluate the "else" branch if it's present, otherwise pass false to the callback. Again note that for "then"/"else" we don't have to run the callback ourselves, but just pass it to evaluate as the “next thing to do” after computing those expressions.

      case "if":
        evaluate(exp.cond, env, function(cond){
            if (cond !== false) evaluate(exp.then, env, callback);
            else if (exp.else) evaluate(exp.else, env, callback);
            else callback(false);
        });
        return;

A "prog" node is handled somewhat similar to "let", but it's simpler because it doesn't need to extend scope and define variables. Any case, the same general pattern: we have a loop function which handles the expression number i. When i is equal to prog.length then we're done, so just return the value that the last expression evaluated to (and by “return” I mean, of course, invoke the callback with it). Note we're keeping track of the last value by passing it as argument to loop (initially false, in case the prog body is empty).

      case "prog":
        (function loop(last, i){
            if (i < exp.prog.length) evaluate(exp.prog[i], env, function(val){
                loop(val, i + 1);
            }); else {
                callback(last);
            }
        })(false, 0);
        return;

For a "call" node we need to evaluate "func" and then evaluate the arguments, in order. Again, a loop function handles them similarly as we needed to do in "let" and "prog", only this time it builds an array with the results. The first value in that array must be the callback, because closures returned by make_lambda will also be in continuation-passing style, thus instead of using return they will invoke the callback with the result.

      case "call":
        evaluate(exp.func, env, function(func){
            (function loop(args, i){
                if (i < exp.args.length) evaluate(exp.args[i], env, function(arg){
                    args[i + 1] = arg;
                    loop(args, i + 1);
                }); else {
                    func.apply(null, args);
                }
            })([ callback ], 0);
        });
        return;

Same epilogue as before. If we don't know what to do, throw an error.

      default:
        throw new Error("I don't know how to evaluate " + exp.type);
    }
}

You can notice that each case above ends with a return. There's no return value though; the result is always passed to the callback. If anything, we would wish that execution never reaches back to the case; but it's how JS works. We need those return statements in order to not fall down to the next case.

The new make_lambda

In this version of our evaluator, all functions will receive as first argument the “continuation” — a callback to invoke with the result. Following it are the other arguments as passed at run-time, but this one is always inserted by the evaluator. Here's the code for the new make_lambda:

function make_lambda(env, exp) {
    if (exp.name) {
        env = env.extend();
        env.def(exp.name, lambda);
    }
    function lambda(callback) {
        var names = exp.vars;
        var scope = env.extend();
        for (var i = 0; i < names.length; ++i)
            scope.def(names[i],
                      i + 1 < arguments.length
                        ? arguments[i + 1]
                        : false);
        evaluate(exp.body, scope, callback);
    }
    return lambda;
}

It's only slightly modified. It extends the scope with the new variable bindings (for the arguments). It must account for that “callback” argument as being the first one (hence, i + 1 when wondering in the arguments). And finally it uses evaluate to run the function body in the new scope, as before, but passing the callback to the evaluator instead of returning the result.

Incidentally, notice that this is the only place where I used an iterative loop (for). That's because the arguments are already computed when the "call" node was evaluated—we need not call the evaluator for them and pass a callback to get the value of each argument.

Primitives

For the CPS evaluator, primitive functions will receive a callback as first argument. We must keep this in mind while defining primitives. Here's some simple test code for the new version:

var code = "sum = lambda(x, y) x + y; print(sum(2, 3));";
var ast = parse(TokenStream(InputStream(code)));
var globalEnv = new Environment();

// define the "print" primitive function
globalEnv.def("print", function(callback, txt){
  console.log(txt);
  callback(false); // call the continuation with some return value
                   // if we don't call it, the program would stop
                   // abruptly after a print!
});

// run the evaluator
evaluate(ast, globalEnv, function(result){
  // the result of the entire program is now in "result"
});

Small test

Let's play with fib again:

But if we increase that to fib(27), we get a “stack overflow” error. Actually, the stack grows much faster now, so it turns out that this evaluator can only compute up to fib(12) (at least in my browser.. yours might vary). That's disappointing, but in the next page I'll show you how we can workaround it.