如何用JavaScript实现一门编程语言 - 我们有多快？

[llwanghong]

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

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

我们有多快？

简单回答：非常慢（dog slow）！

但来测试一下。我们将使用计算斐波那契数列的双递归函数，因为它不需要太多的栈空间但执行时间会随着 n 的规模增长曾现指数级增长。我们将会对比这个函数在普通JavaScript及λanguage语言下的执行时间。

我在当前环境定义了下面的原始功能函数；

globalEnv.def("fibJS", function fibJS(n){
  if (n < 2) return n;
  return fibJS(n - 1) + fibJS(n - 2);
});

globalEnv.def("time", function(fn){
  var t1 = Date.now();
  var ret = fn();
  var t2 = Date.now();
  println("Time: " + (t2 - t1) + "ms");
  return ret;
});

time接收一个函数，并会打印出该函数的执行时间。执行下面的程序：

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

print("fib(10): ");
time( λ() println(fib(10)) );
print("fibJS(10): ");
time( λ() println(fibJS(10)) );

println("---");

print("fib(20): ");
time( λ() println(fib(20)) );
print("fibJS(20): ");
time( λ() println(fibJS(20)) );

println("---");

print("fib(27): ");
time( λ() println(fib(27)) );
print("fibJS(27): ");
time( λ() println(fibJS(27)) );

在我的机器上，使用Google Chrome，最后的 n (27) ，λanguage语言执行超过了1秒，JavaScript却只用了4毫秒。显然这完全无法接受。

我们可以并将λanguage语言编译成JavaScript。为了弥补只能使用递归的情况，我们可以增加循环关键字（for / while），增加对象或数组等复杂数据结构，甚至异常 — 所有这些都可以被底层JavaScript语言所支撑。但这又有什么意义呢？JS同样有它的缺点，只是在它上面强加另一种语法不会给我们带来任何引以为豪的成就。

所以本教程中我投入了更多的思考，接下来将会介绍一个CPS（Continuation-Passing Style）求值器，会先后尝试 Continuations 以及一个与JavaScript同样有效率但拥有更强语义能力的编译器。

我们要试着做得比宿主语言（JavaScript）更好。速度很重要，但不是唯一的目标。