如何用JavaScript实现一门编程语言 - 总结

[llwanghong]

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

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

总结

为了能真正完成本教程，我又进一步给λanguage增加了一些特性实现和修复（非核心的，但有了更好），但这里并没有给出具体描述。下面可以下载到完整的代码。

下载 lambda.js

可以通过NodeJS运行程序。从标准输入STDIN读取λanguage源程序并编译执行。会从标准错误输出编译结果，并在标准输出给出程序执行结果。使用示例：

cat primitives.lambda program.lambda | node lambda.js

最终的改动点如下：

• 支持求反运算符（!）。它之所以非核心是因为可以简单地通过一个函数实现：

not = λ(x) if x then false else true;
not(1 < 0)        # ⇒ true

然后，给它分配一个专用AST节点进而可以生成更高效的代码（一个函数调用意味着需要GURAD或诸如此类的）。

• 增加了一个 js:raw 关键字。通过它可以在输出中插入任意JavaScript代码（仅仅指完整的表达式，而非语句）。使用示例是很容易在λanguage语言中定义原始功能函数：

length = js:raw "function(k, thing){
  k(thing.length);
}";
​
arrayRef = js:raw "function(k, array, index){
  k(array[index]);
}";
​
arraySet = js:raw "function(k, array, index, newValue){
  k(array[index] = newValue);
}";
​
array = js:raw "function(k){
  k([].slice.call(arguments, 1));
}";

我的语法高亮配置给这个关键字使用了一个红色，因为它是危险的。可能不是太危险，但你需要知道使用它意味着什么：你传给 js:raw 的代码不会被校验并将原封不动地输出到JS中。例如下面代码中，优化器不能判断你访问了局部变量，并会将 x = 10 丢弃：

这不是一个bug。是意料之中会发生的。

• 为布尔表达式生成更好的代码 — make_js，像我们写得那样，可能很容易输出类似代码 (a < 0 ? true : false) !== false，但明显可以简化成 a < 0。这可能不会提升速度，但至少看起来不会那么傻。

• 修复 && 和 || 运算符的语义使得 false 是λanguage中唯一的假值。

• 为全局变量生成 var 声明并基于严格模式"use strict"对最终输出代码进行求值（严格模式下似乎会有大概 5-10% 的速度提升）。

我们是否已经接近一门真实的编程语言了？

不论相信与否，λanguage相当接近Scheme语言了。我曾答应我们不是在实现一门Lisp，我遵守了诺言。但大部分工作已经完成了：我们有了一个不错的CPS转换器和优化器。如果想实现Scheme，剩下的就是写一个Scheme解析器来生成兼容的AST，以及一轮预编译来完成宏扩展。还有核心库的一堆原始功能函数。应该不会有太多的工作。

待增加特性

如果我们想针对λanguage语言有进一步的工作，下面是一些应该考虑的点。

变量名字

JavaScript生成器原样保留了变量的名字，但这通常并不是一个好主意（不用说这是一个bug，因为我们允许标识符名称中出现JavaScript认为非法的字符）。我们至少应该全局增加前缀并替换非法字符。我考虑的前缀是“λ_”。

可变参数列表

任何实用的语言都将需要像JavaScript arguments类似的支持。我们可以简单地通过增加一些语法来支持它，例如：

foo = λ(first, second, rest...) {
  ## rest here is an array with arguments after second
};

但等等，在λanguage语言中数组是什么？（下一小节list中会讲到）。

似乎有倾向认为我们已经可以使用“arguments”名字（因为JS中我们保持了相同的变量名字），但这不会正常工作：to_cps和优化器会认为其是一个全局变量，可能造成混乱。

在不牺牲太多代码大小的情况下实现上面的语法，我们可以使用GURAD函数。示例输出：

foo = function CC(first, second) {
  var rest = GUARD(arguments, CC, 2); // returns arguments starting at index 2
};

与这个特性相关，我们同样需要一个与Function.prototype.apply等价的特性。

数组和对象

可以很容易地将它们定义为原始功能函数，就像在上面 js:raw 中做得那样。然而，在语法层面实现它们将会生成更高效的代码，同时会赋予我们更熟悉的语法；a[0] = 1 毫无疑问要比 arraySet(a, 0, 1) 更友好。

我想避免的一件事就是歧义。例如，JavaScript中花括号用来表示代码块和字面量对象。规则就是“当左花括号处于语句的位置，则其为一个代码块；当处于一个表达式中时，就是一个对象字面量”。但λanguage中并没有语句（这也是一个特性）并且花括号意味着一个表达式序列。我希望保持这种状态，所以不会使用 { ... } 来表示一个对象字面量。

“点”符号

与前一条相关，我们应该支持通过点符号访问对象的属性。这种用法太普遍了，而不容忽视。

我期望像JavaScript那样支持“方法”是有挑战的（比如：支持 this 关键字）。原因是我们所有函数都会转换成CPS形式（所有函数调用都会将continuation作为第一个参数插入进来）。如果我们打算支持类似JS的方法，我们怎么判断是在调用一个CPS形式的函数（例如：λanguage语言写的）而不是一个普通函数（例如：来自某些JS库）？这点值得思考。

语法（分隔符）

要求prog节点中表达式必须以分号分隔有点太苛刻。例如：按目前的解析器规则，下面的程序是非法的：

if foo() {
  bar()
}                  # ← error
print("DONE")

问题出在井号#一行。即使以一个右花括号结束，紧接着它还应该有一个分号（因为if是一个表达式，并以一个右花括号结束）。如果之前使用过JavaScript，这并不很直观；可能更希望放松规则，并认为右花括号后面的分号是可选的。但又很棘手，因为下面的代码也是一个有效的程序：

a = {
  foo();
  bar();
  fib
}
(6);

上面代码的结果是调用foo()，bar()，并将 fib(6) 的结果赋值给变量a。多么滑稽的语法，但你知道吗，绝大多数中缀语言都有类似古怪的语法，比如下面代码是一个语法合法的JS程序；尝试运行并不会出现解析错误，但当你调用foo()时会发现有个明显的运行时错误：

function foo() {
  a = {
    foo: 1,
    bar: 2,
    baz: 3
  }
  (10);
}

异常

我们可以在reset和shift操作符或者其它原始功能函数基础上实现一个异常系统。

继续…

即使没有TODO中罗列的特性，λanguage语言已经相当强大，我将以一些样例来结束整篇教程，会对比在NodeJS和λanguage中如何来实现一些小程序。继续阅读。