如何用JavaScript实现一门编程语言 - 保护堆栈

[llwanghong]

整篇译文的目录章节如下：

• 前言
• λanguage描述
• 写一个解析器（Parser）
  • 字符流（Character Stream）
  • 标记流（Token Stream）
  • AST
  • 解析器
• 简单的解释器（Interpreter）
  • 我们得到了什么
  • 增加新的结构
  • 我们有多快？
• CPS求值器（CPS Evaluator）
  • 保护堆栈
  • Continuations
  • Yield进阶
• 编译成JS
  • JS代码生成器
  • CPS转换器
  • 示例及改进
  • 优化器
• 总结
• 真实示例

保护堆栈

CPS求值器中堆栈消耗得更快，因为它持续调用其它函数来推进程序流并且一直没有返回。不要太相信return语句—它们很必要，但在递归非常深的情况下，可能还没等执行到它们就堆栈溢出报错了。

想象一个非常简单程序的堆栈会是什么样子。下面展示了相应的伪代码，其中没包括env是因为对展示堆栈深度不重要。

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.

只有当最后一个continuation（K0）执行完之后才会轮到一系列无助的return来释放堆栈。对一个如此简单的程序都嵌套这样深，可以想象fib(13)是如何快速地把堆栈空间消耗光的。

堆栈守卫（stack guard）

我们新写的求值器中，堆栈简直就是垃圾。程序每一步后续的计算都需要包裹在传入的回调函数中。所以这也带出一个问题：如果JavaScript能够提供某种方式重置堆栈会怎样？那么我们就可以不时地这样操作，就像某种垃圾回收机制一样，这样深层递归也可以工作。

假设我们有一个GUARD函数可以完成这种重置。它接收两个参数：一个将要调用的函数和一个将要传给它的参数数组。它会检查堆栈，如果嵌套太深则会重置堆栈，然后再调用传入的函数；否则什么都不会做。

使用该函数重写后的求值器如下。因为跟之前代码一样，所以不会解释每种情况；唯一的修改就是在每个函数最前面增加了GUARD函数。

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);
          if (exp.operator === '&&') {
            if (left === false) {
              callback(left);
            } else {
              evaluate(exp.right, env, function CC(right) {
                GUARD(CC, arguments);
                callback(right);
              });
            }
          } else if (exp.operator === '||') {
            if (left) {
              callback(left);
            } else {
              evaluate(exp.right, env, function CC(right) {
                GUARD(CC, arguments);
                callback(right);
              });
            }
          } else {
            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);
    }
}

为了可以引用到匿名函数，需要给它们声明一个名字。我使用了CC（代表“current continuation”）。 或者另外一种方法使用arguments.callee，但我们还是不要用废弃的API了。

同样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;
}

GUARD的实现真的非常简单。如何做到从一个深层嵌套调用里立即退出？— 使用异常。所以我们维护了一个限制堆栈最大嵌套层级的全局变量，当达到了这个限制，则抛出异常。我们抛出一个Continuation对象，该对象持有后续计算的信息 — 将要调用的函数及其参数：

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

最后需要设置一个循环来捕获Continuation对象。我们还必须借助循环来执行求值器进而使整体方案运作起来。

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接收一个将要运行的函数f及其参数args。函数f最终是在循环中执行，但请注意这里的return—如果执行期间没发生异常，最终程序就会在此结束。STACKLEN会在每次循环开始时被初始化。我发现200是一个合适的值。当捕获到了一个Continuation对象，函数f及其参数args会被恢复为Continuation对象中保存的值，然后继续执行循环。堆栈此时会因异常而被清理，所以又可以继续嵌套执行了。

我们可以像下面这样使用Execute来运行求值器：

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

测试

fib函数不会再失败了：

fib = λ(n) if n < 2 then n else fib(n - 1) + fib(n - 2);
time( λ() println(fib(20)) );

可惜尝试fib(27)则会发现其执行时间要比第一版（非CPS）求值器大概慢4倍。但至少可以无限递归下去，如下面例子所示：

sum = λ(n, ret)
        if n == 0 then ret
                  else sum(n - 1, ret + n);

# compute 1 + 2 + ... + 50000
time( λ() println(sum(50000, 0)) );

我们的语言事实上要比JavaScript慢很多！设想一下每个变量都必须通过环境对象来查询。尝试优化解释器已经没有意义了 — 没有更多优化空间了。获取更快速度的办法只有将λanguage语言编译成原生JS，这也是我们即将要做的。但首先我们来看一些CPS求值器带来的有趣结果。