如何用JavaScript实现一门编程语言 - 增加新的结构

[llwanghong]

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

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

增加新的结构

我们语言的语法还是有点少见。例如没有办法定义新变量。正如之前提过的，我们需要使用一个立即执行函数IIFE，就像下面这样（有点无聊的例子，没想出更好的）：

(λ(x, y){
  (λ(z){ ## it gets worse when one of the vars depends on another
    print(x + y + z);
  })(x + y);
})(2, 3);

我们想增加一个 let 关键字从而可以像下面这样定义变量：

let (x = 2, y = 3, z = x + y) print(x + y + z);

每个变量的定义，都可以引用到前面定义的变量。let关键字可以被转换成下面的代码片段：

(λ(x){
  (λ(y){
    (λ(z){
      print(x + y + z);
    })(x + y);
  })(3);
})(2);

上面的转换可以直接在解析器中完成而不需要求值器的任何改动。我们可以直接将整个转换操作转变为 call 和 lambda 节点，而不需要增加一个专门的 let 节点。这意味着我们的语言没有增加任何语义 — 这被称为“语法糖”（syntactic sugar），其中转变为AST节点的操作就是熟知的“脱糖”（desugaring）。

既然无论怎样都要修改解析器，我们还是增加一个专用的 let 节点进而求值的效率可以更高（我们只需要扩展作用域，没有必要创建闭包并立即调用它们）。

我们会额外支持一种Scheme中很受欢迎的“命名let”（named let）语法。这样我们能以更简单的方式来定义循环表达式：

print(let loop (n = 10)
        if n > 0 then n + loop(n - 1)
                 else 0);

上面是一个计算 10 + 9 + ... + 0 累加和的递归循环。目前我们语言的能力只能按下面的方式实现：

print((λ(loop){
         loop = λ(n) if n > 0 then n + loop(n - 1)
                              else 0;
         loop(10);
       })());

为了能进一步简化，我们将增加命名函数（named functions）的概念。这样我们就可以按照下面的方式实现：

print((λ loop (n) if n > 0 then n + loop(n - 1)
                           else 0)
      (10));

总结一下，我们需要做的修改：

• lambda关键字后面支持一个可选的名字。如果指定了名字，则函数执行的环境必须定义这个名字并指向该函数。正如JavaScript中的命名函数表达式一样。
• 支持一个新的 let 关键字。紧接着关键字会有一个可选的名字及被圆括号包裹并由逗号分隔的变量定义列表（该列表也可能为空），其中变量定义形式如 foo = EXPRESSION。 let 关键字定义体是一个单一的表达式（显然也可以是{}包裹的表达式组）。

解析器更新（Parser changes）

首先，稍微改动一下分词器，需要将 let 加入到关键字列表中：

var keywords = " let if then else lambda λ true false ";

还需要更改解析器中的parse_lambda函数来支持可选的函数名字：

function parse_lambda() {
    return {
        type: "lambda",
        name: input.peek().type == "var" ? input.next().value : null, // this line
        vars: delimited("(", ")", ",", parse_varname),
        body: parse_expression()
    };
}

现在来定义 let 的解析：

function parse_let() {
    skip_kw("let");
    if (input.peek().type == "var") {
        var name = input.next().value;
        var defs = delimited("(", ")", ",", parse_vardef);
        return {
            type: "call",
            func: {
                type: "lambda",
                name: name,
                vars: defs.map(function(def){ return def.name }),
                body: parse_expression(),
            },
            args: defs.map(function(def){ return def.def || FALSE })
        };
    }
    return {
        type: "let",
        vars: delimited("(", ")", ",", parse_vardef),
        body: parse_expression(),
    };
}

上述函数处理了两种情况。如果紧接着 let 解析到了一个 var token，则其为“命名let”（named let）。其定义形式为被圆括号包裹并由逗号分隔，所以可以用 delimited 函数并传入parse_vardef（下文中定义了该工具函数）来解析该定义。接着返回一个调用命名函数表达式的 call 节点（即节点整体为一个IIFE）。命名函数的参数名字为 let 中定义的变量，call 节点会负责传递参数值。函数体则是通过 parse_expression() 解析完成。

如果不是“命名let”，则返回一个 let 节点，持有 vars 和 body 属性。vars 的结构为 { name: VARIABLE, def: AST }，会由下面函数从 let 定义列表中解析获得：

function parse_vardef() {
    var name = parse_varname(), def;
    if (is_op("=")) {
        input.next();
        def = parse_expression();
    }
    return { name: name, def: def };
}

我们还需要考虑在调度器（parse_atom）中解析到 let 关键字的情况，所以增加了下面一行代码：

// can be before the one handling parse_if
if (is_kw("let")) return parse_let();

求值器更新（Evaluator changes）

既然我们倾向于修改AST而不是进行“脱糖”操作（即直接转换为已有的AST节点），所以必须要更新求值器。

为了支持可选的函数名字，下面是更新后make_lambda函数：

function make_lambda(env, exp) {
    if (exp.name) {                               // these
        env = env.extend();                   // lines
        env.def(exp.name, lambda);    // are
    }                                                      // new
    function lambda() {
        var names = exp.vars;
        var scope = env.extend();
        for (var i = 0; i < names.length; ++i)
            scope.def(names[i], i < arguments.length ? arguments[i] : false);
        return evaluate(exp.body, scope);
    }
    return lambda;
}

如果有函数名字，则当闭包创建的时侯会立即扩展作用域，并定义该名字指向新创建的闭包。剩下的不变。

最终，为了支持 let AST节点，我们在求值函数中增加了下面的分支：

case "let":
  exp.vars.forEach(function(v){
      var scope = env.extend();
      scope.def(v.name, v.def ? evaluate(v.def, env) : false);
      env = scope;
  });
  return evaluate(exp.body, env);

注意每个定义的变量都需要扩展作用域，如果有初始化代码，则其求值结果会作为初始值，否则初始值为false。接着对let定义体进行求值。

测试

println(let loop (n = 100)
          if n > 0 then n + loop(n - 1)
                   else 0);

let (x = 2, y = x + 1, z = x + y)
  println(x + y + z);

# errors out, the vars are bound to the let body
# print(x + y + z);

let (x = 10) {
  let (x = x * 2, y = x * x) {
    println(x);  ## 20
    println(y);  ## 400
  };
  println(x);  ## 10
};

结论

λanguage语言整体都是我们自己实现的，所以上面的更新不会太难。但如果语言是其他人实现并且我们拿不到源码；更难的情况，如果是大家都已经安装的标准语言，并且需要遵从特定（严格）的语法？比如JavaScript语言。设想一下你需要给JavaScript增加一个新的语法结构 — 能做到吗？可能门都没有，即使你能将其提议给维护JS的那些大佬，提议也需要等待数年才会被考虑，接受，标准化然后广泛实现。在JavaScript中，我们就像囚徒一样（除非在JS基础上实现自己的语言）。

前面曾说过我将会讨论为什么Lisp是一门伟大的语言：Lisp中不需要改变解析器/求值器/编译器就能增加语法结构，这使得我们不需要将这些结构强加给所有语言用户，也不用花费数年来等待某些委员会采纳提议并由其他组织实现这些提议。Lisp即自由。如果Lisp没有命名函数或者 let 语法结构，我们就可以通过比上面更少的代码来增加实现，并且它们就跟其它内置语法结构一样。