Guarding the stack

In the CPS evaluator the stack is exhausted much quicker because the evaluator ever keeps calling other functions, and never returns. Do not be tricked by the return statements—they are necessary, but in the case of a very deep recursion they are never reached, because we get a stack overflow error instead.

Let's imagine how the stack looks for a very simple program. I'll show pseudo-code and I'm not including the env as it's not important for making this point

print(1 + 2 * 3);

## stack:
evaluate( print(1 + 2 * 3), K0 )
  evaluate( print, K1 )
    K1(print)  # it's a var, we fetch it from the environment
      evaluate( 1 + 2 * 3, K2 )
        evaluate( 2 * 3, K3 )
          evaluate( 2, K4 )
            K4(2)  # 2 is constant so call the continuation with it
              evaluate( 3, K5 )  # same for 3, but we're still nesting
                K5(3)
                  K3(6)  # the result of 2*3
                    evaluate( 1, K6 )  # again, constant
                      K6(1)
                        K2(7)  # the result of 1+2*3
                          print(K0, 7)  # finally get to call print
                            K0(false)  # original continuation. print returns false.

Only after the last continuation runs (K0) will a long sequence of pointless return-s rewind the stack. If we nest so much even for a trivial program, it's easy to imagine how fib(13) runs out of stack space.

A stack guard

The way we wrote the new evaluator, the stack is simply garbage. All the computation that needs to happen after each step is enclosed in the callback, which is passed as an argument. So this begs the question: what if JavaScript would provide some way to reset the stack? Then we could do it every now and then, like some kind of garbage collection, and deep recursion will work.

Let's assume we have a GUARD function which can do that. It receives two values: a function to call and an array of arguments to pass to it. It checks if the stack is too nested, and if so, it'll reset the stack and call that function thereafter. Otherwise it does nothing.

Using this function we'll rewrite our evaluator as follows. I will not comment on each case because it's the same code as before; the only addition is GUARD-ing every single function, before doing anything else.

function evaluate(exp, env, callback) {
    GUARD(evaluate, arguments);
    switch (exp.type) {
      case "num":
      case "str":
      case "bool":
        callback(exp.value);
        return;

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

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

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

      case "let":
        (function loop(env, i){
            GUARD(loop, arguments);
            if (i < exp.vars.length) {
                var v = exp.vars[i];
                if (v.def) evaluate(v.def, env, function CC(value){
                    GUARD(CC, arguments);
                    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;

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

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

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

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

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

For anonymous functions I had to declare a name in order to refer to them. I used CC (stands for “current continuation”). An alternative would be arguments.callee but let's not use deprecated API.

Also, a similar one-line change in make_lambda:

function make_lambda(env, exp) {
    if (exp.name) {
        env = env.extend();
        env.def(exp.name, lambda);
    }
    function lambda(callback) {
        GUARD(lambda, arguments);  // <-- this
        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;
}

The implementation of GUARD is really simple. How do you exit abruptly from e deeply nested call? — using exceptions. So we'll maintain a global variable for the stack nesting limit and when it's too deep, throw. We throw a Continuation object which holds the future of the computation — a function to call and its arguments:

var STACKLEN;
function GUARD(f, args) {
    if (--STACKLEN < 0) throw new Continuation(f, args);
}
function Continuation(f, args) {
    this.f = f;
    this.args = args;
}

Finally, we need to setup a loop that will catch Continuation objects. We'll have to run our evaluator through that loop in order for the whole trick to work.

function Execute(f, args) {
    while (true) try {
        STACKLEN = 200;
        return f.apply(null, args);
    } catch(ex) {
        if (ex instanceof Continuation)
            f = ex.f, args = ex.args;
        else throw ex;
    }
}

Execute takes a function to run and arguments to pass it. It does that in a loop, but note the return—in the event the function runs without blowing the stack, we stop there. STACKLEN is initialized every time we resume the loop. I found 200 to be a good value. When a Continuation is caught, reinstate the new function and arguments and continue the loop. The stack is cleared at this point by the exception, so we can nest again.

To run our evaluator now with Execute, we do something like this:

Execute(evaluate, [ ast, globalEnv, function(result){
    console.log("*** Result:", result);
}]);

Test

Our fib function won't fail anymore:

Unfortunately, if you try fib(27) the execution time will be about about 4 times slower than with the first (non-CPS) version of the evaluator. But at least we have unlimited recursion, for example:

Our language is much slower than JavaScript indeed! Just imagine that every variable lookup has to go through our Environment object. Trying to optimize the interpreter is pointless—we won't get far. The solution for better speed is to compile λanguage to native JS, and that's what we'll do. But first let's see some interesting consequences of having a CPS evaluator.