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

[llwanghong]

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

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

Continuations

至此我们通过CPS（continuation passing style）形式实现了求值器，其中所有函数，无论是λanguage语言定义的，或是JavaScript提供的原始功能函数，第一个参数都是一个将接收求值结果进行调用的回调函数（这个回调函数参数，对于原始功能函数是显式传递的，对于λanguage语言中定义的函数是不可见的，换句话是求值器隐式插入的）。

这个回调函数参数代表了程序所有的未来行为。下一步要做什么的完整描述。我们称其为“the current continuation”，并在代码中使用名字k来指代它。

有一点值得一提，如果我们永远不调用该回调函数即该continuation，程序就暂停了。我们在λanguage语言中还做不到这点，因为make_lambda创建的函数总会调用它们的continuation。但我们可以在原始功能函数中实现这个能力。我引入下面这个原始功能函数来展示如何实现：

globalEnv.def("halt", function(k){});

这个函数什么都没有做。它接收了一个continuation参数（k）但没有调用它。

println("foo");
halt();
println("bar");

如果删除halt()，就会输出“foo / bar / ***Result: false”（因为最后一个println返回 false）。但存在halt()时，输出只有“foo”。这种情况下甚至没有结果，因为halt()没有调用continuation — 所以我们传给evaluate的回调，即打印***Result结果的函数, 没有执行到。调用函数却永远不知道程序已经暂停了。如果你用的是NodeJS，你很可能已经搬石头砸了自己的脚。

比如说我们想要写一个sleep函数，能够推延程序执行但是不会冻结住浏览器（即没有死循环）。我们可以简单地将其实现为一个原始功能函数:

globalEnv.def("sleep", function(k, milliseconds){
  setTimeout(function(){
    Execute(k, [ false ]); // continuations expect a value, pass false
  }, milliseconds);
});

不方便的一点就是我们不得不使用Execute，因为setTimeout将会丢弃当前的执行堆栈。直接调用k(false)的话，代码不会被捕获Continuation异常的循环包裹，第一次发生Continuation异常的时候，程序就会失败。下面是我们如何使用它（多次运行可以发现调用都是并行执行的）：

译者：上一节堆栈保护中提到CPS形式更新后的λanguage语言程序的整体执行方案，在Execute内部会设置一个循环保证λanguage语言程序的执行，程序各个Continuation的衔接，是通过将Continuation作为特殊异常抛出，然后循环里捕获到这个异常，会进行Continuaion的衔接设置，达到重置堆栈效果的同时，能保证继续执行后续代码。如果直接调用k(false)，则第一次Continuation异常抛出后没有相应的处理机制，程序会直接失败。

let loop (n = 0) {
  if n < 10 {
    println(n);
    sleep(250);
    loop(n + 1);
  }
};
println("And we're done");

这是原生JavaScript做不到的，除非你手工用CPS形式重写代码（并且你不能使用 for 循环）：

(function loop(n){
  if (n < 10) {
    console.log(n);
    setTimeout(function(){
      loop(n + 1);
    }, 250);
  } else {
    println("And we're done"); // rest of the program goes here.
  }
})(0);

设想有一些基于NodeJS文件系统API封装实现的原始功能函数，比如：

globalEnv.def("readFile", function(k, filename){
  fs.readFile(filename, function(err, data){
    // error handling is a bit more complex, ignoring for now
    Execute(k, [ data ]); // hope it's clear why we need the Execute
  });
});
globalEnv.def("writeFile", function(k, filename, data){
  fs.writeFile(filename, data, function(err){
    Execute(k, [ false ]);
  });
});

基于上面的定义，我们可以做下面的事情：

copyFile = λ(source, dest) {
  writeFile(dest, readFile(source));
};
copyFile("foo.txt", "bar.txt");

并且是异步的。没有回调地狱。

下面是一个更令人费解的例子。我写了下面的原始功能函数：

globalEnv.def("twice", function(k, a, b){
  k(a);
  k(b);
});

它接收两个参数a和b，然后针对每个参数共调用continuation两次。运行一个示例：

println(2 + twice(3, 4));
println("Done");

// output
// 5
// Done
// ***Result: false
// 6
// Done
// ***Result: false

如果你之前从没接触过continuation，会觉得输出比较奇怪，我还是把这个疑问留给你自己来思考。一个简短的提示：程序运行一次程序，会给调用者返回两次！

CallCC

目前为止，我们都是通过在JS中写原始功能函数来达到目的。λanguage语言中还没有一种方式能拦截当前的执行。CallCC弥补了这个能力空缺。这个名字是Scheme中call-with-current-continuation的简称（Scheme中也常常拼写为call/cc）。

globalEnv.def("CallCC", function(k, f){
    f(k, function CC(discarded, ret){
        k(ret);
    });
});

它将当前continuation具象化为一个可以直接在λanguage语言中调用的函数。这个函数会忽略它自己的continuation （discarded参数）并调用CallCC的continuation。

有了它，我们可以实现许多之前不敢想的操作符（直接通过λanguage语言自身实现，而不是通过JS原始功能函数的方式！），从exceptions到return。我们首先开始实现return。

return实现

foo = λ(return){
  println("foo");
  return("DONE");
  println("bar");
};
CallCC(foo);

foo函数接收了一个参数，其有效地充当了JS的return语句（ 仅有一点是需要像一个函数一样调用，因为它本质上就是一个函数）。它会丢弃后续的执行（原本会打印“bar”）并提前以传入的返回值（"DONE"）结束函数。当然，仅在将foo传给CallCC，进而return参数可以被赋值为continuation，这样才能按上述预期执行。我们可以提供一层封装：

with-return = λ(f) λ() CallCC(f);

foo = with-return(λ(return){
  println("foo");
  return("DONE");
  println("bar");
});

foo();

上面的优势就是我们目前调用foo时不再需要用CallCC。当然，如果可以不用将return命名为一个函数参数，或者说可以直接使用with-return（译者理解即支持一个return关键字），这将会更好，但是λanguage语言还不允许做语法扩展，至少需要修改解析器才能做到（Lisp语言同样如此）。

简单回溯Easy backtracking

假设我们想实现一个程序，能够找出100以内两个正整数乘积为84的所有数对。这个问题不难，你可能会尝试用两层嵌套循环来解决它，但这里我们会尝试另外一种方法。我们会实现guess和fail两个函数。guess函数将会选一个数字，fail函数反馈需要“尝试其它数字”。我们将会像下面这样使用它们：

a = guess(1);  # returns some number >= 1
b = guess(a);  # returns some number >= a
if a * b == 84 {
  # we have a solution:
  print(a); print(" x "); println(b);
};
fail();  # go back to the last `guess` and try another value

fail = λ() false;
guess = λ(current) {
  CallCC(λ(k){
    let (prevFail = fail) {
      fail = λ(){
        current = current + 1;
        if current > 100 {
          fail = prevFail;
          fail();
        } else {
          k(current);
        };
      };
      k(current);
    };
  });
};

a = guess(1);
b = guess(a);
if a * b == 84 {
  print(a); print(" x "); println(b);
};
fail();

注意到当a大于84的平方根，或当b大于84/a，继续执行没有意义，可以基于此进一步优化上面的程序。我们可以让guess接收两个参数，start和end，并只在这个范围内取出一个正整数。但针对这个例子我们就此打住，还是继续来看continuations。

ES6 yield

EcmaScript 6将会引入一个神奇的yield操作符，使用之前版本的JavaScript无法实现这个语义，除非将代码整体调整为CPS形式。在λanguage语言中，显式continuation给我们提供了一种方法来实现yield。

但实现yield并不是什么轻松的事情。比我之前预想的要有更多的细节，所以将yield的讨论单独移到了下一章节。这是个进阶话题，对于理解本教程剩余内容不是必须的，但如果想对continuation有更深入的理解，推荐你阅读一下。

Common Lisp中的catch和throw

我们将会实现两种语法结构，catch和throw。可以像下面这样使用：

f1 = λ() {
  throw("foo", "EXIT");
  print("not reached");
};
println(catch("foo", λ() {
  f1();
  print("not reached");
}));  # prints EXIT

解释一下，catch(TAG, function)将定义一个捕获TAG类型异常的hook，然后调用function函数。throw(TAG, value)将跳转到嵌套层级中最近的可以捕获TAG类型异常的catch，然后返回value。 无论catch函数是正常结束或是通过throw结束，hook都会在catch函数结束前被释放掉。

下面简要描述了一种实现。

## with no catch handlers, throw just prints an error.
## even better would be to provide an `error` primitive
## which throws a JavaScript exception. but I'll skip that.
throw = λ(){
  println("ERROR: No more catch handlers!");
  halt();
};

catch = λ(tag, func){
  CallCC(λ(k){
    let (rethrow = throw, ret) {
      ## install a new handler that catches the given tag.
      throw = λ(t, val) {
        throw = rethrow;  # either way, restore the saved handler
        if t == tag then k(val)
                    else throw(t, val);
      };
      ## then call our function and store the result
      ret = func();
      ## if our function returned normally (not via a throw)
      ## then we will get here.  restore the old handler.
      throw = rethrow; # XXX
      ## and return the result.
      ret;
    };
  });
};

可以按如下方式测试：

throw = λ(){
  println("ERROR: No more catch handlers!");
  halt();
};

catch = λ(tag, func){
  CallCC(λ(k){
    let (rethrow = throw, ret) {
      ## install a new handler that catches the given tag.
      throw = λ(t, val) {
        throw = rethrow;
        if t == tag then k(val)
                    else throw(t, val);
      };
      ## then call our function and store the result
      ret = func();
      ## if our function returned normally (not via a throw)
      ## then we will get here.  restore the old handler.
      throw = rethrow;  # XXX
      ## and return the result.
      ret;
    };
  });
};

f1 = λ() {
  throw("foo", "EXIT");
  print("not reached");
};
println(catch("foo", λ() {
  f1();
  print("not reached");
}));

原力黑暗面（The Dark Side of the Force）

上面对catch的描述中，曾提到hook会在catch函数结束前被释放掉。查看代码似乎确实是这样，但CallCC有能力来规避这个行为。哲学上会有两种观点。我完全赞成“权力属于人民”—允许用户有一些颠覆行为或许不是一个坏主意。但对于目前这种特殊情况，如果catch/throw的行为跟用户预期不一致，会给用户带来更多的困惑而不是帮助。

不按常规出牌很简单。你可以调用一个在catch外部存储的contiunation。catch中throw则不会被重置为先前存储的throw处理函数，因为catch甚至无法知道已经退出了当前代码块。例如：

exit = false;  # create a global.
x = 0; # guard: don't loop endlessly when calling exit() below
CallCC( λ(k) exit = k );
## exit() will restart from here...
if x == 0 then catch("foo", λ(){
  println("in catch");
  x = 1; # guard up
  exit();
});
println("After catch");
throw("foo", "FOO");

上面代码输出两次"After catch"，之后输出"ERROR: No more catch handlers!"。正确的行为是只输出一次"After catch"，然后输出ERROR。但通过catch外部保存continuation的方式退出函数，catch定义中恢复throw处理函数的逻辑（即上面catch定义代码中标记“XXX”的一行）永远不会执行到，所以旧throw处理函数得不到恢复，catch下面的throw就简单直接跳回catch内部最初定义的hook。

为了能正确的实现exceptions需要delimited continuations。将会在yield实现章节中进行讨论。

这也是众多反对CallCC的争议之一（强调一点：主要是反对CallCC中提供的undelimited continuations）。我还是很喜欢CallCC，如果undelimited continuations能在语言底层被支持并且CallCC不将它们暴露为一等公民，相信这样会更好。另外，我确实发现continuations很令人着迷，如果能很好的理解它，对于实践中实现很多其它有用的数据结构会至关重要。

接下来我们开始实现编译器 — 让程序运转得更快!