如何用JavaScript实现一门编程语言 - 编译器示例及改进

[llwanghong]

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

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

示例

接下来的示例将解析源代码、转换为CPS形式并生成最终的JavaScript代码。你可以看到λanguage语言是如何正确地转换为CPS形式的JavaScript代码。输出代码的缩进等是借助UglifyJS完成的（查看页面源码可以发现这些示例实际上是浏览器生成的）。可以通过下面的代码来完成转换：

var ast = parse(TokenStream(InputStream(code)));
var cps = to_cps(ast, function(x){ return x });
var out = make_js(cps);

// get beautified output:
out = UglifyJS.parse(out).print_to_string({ beautify: true });

我们传给to_cps的“toplevel continuation”会原样返回传入的AST节点。

下面示例中你将发现return关键字是无意义的，跟CPS求值器中的效果一样，函数都不会return，相反会将结果传入continuation调用进行后续的计算。

函数调用

可以看到每个函数调用中是如何将包裹了程序后续行为的continuation作为第一个参数插入的。

表达式序列 (prog)

条件（Conditionals）

注意下面两个 if 示例是如何完全一样地完成了编译。这很有趣并也预示着一个问题。

下面示例展示连续多个 if 会编译成什么：

函数（lambda）

还有一点，输出代码中传给add的continuation的作用就是传入结果并调用dup的continuation — β_K(β_R)。所以整个函数可以直接替换为 β_K：

dup = function(β_K_1, x) {
  return add(β_K_1, x, x);
};

这是一个应该完成的重要且简单的优化。

Let

fib函数

仅为了展示一个更有意义的程序示例：

结论

为了得到一个不错的语言我们还需要修复一些问题。在此之上，我们会重新回归考虑递归限制的问题 — 我们将直接复用CPS求值器中构建的基础结构：Execute，Continuation和GUARD，所以修复相当容易。下一节我们将直接在CPS转换器以及JS代码生成器中修复一系列问题。

改进

下面我们将会对CPS转换器及代码生成器做一些轻微的修改。

prog节点

我们从一个简单的函数开始，cps_prog — 想法就是当第一个表达式没有副作用时，没有必要再将其输出。下面的帮助函数将决定一个AST节点是否会产生副作用。该函数并不完美；这里的金科玉律就是小心为上。如果确定不了，就认为是有副作用的。

例如，判断assign或call节点是否有副作用并不容易。变量定义中的赋值操作会产生副作用，但如果定义的变量从未使用或立即被重新赋值，则都可以丢弃。另一方面，如果被调用的函数是“纯函数”，则函数调用也可能没有副作用，但没有简单的方式来证明这一点。既然不容易确保是否有副作用，就认为它们都有副作用。

function has_side_effects(exp) {
    switch (exp.type) {
      case "call":
      case "assign":
        return true;

      case "num":
      case "str":
      case "bool":
      case "var":
      case "lambda":
        return false;

      case "binary":
        return has_side_effects(exp.left)
            || has_side_effects(exp.right);

      case "if":
        return has_side_effects(exp.cond)
            || has_side_effects(exp.then)
            || (exp.else && has_side_effects(exp.else));

      case "let":
        for (var i = 0; i < exp.vars.length; ++i) {
            var v = exp.vars[i];
            if (v.def && has_side_effects(v.def))
                return true;
        }
        return has_side_effects(exp.body);

      case "prog":
        for (var i = 0; i < exp.prog.length; ++i)
            if (has_side_effects(exp.prog[i]))
                return true;
        return false;
    }
    return true;
}

期望上面的函数已经足够清晰而不需要进一步解释。有了这个函数，cps_prog变成下面这样：

function cps_prog(exp, k) {
    return (function loop(body){
        if (body.length == 0) return k(FALSE);
        if (body.length == 1) return cps(body[0], k);
        if (!has_side_effects(body[0]))
            return loop(body.slice(1));
        return cps(body[0], function(first){
            if (has_side_effects(first)) return {
                type: "prog",
                prog: [ first, loop(body.slice(1)) ]
            };
            return loop(body.slice(1));
        });
    })(exp.prog);
}

所以，对于前两种情况的处理跟之前相同：如果表达式序列为空则返回false，如果只有一个表达式则进行编译因为我们需要其编译结果。但如果至少有两个表达式时，会进一步校验：能否在编译时确定第一个表达式没有副作用？如果确定没有则将其丢弃—甚至不会编译它—直接对剩余部分进行编译。如果有副作用，还会在其continuation中进一步校验其结果是否有副作用（因为结果可能仅是一个普通变量），并仅当有副作用时才会包含其结果。

if节点

之前的cps_if中各分支都进行编译，导致连续的if语句会增加大量的代码输出。一种修复方法（代价相当大）是将程序剩余部分包裹到一个continuation里，我们将if节点转换为接收一个continuation参数的IIFE表达式。IIFE函数体将使用if表达式的编译结果来调用continuation。

下面是一个采用上面方案的 λ 到 λ 转化示例：

上面的转换确实会增加一些开销，但至少代码增长是线性而不是指数型的（比如，你不会在输出中看到两个print(a)）。

下面是更新后的 cps_if：

function cps_if(exp, k) {
    return cps(exp.cond, function(cond){
        var cvar = gensym("I");
        var cast = make_continuation(k);
        k = function(ifresult) {
            return {
                type: "call",
                func: { type: "var", value: cvar },
                args: [ ifresult ]
            };
        };
        return {
            type: "call",
            func: {
                type: "lambda",
                vars: [ cvar ],
                body: {
                    type: "if",
                    cond: cond,
                    then: cps(exp.then, k),
                    else: cps(exp.else || FALSE, k)
                }
            },
            args: [ cast ]
        };
    });
}

我们不得不为continuation起一个名字（cvar）。将程序剩余部分编译为cast的continuation后，我们将k赋值为一个会调用cast（可通过cvar引用到）的call节点，并会将if表达式（then和else分支）的编译结果传给cast进行调用。就是目前传给各分支中的k。

增加堆栈保护并丢弃return

为了实现这个功能需要对代码生成器做一点小改动。更新后的js_lambda如下：

function js_lambda(exp) {
    var code = "(function ";
    var CC = exp.name || "β_CC";
    code += make_var(CC);
    code += "(" + exp.vars.map(make_var).join(", ") + ")";
    code += "{ GUARD(arguments, " + CC + "); " + js(exp.body) + " })";
    return code;
}

如果编译的函数没有命名，则默认函数名为"β_CC"，所以可以将其传给GUARD。我翻转了GUARD的参数，因为它们会增加很多输出（可以看到虽然删除了return语句，但同时需要增加这些guard语句）— 并提供一个更长的常量字符串使得输出代码能够在使用gzip后得到更好的压缩。

经过这些“改进”，fib函数的输出看起来很“混乱”：

试着运行一下：

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

根据我的测试，看起来比最初一版求值器实现快了6倍，比CPS求值器快了30倍。同时也比手写的JS慢了大概30倍。导致其慢的原因，除了引入CPS转换的开销，还有就是堆栈保护。遗憾的是没有方法还规避这些开销。如果JS代码生成器中放弃了使用GUARD，上面的例子将会堆栈溢出。

另一方面开销增加来自于if节点的处理方式。对于上面的例子完全没有必要，因为if表达式是函数中的最后一项（它的continuation就是调用fib函数的continuation）。

下一章节我们将写一个优化器来进一步改善输出代码的质量。