如何用JavaScript实现一门编程语言 - CPS求值器（CPS Evaluator）

[llwanghong]

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

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

CPS求值器（CPS Evaluator）

作者原文提到的bug此译文中已修复，主要是指在解释器，CPS求值器及CPS编译器章节中：像 a() && b() 或者 a() || b() 的表达式两侧都会求值。这样处理是不对的，是否对 b() 求值依赖 a() 的求值结果。通过将 || 及 && 两个二元操作符的处理逻辑替换为 if 表达式来修复。

CPS求值器（CPS Evaluator）

我们的语言有两个问题：(1) 递归受限于JS的堆栈，所以没有有效的方式做遍历；(2) 很慢。我们这里先解决第一个问题，遗憾的是以语言变得更慢为代价。我们将以CPS（Continuation-Passing Style）形式来重写求值器。

什么是CPS？

在NodeJS中你总会如下操作：

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.
});

程序执行的每一步，你都需要调用回调函数才能得以持续执行。CPS使得程序控制流变得“清晰” — 你不用return，你不用throw，你不用break 或 continue。没有任意的跳转。你甚至不能直接将 for 或者 while 循环和异步函数组合使用。如果真是这样，为什么语言中还要有这些关键字？

手工写CPS形式的程序很不直观且易出错，但我们也不得不以这种方式来重写求值器。

求值函数（The evaluate function）

CPS形式的evaluate函数将接收三个参数：表达式exp（AST形式），环境env，以及接收结果的回调函数callback。下面是代码实现，我会像之前一样对每种情况进行解释：

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

对于常量节点，直接返回它们的值。但请记住，我们需要调用callback来传值，而不是return。

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

var节点的处理同样简单： 从环境中获取变量的值，并将其传给callback。

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

对于assign节点，我们首先需要对right表达式进行求值。直接调用evaluate并传入一个回调函数，回调函数中就可以获取到结果（即right表达式的求值）。然后设置变量并用设置结果（实际就是变量的值）来调用顶层的callback。

      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;

类似地，对于二元表达式binary节点，首先需要对left节点求值，然后对right节点求值，最后将两节点基于操作符运算后的结果传递给callback。和之前一样，我们递归调用evaluate并传入一个回调函数来继续执行后续步骤。

      case "binary":
        evaluate(exp.left, env, function(left){
          if (exp.operator === "&&") {
            if (left === false) {
              callback(left);
            } else {
              evaluate(exp.right, env, function(right){
                callback(right);
              });
            }
          } else if (exp.operator === "||") {
            if (left) {
              callback(left);
            } else {
              evaluate(exp.right, env, function(right){
                callback(right);
              });
            }
          } else {
            evaluate(exp.right, env, function(right){
              callback(apply_op(exp.operator, left, right));
            });
          }
        });
        return;

let节点看起来要更复杂一点，但实际上非常简单。 我们有许多变量定义，它们可能不包含def（初始值）属性，此时默认会初始值为 false；当该属性存在时，则需要递归调用evaluate函数对其求值。

如果你用过NodeJS，你可能已经解决过很多类似的问题。由于使用了回调，我们不能直接使用for，而是需要一个接一个逐个计算表达式（想象一下evaluate函数可能不是立即返回，而是异步的）。下面的循环函数（立即调用的）接收环境对象env及当前变量定义索引i来进行计算。

如果i等于vars.length则意味着计算结束并且环境中已经有了所有变量定义（defs），此时再来执行evaluate(exp.body, env, callback)。需要注意这次我们没有直接来调用callback，而是将其传给evaluate函数作为exp.body执行之后的延续，即其将负责继续执行后续工作。

否则i小于vars.length的情况，则会用evaluate求值当前的定义，并传入一个回调函数用刚求值的变量定义来扩展环境，然后进行下一次循环loop(scope, i + 1)。

      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;

我们再次使用了一个独立的函数来处理lambda节点，下面我会进行介绍。

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

对于if节点的执行，首先要对条件求值。如果求值不是 false 则对 then 分支求值，否则进一步判断 else 分支，如果其存在则求值，否则给callback传入 false。在then/else分支处理中可以再次注意到，我们同样没有调用callbcak，而是将其传给了evaluate，负责起表达式计算后续的工作。

      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;

prog节点的处理类似let节点，但会更简单因为不需要定义变量并扩展环境。两种节点都有相同的处理模式：使用一个loop函数处理索引i。当i与prog.length相等时，则求值结束，直接返回最后一个表达式的求值结果（当然这里的返回，还是通过调用callback并传值的方式）。可以注意到我们是通过将last传给loop的方式来获取它的值（prog.body为空的情况，last初始值为false）。

      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;

对于call节点，我们需要先后对func和arguments求值。同let和prog节点一样，再次使用了一个loop函数来类似地处理它们，只不过这次会将结果构造成一个数组。数组的第一个值必须是callback，因为make_lambda返回的闭包函数也都是CPS形式的，所以它们都是通过调用回调并传结果而不是使用return。

      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;

和之前一样的收尾，如果我们不知道如何继续，则抛出一个错误。

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

你可能注意到上面每个case分支都以一个return结束。 但没有返回值；结果都传给了callback。如果有可能，我们期望执行永远不会返回case分支；但这就是JS的工作方式。我们需要return语句来确保不会进入到下一个分支。

新make_lambda

在这个版本的求值器中，所有函数接收的第一个参数都是“continuation” — 一个将被传入结果并调用的回调函数。求值器总会插入这个参数，紧接着是运行时传入的其它参数。下面是新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;
}

仅仅做了略微的改动。使用新变量绑定（参数arguments产生的）来扩展环境。同时需要考虑第一个参数是callback（arguments使用了i + 1索引的原因）。最终像之前一样，在新环境作用域下通过evaluate对函数体求值，但是需要传入callback而不是直接返回结果。

顺便需要注意这里是唯一使用for进行循环的地方。因为当call节点求值时所有参数都已经计算出来了—不需要再对每个参数求值并传入一个回调函数来获取参数值。

原始功能函数（Primitives）

对于CPS求值器，原始功能函数均会将callback作为第一个参数。定义原始功能函数时我们必须记住这一点。下面是针对新版本的一些简单测试代码：

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"
});

小测试

我们再次使用fib函数：

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

如果增加n至fib(27)，我们将得到一个“堆栈溢出”错误。事实上，目前堆栈会增长的更快，所以当前的求值器最多只能计算到fib(12)（至少在我的浏览器上是这样，你们的可能会有变动）。非常令人失望，下一节会展示如何规避这个问题。