【译】延续性究竟是什么？

发表于 5年以前 | 总阅读数：1364 次

原文：http://www.zcfy.cc/article/365

许多开发者听说过"延续性（continuation）"，知道它和解决 node.js 的"回调地狱"问题有关。但我不认为大多数人真正了解了什么是延续性。延续性并不只是一个个被异步调用的回调函数。

"延续性"指的是你的程序控制流在任意时间点上的表现形式。抽象地说，它表现当前时间点之后的你的程序的其余部分。在 Scheme 一类的语言中，延续性是一等公民（first-class values）（类比：JavaScript中，函数是一等公民 ---- 译者注），在这类语言中，你可以_捕获_当前的延续性然后在一段时间之后继续调用。继续调用的时候，当前的程序状态被替换成延续性被捕获时的状态（比如，当前的调用栈被替换成被捕获的延续性的调用栈）。

通过延续性，你的代码可以真正地"跳转"到不同地方。它们是底层的"原语操作"，能让你完全控制代码的执行流程，你通过它能实现任何你想实现的一切，不管是可恢复的异常还是协程。研究延续性是我作为一名年轻程序员做得最好的一件事，它强迫我去理解控制流是如何工作的。

如果 JavaScript 引擎能够实现_类似于_延续性的特性就好了，那样我们就可以基于它实现一切（注意我是说_类似于_延续性，因为真正的延续性对自身的优化非常困难）。我是一个底层原语操作的簇拥者，我支持它的理由如同 Extensible Web Manifesto 的观点，因为底层原语操作能够让开发者自己随着时间逐步进化所用的程序语言。

我最近成功实现了 JavaScript 语言的延续性。我是无心插柳。我本来只是在寻找一个方法，让我能够随时控制 JavaScript 暂停执行，这样我就能写 JavaScript 教程和可交互的编辑器。我意识到，要随意暂停 JS，等同于我需要实现"延续性"。我需要保存调用栈一段时间之后恢复执行。最后，我找到了一篇论文"Exceptional Continuations in JavaScript" ，它描述了如何实现延续性，能够达成我在浏览器里实现单步调试的目的。

在这篇文章的末尾部分，我更详细地介绍了这个项目产生的背景。我为这个项目耗费了几乎两年的时间，现在我终于将它打磨好可以发布了。

点击图片打开链接

一个单步调试器! 点击任何一行可以添加一个断点。

就这样，我意识到，我可以为这个特殊的 JS 虚拟机提供"延续性"作为一等公民（这里，Unwinder 可以看作一个 JS 虚拟机 ---- 译者注），这比我的单步调试工具更有意思。在这篇文章里，我会用我的单步调试器解释延续性是什么，并让你能够同它进行交互。

在下一篇文章中，我会详细解释我是怎么实现延续性的。在这里我简单说一下：我实现了一个虚拟机，将所有的代码转成状态机，然后通过抛异常来保存所有函数调用栈的状态。这样做意味着每一个函数都被转为一个非常大的 switch 语句，每一个表达式（语句）都对应成一个单独的 case 语句，这样做了之后，我就能够在代码的任意处跳转。

这个转换与 regenerator 非常类似，regenerator 将 ES6 的 generator 编译成 ES5 代码。事实上，我的项目也是受了 regenerator 项目的鼓舞。在两年前，我 fork 了 regenerator，从它的分支上实现了我想要的一切功能，从而产生了今天你所看到的这个项目。由于我 fork 的版本较早，所以它不支持最新的 ES6 特性，也错过了很多 bug 修复。.

访问 Unwinder 代码库来查看代码，可以自己动手尝试下。警告：目前的版本基本上只是一个原型，许多代码实现得很丑，很有可能可能你会遇到一些 bug。尽管如此，再经过一些打磨，这个项目就能让我们用 JS 来实现一些非常有趣的模式。

其他一些注意事项：

你不能单步调试到原生代码中去，你也不能在调用栈有原生代码的时候使用延续性。如果你使用数组原生的 forEach 方法，在 callback 里面拿到延续性，结果会出错。如果你要使用延续性，那么全部代码都必须要被转换器编译过（当然了，普通的代码能正常调用引擎原生的代码）。（这里的意思是你不能在经过原生代码的调用中使用 cont，比如 arr.sort((a,b)=>callCC(cont=>cont(true)))，这样是不可以的，因为 sort 是数组原生的函数 ---- 译者注）。
这项技术的性能在不使用延续性的时候保持良好。捕获延续性会比较慢，但是如果你只是要实现一个调试器之类，那么不会有什么问题。然而，如果你要实现一些高级流程控制操作，你有可能会遇到性能问题。不过，你可以实验一下看看是否确实有问题。

延续性简介

让我们复习一下延续性的定义：维基百科将它描述成计算机程序控制状态的抽象表现形式。延续性性使程序状态信息具体化。关键的是控制状态。这意味着当一个延续性被创建，它包含了程序在这个时间点上的全部必要信息，因此你可以在任意时刻将程序恢复到延续性被创建的这个时间点开始运行。

这是单步调试器的内在工作机制。编译好的代码查找断点，当一个断点被触发，它捕获当前的延续性，停止程序的执行。当需要继续执行的时候，简单通过唤起被保存的延续性就可以让程序继续往下执行。

延续性作为语言的一等公民会非常有意思。在 Scheme 中，你可以使用 call-with-current-continuation 来捕获当前的延续性，或者使用 call/cc 简写。有经验的 Scheme 程序员都熟悉下面的代码：

(define (foo)
      (let ([x (call/cc
                (lambda (cont)
                  (display "captured continuation")
                  (cont 5)
                  (display "continuation called")))])
        (display "returning x")
        x))

    (display (foo))

我在我的 JavaScript 虚拟机里实现了一个 callCC 函数，它已经万事俱备。此外，我们可以使用单步调试器来研究延续性是如何作用于控制流的。

基础的延续性示例

上面是一个非常简单的使用延续性的例子。点击"忽略断点往下执行"，看看发生了什么。我们使用 callCC 捕获了延续性，它将延续性作为函数 cont 返回给我们。于是我们 log 了 "captured continuation" 并调用 cont。仔细想一下为什么"continuation called"没有被 log，它是怎么做到的？

现在我们重新点击"Run"按钮，触发第13行的断点，然后连续点击"Step"来单步调试程序，看看当 cont 被调用时发生了什么。

它跳回了第3行！前一个控制流被中断，当 cont 被捕获时的调用栈被保存。传递给 cont 的任意参数替换掉了 callCC 调用，就像是 callCC 自己返回了那个值。

注意，虽然调用一个延续性看起来像是调用一个函数，它们实际上非常不同。调用一个延续性从不返回。这可能让你有点迷糊，我在将来的文章中会详细讲可选的连续性接口。此外，连续性是底层的接口，它很少被直接使用。

延续性像一个传送门。如果下图代表你的控制流，你可以捕获当前调用栈（蓝色传送门）并且在任何时候跳回它（桔黄色传送门）。

程序控制流，通过桔黄色传送门跳转到蓝色传送门时将会把调用栈重置为处在蓝色传送门时的值。

就如同在游戏中的传送门，这些传送门不会随着时间而改变。延续性唯一保存下来的东西是调用栈，因此任何变量的改变在通过延续性跳转之后依然可以生效。让我们看一下闭包中会发生什么：

function foo() {  
      var x = 5;
      var func = function() { return x; };
      x = 6;
      return func;  
    }

    console.log(foo()())

上面的代码会打印6，因为闭包引用了相同的变量，这个变量在运行中改变了。使用延续性，会发生同样的事情，除了调用栈指向变量这一点有所不同。我们会在后面看到有关这些的例子。

实际用途

现在你理解了基本概念，让我们好好使用延续性。它当然看起来很强大，但是你可能在想用它来解决问题时遇上麻烦。你可能会觉得延续性只会让程序变得难懂。

滥用延续性当然会让程序变得难懂。但是，延续性在一些场景下也会很有用。break 和 continue 可能让你的程序变得有点难懂，但是它们确实解决了一些问题，就像另一些流程控制操作那样。此外，在以后的文章里，我们将会讨论界定的连续性，这将强制开发者以更清楚的方式使用延续性。

第一个练习是实现 JavaScript 的 some 方法，这个方法检查是否有任意一个数组元素通过条件判定。非常重要的一点是，它是"短路循环"，即是说如果它找到了第一个通过条件判定的元素，它就会停止迭代后续的元素，因为后续的元素不需要再检查了。

使用延续性实现 some

如果你执行上面的代码，你会注意到它并没有检查 3 和 4。它在 2 通过条件判定之后就停止执行了。单步执行代码看一下它是怎么做的。

当然，我们可以使用 break 来停止 for 循环。但是，这里用延续性来实现这个，只是用简单的例子来说明延续性。这种用法通常是用于你调用其他一些函数，对于有些函数你不能从循环中 break 出来。原生的控制操作符非常有限。然而延续性让你能在堆栈帧中通过。

例如，你想要使用 forEach 取代 for 循环，因为现在 forEach 已经被用在许多地方了，下面是一个例子：

使用实现延续性实现 some, 穿过堆栈帧

这段代码实现的功能和上一段一样，甚至我们可以在传递给 forEach 的函数中调用条件判断。它依然是短路模式的。注意到我们不需要改变 forEach 的任何代码，我们可以如同我们使用在别处一样使用我们的代码。

这凸显了延续性和其他 JavaScript 已存在的特性的本质不同：延续性暂停了整个调用栈。生成器也暂停执行代码，但是 yield 只保存当前堆栈帧，即生成器本身。

虽然 yield 让代码变得清晰，但是它使用的特殊语法必须一层一层都使用，这导致开发者必须要在项目中花费很多时间。将一个函数转换成异步的函数导致大量的重构工作，你得改变所有用到它的地方。我推荐你阅读 "What Color is Your Function?"，这篇文章对这个问题有非常好的描述。

（yield 还有 async/await 都一样，所有依赖异步的函数自己也都得从语法上改成异步，而刚才前面看到的延续性的例子里，虽然 some 给 forEach 传了一个返回延续性的函数，但是并没有要求 forEach 自己有任何改变，这就是 continuations 与 generator 和 async/await 的最大区别 ---- 译者注）

在下一篇文章中，我会演示如何只用普通函数接口（不需要 function* 或者 async function），通过深堆栈控制来实现异步，从而很大程度上改进代码的可重用性和可读性。

错误处理

让我们真正来考虑实际问题。上面的练习有点脑残。我们不会真得那样使用延续性。循环遍历值有许多更好的结构和短路方式。上面的例子仅仅是为了说明什么是延续性。

现在我们将要实现一个新的基础控制结构：异常。这个例子演示延续性能够让你能创建一些以前得内置进语言特性的功能。

使用者可以抛出异常并通过异常处理器 catch 住它们。异常处理器根据给出的代码段产生动态作用域：任何代码块中的异常，甚至外部函数抛出的异常都可以被捕获。

异常处理器需要以堆栈的形式出现：你可以定义一个新的异常处理器在一段时间内覆盖当前存在的处理器，但是前一个异常处理器在新的被 pop 出堆栈之后被恢复，因此我们必须要管理一个堆栈。

堆栈是一个延续性列表，因为当一个 throw 发生的时候，我们需要能够跳回到 try 被创建的地方。这意味着在 try 中我们需要捕获当前的延续性，将它压入堆栈中，运行代码，然后派发异常。下面是 try/catch 的完整实现：

var tryStack = [];

    function Try(body, handler) {
      var ret = callCC(function(cont) {
        tryStack.push(cont);
        return body();
      });
      tryStack.pop();

      if(ret.__exc) {
        return handler(ret.__exc);
      }
      return ret;
    }

    function Throw(exc) {
      if(tryStack.length > 0) {
        tryStack[tryStack.length - 1]({ __exc: exc });
      }
      console.log("unhandled exception", exc);
    }

这里的关键是延续性可以用某些值来恢复。return body() 会返回代码的最终值。如果正常返回，没有延续性被调用，它只是将值传递过去。但是如果 Throw 被调用，它会使用异常值调用被捕获的延续性，然后这个值被赋给 ret，于是我们检查返回值的类型然后调用处理器。（我们可以对异常类型做更精确的检查。）

注意到我们在调用 handler 之前将 tryStack pop 了，这么做是保证在异常处理器中产生的异常能正确地压入堆栈。（是这样的，如果我们不在 handler 之前 pop tryStack 而在 handler 之后 pop 的话，那么如果 handler 自己产生了新的异常，我们就来不及将之前的从 tryStack 中 pop 出来了，因为程序跳转了，这一段我觉得作者自己解释得不清楚，不能保证我理解的对，可以结合原文对比一下 ---- 译者注）

下面的代码演示 Try / Catch 的使用：

function bar(x) {
      if(x < 0) {
        Throw(new Error("error!"));
      }
      return x * 2;
    }

    function foo(x) {
      return bar(x);
    }

    Try(
      function() {
        console.log(foo(1));
        console.log(foo(-1));
      },
      function(ex) {
        console.log("caught", ex);
      }
    );

不幸地是，JavaScript 不允许我们扩展语法（虽然我们可以使用 sweet.js macros，在我以后的文章中会介绍）。因此我们不能像原生的 try / catch 那样传一个代码块进去，而必须传函数进去。上面的代码的输出将会是 2 \n caught "error!"。

上面的例子可以点击下面的链接演示，我在 Try 代码块中已经设置了一个断点，点击"Run & Ignore Breakpoints"来检查输出，点击"Run"来触发断点进行单步执行来看它是怎么一步步展开的。

当 x 在 bar 中的值是-1` 时, 一个异常被抛出并在我们的异常处理器中被处理。单步执行代码来看它是如何做的

还有更多的控制结构可以通过延续性来实现，我将在以后的文章中逐步给大家介绍。

从外部调用

目前为止我们总是从 callCC 内部调用延续性。这意味着我们总是只跳出运行栈，也即我们总是跳回到前面的堆栈帧。

这样的延续性被称作 escape continuations。这是一种受限制的延续性，它只能在传递给 callCC 的函数的动态范围内被调用（在这个例子中，它可以被叫做 callWithEscapeContinuation 或者 callEC）。很多功能比如异常只能通过 escape 延续性实现。

区分出这种特定延续性的理由是性能。Escape 延续性不需要保存整个调用栈，它们可以假定在 callEC 的时间点上的堆栈帧总是存在于内存里，不管延续性在什么时候被调用。（从里层往外层跳转就只要从函数return就行了，不需要自己维护整个调用栈 ---- 译者注）

然而，我实现的延续性是完全的延续性，这才是神奇的地方。在以后的文章里，我会使用这个技术来实现一些特性比如协程。现在，我们先看一个简单的例子：

在 callCC 调用中，你可以仅仅返回延续性本身：

var value = callCC(cont => cont);

value 将是一个延续性，但我们不叫他做 cont，因为当之后延续性被调用，它会变成不同的值。value 可以是任何延续性被调用的值。我们可以将它封装到一个函数中来方便使用：（译者表示这里有点晕菜了╮(╯▽╰)╭ ---- 译者注）

function currentContinuation() {
      return callCC(cont => cont);
    }

现在，我们可以做像这样的事：

我们让控制流形成了分支，走哪个分支取决于我们得到的是延续性还是一个普通的值

这非常强大，因为它说明我们可以在代码的任何时间点调用一个延续性，它总能正常工作。

上面的代码仅仅是一个示例，下面用一个更复杂的例子来演示它更多的价值。通过延续性，我实现了一个非常基础形式的协程，可以暂停自身的执行，然后通过一个值恢复执行。

function currentContinuation() {
      return callCC(cont => ({ __cont: cont }));
    }

    function pause() {
      var value = currentContinuation();

      if(value.__cont) {
        throw value;
      }
      else {
        return value;
      }
    }

    function run(func) {
      try {
        return func();
      }
      catch(e) {
        if(!e.__cont) {
          throw e;
        }

        var exc = e;
        return {
          send: function(value) {
            exc.__cont(value);
          }
        };
      }
    }

当协程调用 pause，一个延续性被抛出，调度器捕获它，返回一个对象给调用者，让调用者可以通过它继续运行协程。下面是使用它的一个简单的程序：

function foo() {
      var x = pause();
      return x * 2;
    }

    var process = run(foo);
    if(process.send) {
      process.send(10);
    }
    else {
      console.log(process);
    }

我们需要检查 process.send，因为我们的实现非常简陋，它保存了完整的延续性，它包含了run被调用时的顶层调用栈。这意味着当程序恢复运行时，顶层控制也被恢复，因此我们的 run 会再一次返回。

挑战：实现一个新的版本，让 process.send 返回最终的值，让使用者不再需要自己处理 run 的多次返回。

以下是完整的程序，你可以单步调试它：

完整的程序已经包含了一个断点. 点击 "run" 来研究它

在以后的文章中，我们将讨论如何使用延续性实现更健壮的协程。

Closing Over Data

遮蔽数据

非常重要的一点是，延续性只保存调用栈，而不保存任何堆栈帧依赖的数据。恢复一个延续性并没有恢复任何被调用栈使用的变量。这样，考虑每个堆栈帧如同闭包那样简单引用这些变量，那样的话，任何对作用域外的改变都会生效。

这对于初学者来说会有点迷茫，但是，希望下面这个简单的例子能让大家明白：

x 的值是 6 因为 x 的改变在延续性恢复后依然生效。捕获延续性并不会保存 x 的值.

在延续性被调用的时候，没有产生任何问题。如果我们保存了延续性以后调用，改变了一些局部变量，从函数中返回，当延续性被调用，我们会看到所有局部变量被改变了。延续性遮蔽了它的数据。

注意：我的延续性实现里面可能有些 bug，使得一些情况下上面说的不成立。在我的实现里，我需要找到一种方式确保数据被遮蔽而不是被拷贝。如果改变需要在延续被调用之后手工生效，那是一个bug。

背景

说来话长，但我会长话短说：

2011年我在做一款浏览器页面上的游戏编辑器，我想要交互式地调试代码。
在这段时间，我由 Scheme 而受启发设计并实现了自己的编程语言 Outlet，之后我尝试让它变得可调试。我通过 continuation-passing style（CSP）变换，有效地实现了延续性，但是它让我不得不重写了堆栈和作用域。它运行得很慢（性能和原生的 JS 堆栈和作用域完全没法比）。我将细节记录在我的博客里：
- Compiling to Javascript in CPS, Can We Optimize?
- The Quest for Javascript CPS: Part 2
在尝试使用原生的 JS 函数作用域的过程中，我考虑通过大量使用 generators 来暂停函数执行。然而我还是需要去重写堆栈，至少变量是原生的了，实现方式也简化了很多（generators 刚刚被 JS 引擎支持）。我把它叫做 YPS 它 yield 每一个表达式，执行在一个特殊的虚拟机上。它的性能实在不敢恭维。
- 接下来 @amasad 终结了这个方案，写了一篇非常棒的文章。
针对我基于 generator 暂停函数执行的想法，@msimoni 指点我去阅读这篇论文 "Exceptional Continuations in JavaScript"。我意识到我需要的是完全的延续性，而论文指出了不需要很大的性能开销实现它的技术。虽然捕获延续性比较慢，但其它部分的代码达到了最佳性能。

这篇论文描述了非常优雅的技巧来实现延续性，从而给了我任何时候跳转代码的能力。不幸的是，它需要一个精巧复杂的变换，但是就在这个时候， regenerator 发布了，并且它实现了一个相似的变换！我 fork 了 regenerator 代码，实现了延续性，得到了一个可用的单步调试工具，然后意识到我可以将延续性作为一等公民开放出来，使得使用者能用它做我上面演示给你的所有的事情。（这是大约 2 年前的事了。从那以后这个项目一直被我丢在电脑里，直到几周之前我重新捡起了它。）