如何用JavaScript实现一门编程语言 - JS代码生成器

[llwanghong]

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

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

编译成JS

为了λanguage语言能更有效率，应将其转换成以JavaScript目标语言实现的程序，而不是直接对AST解析求值。接着我们通过 eval 或 new Function （或用一个 <script> 标签加载) 来运行它，我向你保证速度提升一定会非常显著。我将这个转换工作分成三个部分：

• JS代码生成器（code generator）
• 转换为CPS形式
• 优化

以代码生成部分开始讲解看起来可能会有点奇怪，直觉上它应该是“最后阶段”。之所以这样安排是因为代码生成会有助于实现和调试后续的部分。后续部分实现后也仅需要对代码生成器做小的调整即可。

JS代码生成器（code generator）

从AST生成JS代码非常简单。参照我们最初一版求值器的结构，make_js是一个接收AST的递归函数。这里环境对象的用处不大，因为这次我们不会执行AST，而是将其转化为等价功能的JavaScript代码，并以字符串形式返回。

代码入口看起来像下面这样：

function make_js(exp) {
    return js(exp);

    function js(exp) {
        switch (exp.type) {
          case "num"    :
          case "str"    :
          case "bool"   : return js_atom   (exp);
          case "var"    : return js_var    (exp);
          case "binary" : return js_binary (exp);
          case "assign" : return js_assign (exp);
          case "let"    : return js_let    (exp);
          case "lambda" : return js_lambda (exp);
          case "if"     : return js_if     (exp);
          case "prog"   : return js_prog   (exp);
          case "call"   : return js_call   (exp);
          default:
            throw new Error("Dunno how to make_js for " + JSON.stringify(exp));
        }
    }

    // NOTE, all the functions below will be embedded here.
}

js函数基于当前节点的类型进行调度，直接调用相应的生成器。

function js_atom(exp) {
    return JSON.stringify(exp.value); // cheating ;-)
}

目前而言，我们将原样输出变量名，这并不完全正确：λanguage语言中允许变量名中包含负号字符，但这在JS中并不合法。为了后面能更容易解决这个问题，所有变量名都会经过一个make_var函数处理，这样后面就可以统一一处修改：

function make_var(name) {
    return name;
}
function js_var(exp) {
    return make_var(exp.value);
}

对于二元运算符，分别编译左、右操作数，并用操作符进行拼接即可。需要注意的是我们最外层整体用括号进行了包裹，不用担心输出的美化—可以使用UglifyJS完成美化工作。

function js_binary(exp) {
    return "(" + js(exp.left) + exp.operator + js(exp.right) + ")";
}

仔细的读者会发现此处与求值器相比存在一些bug：求值器里会确保数字类型的操作符将接受恰当类型的操作数，并且不会发生除0的情况；同时&&和||的语义（关于falsy假值的认定）也与原生JS有些许的不同。我们后续再来关心这些问题。

// assign nodes are compiled the same as binary
function js_assign(exp) {
    return js_binary(exp);
}

lambda节点同样相当简单。就是输出一个JavaScript函数表达式。我们用括号包裹一下，避免可能的错误，输出function关键字，紧接着如果有函数名则输出函数名，然后是参数列表。函数体是一个单一的表达式，返回其结果。

function js_lambda(exp) {
    var code = "(function ";
    if (exp.name)
        code += make_var(exp.name);
    code += "(" + exp.vars.map(make_var).join(", ") + ") {";
    code += "return " + js(exp.body) + " })";
    return code;
}

使用立即执行函数IIFE来处理let节点。有点大材小用，我们可以做得更好，但目前不想耗费更多精力。用IIFE处理let节点非常简单：如果vars属性为空，则编译body属性。否则为第一个变量/定义创建一个IIFE节点（一个call节点），如果变量/定义为空则返回一个FALSE节点 — 最后编译IIFE节点。这叫做“脱糖desugaring”。

function js_let(exp) {
    if (exp.vars.length == 0)
        return js(exp.body);
    var iife = {
        type: "call",
        func: {
            type: "lambda",
            vars: [ exp.vars[0].name ],
            body: {
                type: "let",
                vars: exp.vars.slice(1),
                body: exp.body
            }
        },
        args: [ exp.vars[0].def || FALSE ]
    };
    return "(" + js(iife) + ")";
}

我们使用JavaScript的三目运算符来编译if节点。我们仍旧坚定λanguage语言中仅有false一个假值的事实（所以仅当条件不是false时才会执行then节点）。如果没有else节点，就默认编译一个FALSE节点。

与求值器不同，根据条件仅会执行then或else，这里两种分支必须都要遍历来生成代码 — 原因很明显，此时还不能知道条件的执行结果。

function js_if(exp) {
    return "("
        +      js(exp.cond) + " !== false"
        +      " ? " + js(exp.then)
        +      " : " + js(exp.else || FALSE)
        +  ")";
}

最后，prog和call — 非常简单的节点。对于prog节点，我们直接使用JavaScript中的逗号操作符即可。逗号操作符可以完美满足我们的诉求，对表达式序列顺序求值并返回最后一个表达式的求值。

function js_prog(exp) {
    return "(" + exp.prog.map(js).join(", ") + ")";
}
function js_call(exp) {
    return js(exp.func) + "(" + exp.args.map(js).join(", ") + ")";
}

上面就是代码生成器的全部！

原始功能函数和用法

这次生成的程序实际使用的是JavaScript变量，所以原生功能函数就是全局JS变量或函数。下面是一个基本的使用示例：

// the "print" primitive
window.print = function(txt) {
  console.log(txt);
};

// some test code here
var code = "sum = lambda(x, y) x + y; print(sum(2, 3));";

// get the AST
var ast = parse(TokenStream(InputStream(code)));

// get JS code
var code = make_js(ast);

// additionally, if you want to see the beautified JS code using UglifyJS
// (or possibly other tools such as acorn/esprima + escodegen):
console.log( UglifyJS.parse(code).print_to_string({ beautify: true }) );

// execute it
eval(code); // prints 5

后面你可以看到它的真实使用案例。

测试

还记得我们求值器的第一个版本（目前最快的版本）需要花费1S多时间来计算fib(27)？（大概比JS慢了300倍）。下面是其编译成JS的版本：

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

就和手写的JS代码一样块（译者多次尝试仅需要4～7ms，在线示例）。你可以从浏览器终端中看到生成的代码（console.log打印出来的）。

很可能我们想就此打住 — 因为已经“和JS一样快”了。但“和JS一样好”，同样并不足够好。没有了continuations，递归再次成为瓶颈。我们这里所做的最好也仅能称其为一个“转译器”。

编译器是将一门源语言转换成一门目标语言。例如，C++转换到汇编语言。或者λanguage到JavaScript。编译器真正做的不是代码生成，而是给源语言提供很多特性使其比目标语言更加强大。

接下来我们将继续把AST转化成CPS形式。