漫谈程序控制流

Table of contents

前言

随着ECMAScript 2015(ES6)的正式发布，以及babel这种 ES6 转 ES5 的工具的慢慢成熟, 在真实产品里使用 ES6 已经完全可行了。

写 JS 的朋友们，是时候点开es6features看一下了。

值得一提的是，ES6 特性里竟然包括尾调用优化(tail call)，真是要点个赞:thumbsup:。然而，这并没有什么用。

从 ES6 的 Generator 谈起

在 ES6 众多新特性里，Generator 无疑是一个很酷的东西。cool 在哪里？看 code:

// 注: 以下code可以在chrome dev tool的console里直接跑
function* fib() {
  // 用function*来定义generator
  var pre = 0,
    cur = 1;
  for (;;) {
    // 无限循环
    var temp = pre;
    pre = cur;
    cur += temp;
    var reset = yield cur; // yield决定next()的返回值
    if (reset) {
      (pre = 0), (cur = 1);
    }
  }
}
var g = fib();
console.log(g.next().value); // 1
console.log(g.next().value); // 2
console.log(g.next().value); // 3
console.log(g.next().value); // 5
console.log(g.next(true).value); // 1

在这里，我们定义了一个 fibonacci 数列的 generator, 每次调用next(), 会 yield 下一个数字; 而next的参数则会是 yield 表达式的值，比如next(true), 则 yield cur就返回 true。

可以看到 code 里有一个无限循环，但并不会导致 CPU hang 住, 因为每一次yield后，程序会暂停，而在next()之后又继续运行。而这，便是 generator 最 cool 的地方：它改变了程序的控制流！

简单来说，yield 停止，next 继续，于是通过这个规则，我们就可以控制程序的运行顺序。于是我们可以写出这样的 code:

co(function* (){
  var data1 = yield ajax_call_1(); // 发出一个ajax请求
  console.log(data1); // 输出response
  var data2 = yield ajax_call_2(data1); // 发出另一个请求
  console.log(data2); // 输出response
  var data3 = yield ajax_call_3(data2); // 发出另一个请求
  console.log(data3); // 输出response
});

//----------------------------------

// 以下为对比的callback写法
(function(){
  ajax_call_1(function(data1){
      console.log(data1);
      ajax_call_2(data1, function(data2){
          console.log(data2);
          ajax_call_3(data2, function(data3){
              console.log(data3);
              ...
          });
          ...
       });
    });
})();

这段看似同步的代码实际上是异步执行的，但是直观简单漂亮，写起来可以谈笑风生，比 callback 不知道高到哪去了(关于这一点，可以看 tj 写的callbacks vs coroutines)。至于那个co，就是某个奇怪的函数，在适当的时候(比如 callback 时)调一下next让 generator 继续跑。感兴趣的话，请戳co

现在让我们总结一下： generator 是一种特殊的子程序，而yield是一种流程控制指令，在 generator 里使用 yield 会将程序的控制权交还给调用者(即返回调用处)，而外界调用 generator 的next方法会让该 generator继续执行。generator 可以用来做iterator，也可以用来玩魔法(同步转异步)，因为它提供了一种较为优雅的流程控制方式

不过，说是 magic，但其实程序的世界，并没有无根之木、无源之水。接下来，就让我们回溯本源，探一探各种流程控制结构的来龙去脉

关于控制流(control flow)

所谓控制流，说白了就是程序执行的顺序。

我们知道，程序执行的基本原理是：cpu 从 program counter(一个寄存器)拿指令的内存地址，然后去内存拿指令来执行，执行过程中会改变 program counter 的值(比如加 1，也就是顺序执行)。如此循环往复直至结束。

程序流程的控制，实际上就是在特定的情况下，更新特定的值到 program counter。而上升到编程的层次，则是提供代表特定策略的流程控制语句，用以实现各种丰富的功能。

一般而言，流程控制语句可以分为以下几类：

• 无条件分支

  就是 goto 了，想去哪去哪(当然还是有限制的，比如 c 语言里 goto 就不能跳出当前 function)。其缺点在于，程序可读性/可维护性容易变得极差。

• 条件分支

  这个其实就是大家耳熟能详的各种基本流程控制语句了，比如 if-else, switch, 以及 for, while 等 loop 语句

• 无条件终止程序

  比如 exit, return

• 运行位在不同位置的一段指令，但完成后会继续运行原来要运行的指令

  包括子程序(subroutine)、协程（coroutine）及延续性（continuation）。(注：generator 实际上是一种 coroutine)

前三种比较直白简单，也比较常见，我们主要看第四种。

运行另一段指令，然后返回原指令段中继续执行。这种情况最常见的就是 subroutine(比如 function 或者 OO 语言里的 method)了，一般都是通过call stack来实现，每次 function call 都产生一个 stack frame 压入栈顶，该 function 结束时将其出栈，这样栈顶就变回其 caller 的 stack frame 了，于是可以继续执行 caller 的代码。

我们看一下典型的 subroutine 调用:

function doOtherthing() {
  // block B
  {
    console.log("executing...doOtherthing");
    return;
  }
}

function doSomething() {
  // block A
  {
    console.log("executing...doSomething");
  }

  doOtherthing();

  // block C
  {
    console.log("continue executing...doSomething");
    return;
  }
}

doSomething();
// executing...doSomething
// executing...doOtherthing
// continue executing...doSomething

这里没什么奇怪的东西，分成几个 block 只是为了方便引用，相信学过几天编程的都能理解。

现在我们从控制流的角度分析一下这个程序。block B 明显与 A 和 C 不在一处，但执行顺序却是 A=>B=>C。A 执行后是 subroutine 调用，jump 到 B 处执行；而 B 执行后会返回到 C 处执行，这也正是 return 语句的语义。

subroutine 调用的执行顺序是固定的，这是因为 return 是一个关键字，提供隐式的流程控制，我们并不能像操作一个 object 一样来操作它——等等，如果可以呢？

如果 return 的语义可以被抽象出来并能在程序中操作，那么我们将可以保存任意的执行点，并且在任意时候返回该处继续执行。这句话的意思是，我们的程序将可以实现任意的控制流，而无需运行环境的支持，比如说我们可以在 ES5 里实现 generator。

你或许已经听过这种抽象的名字：continuation

Continuation

在计算机科学里，Continuation 是指可以被编程语言访问的、对程序控制流程/状态的抽象表示。简单来说，就是程序运行时的某个执行点，比如上文所说的 block B 里的 return 运行后的那个点。而 return 语句可以理解为隐式的调用了 current continuation。

我们说current continuation, 是指在那个点之后将要执行的代码，比如 B return 时，current continuation 就是整个 block C。

说到 continuation，就不得不说 CPS(continuation passing style)，顾名思义，就是显式的将 continuation 作为参数传递，以此来进行流程控制。而我们平常写的 code 叫做 direct style，比如上文 doSomething 那段 code。

我们现在将之前的 code 改写成 CPS:

function doOtherthing(k) {
  // block B
  {
    console.log("executing...doOtherthing");
    k();
  }
}

function doSomething(k) {
  // block A
  {
    console.log("executing...doSomething");
  }

  doOtherthing(function (ret) {
    // block C
    {
      console.log("continue executing...doSomething");
      k();
    }
  });
}

doSomething(function () {});
// executing...doSomething
// executing...doOtherthing
// continue executing...doSomething

改写后执行结果是一样的。可以看到函数调用变成了 callback 的形式，而 return 都变成了k()，这个 k 就是传入的 continuation。

注意，这里的重点并不在于 callback 形式，而在于CPS 变换，之前的 code 和这段 code 是等价的。在这里我们是手动做的 CPS 变换，但实际上，所有 direct style 的 code 都可以被自动变换成 CPS 的 code。(至于怎么变换，可以尝试看How to compile with continuations)

为何要强调自动的 CPS 变换？因为它可以用来实现一个锋利无匹的强大函数: call/cc

call/cc

scheme 语言里有一个著名的函数，叫做 call-with-current-continuation, 一般简称为 call/cc。

call/cc 接受一个函数作为参数，并捕捉 current continuation 然后将之传递给这个函数。而 continuation 一被调用，call/cc立即返回，返回值即为传给 continuation 的参数。 比如：

(let ((a (call/cc
          (lambda (k)
            (begin
              (display "will execute\n") ; 输出 "will execute\n"
              (k 1)
              (display "will not execute")))))) ; 不执行
  (display a)) ; 输出1

再来段 JS 的版本，JS 里当然是没有 call/cc 的了，不过这不妨碍我用 JS 来表达。此处假设 js 里有一个等价的 callcc：

var a = callcc(function (k) {
  console.log("will execute"); // 输出 "will execute"
  k(1);
  console.log("will not execute"); // 不会执行
});

console.log(a); // 输出1

这段 code 等同于:

(function (k) {
  console.log("will execute"); // 输出 "will execute"
  k(1);
})(function (a) {
  console.log(a);
});

这实质上就是自动做了 CPS 变换。

有了 call/cc，就可以直接在程序里操作 continuation 了。仅从功能上来说，就可以实现各种高级控制流，而不需要编译器/解释器这个 level 的支持了。

接下来就让我们看看 call/cc 的 power

Coroutine

Coroutine(协程)是一种类似 subroutine 但更灵活的控制结构，它允许有多个程序进入点，可以随意暂停或继续执行，主要用来做 nonpreemptive multitasking(非抢占式多任务处理)。

在 coroutine 中，可以通过yield语句来转移控制权，比如两个 coroutine，c1 和 c2，在 c1 中调用yield to c2(伪代码), 就会去执行 c2，在 c2 中又调用yield to c1，就会继续执行 c1(重新进入之前的执行点)。听起来和之前说的 generator 有些像？其实 generator 就是一种 coroutine，我们之后会讲到。

Donald Knuth说：“subroutine 是 coroutine 的特例”，因为 subroutine 可以看作不使用yield的 coroutine。

我们说 coroutine 是用来做 nonpreemptive multitasking(非抢占式多任务处理)的，要理解这一点，最好先理解 preemptive multitasking(抢占式多任务处理)。

我们熟知的基于多线程的多任务/并发处理就是 preemptive 的, 程序控制权由调度器而非程序自身来决定， 实质上就是在程序外部强行打断程序的运行，再根据某种策略(优先级,动态时间片)决定由哪个线程继续执行。

而 coroutine 是自已决定将控制权交给谁(yield)，因而不会有 race condition, 不需要考虑锁的问题，可以极大的简化并发编程。

这里要提一下为何我们熟知的是抢占式多任务处理，因为人们需要流畅的同时做多件(不相关的)事的能力，比如在上网时下载和听音乐，而抢占式的多任务处理有助于实现这一点(不会因为控制权被占用而导致其它应用 hang 住)。而编程时关注的是如何更高效的做好事情，并且开发者知晓全部的 context，也就容易明白如何去协调控制权，所以从编程的角度，非抢占式多任务处理反而更有优势。

而从具体实现的角度来看，coroutine 一般是语言级别的实现，实际上是在用户态进行上下文切换，不会陷入内核态，因而更高效。

coroutine 的缺点是无法利用多核，它只能做 concurrency，而不能做 parallelism，因为一般它是跑在一个线程上，多个 coroutine 不能同时运行。但是也有改进的方案，比如 go 语言的 goroutine, 就是 work 在一个线程池之上的，不过这样就需要更复杂的调度了，当然名字也华丽的变了。

以下是用 callcc 实现简单的协程(不过不能运行):

var queue = [];
function isEmpty() {
  return queue.length == 0;
}
function enqueue(x) {
  queue.push(x);
}
function dequeue() {
  return queue.shift();
}
function run(f) {
  callcc(function (k) {
    enqueue(k); // 将current continuation enqueue
    f();
  });
}
function $yield() {
  callcc(function (k) {
    enqueue(k);
    dequeue()(); // dequeue某个continuation并执行
  });
}

function doSomething(str) {
  for (;;) {
    console.log(str);
    $yield(); // 放弃控制权
    // point C
  }
}

run(function () {
  doSomething("A");
});

// point A
run(function () {
  doSomething("B");
});

// point B
if (!isEmpty) {
  dequeue()();
}

// 理论上的输出结果为
// A
// B
// A
// B
// ..., A和B交替输出

简单描述一下程序的执行：

1. 执行第一个 run
   • continuation 指向 point A，然后它被 enqueue, 此时 queue 为[A]
2. 执行 doSomething(“A”)
   • 输出 A
   • 执行$yield()
     • 将当前 continuation enqueue, 此时 queue 为[A, C-A]
     • dequeue 并执行，此时 queue 为[C-A], 从 point A 处执行
3. point A, 执行第二个 run
   • continuation 指向 point B, 然后它被 enqueue，此时 queue 为[C-A, B]
4. 执行 doSomething(“B”)
   • 输出 B
   • 执行$yield()
     • 将当前 continuation enqueue, 此时 queue 为[C-A, B, C-B]
     • dequeue 并执行，此时 queue 为[B, C-B], 从 C-A 处执行
5. C-A 处
   • 输出 A
   • 执行$yield()
     • enqueue, queue 为[B, C-B, C-A]
     • dequeue 并执行，此时 queue 为[C-B, C-A], 从 B 处执行
6. B 处，dequeue 并执行，从 C-B 处执行，输出 B，并 enqueue, 此时 queue 为[C-A, C-B]
7. [C-A, C-B] -> [C-B, C-A] -> [C-A, C-B] 循环, A 和 B 交替输出

可见通过callcc和一个 queue，我们可以轻易的实现 coroutine

Generator

Generator 又叫 Semi-Coroutine(半协程)或 Asymmetric Coroutine(不对称协程)，它本质上仍是协程，和一般的协程的区别在于，generator 只能把控制权交还给它的caller, 而 coroutine 是可以决定把控制权交给谁。

先看一个 callcc 实现的 generator:

function fib() {
  var controlState = function ($yield) {
    var pree = 0;
    var pre = 1;
    while (true) {
      callcc(function (resume) {
        controlState = resume;
        $yield(pree);
      });
      var tmp = pree;
      pree = pre;
      pre = tmp + pre;
    }
  };

  return {
    next: function () {
      return callcc(controlState);
    },
  };
}

next调用时，进入 controlState 函数，$yield 一旦调用，马上返回，但是 controlState 已经被替换成内部循环处的 continuation，因而当next再调用时会回到循环处继续执行。

其实 generator 可以和 coroutine 互相转化，因为它们本质上是一样的东西。generator 加一个 scheduler 就可以实现 coroutine(yield 一个 value, 然后根据 value 决定 resume 哪个 generator)

来一个用 ES6 generator 模拟 couroutine 的例子(可以在 chrome dev tool 里运行):

function* ge1() {
  for (var i = 1; ; i++) {
    console.log("running...generator 1, " + i + " times");
    yield "g2";
  }
}

function* ge2() {
  for (var i = 1; ; i++) {
    console.log("running...generator 2, " + i + " times");
    yield "g1";
  }
}

function schedule() {
  var map = {
    g1: ge1(),
    g2: ge2(),
  };
  var current = "g1";
  for (var i = 0; i < 100; i++) {
    current = map[current].next().value; // current 在'g1'和'g2'间来回变化
  }
}

schedule();

Delimited Continuation

关于 continuation, 还有一个值得一提的是 Delimited Continuation，Scala 里就支持这种 continuation。它是在一个限定的区域里，捕捉 continuation 并具体化成一个函数，以供复用。一般是通过 reset+shift 来表达：

(reset
 (display (* 2 (shift k
                      (k 2)
                      (k 4)
                      (k 3)))))

用 JS 来翻译一下：

reset(function () {
  var x = shift(function (k) {
    k(2);
    k(4);
    k(3);
  });
  console.log(2 * x);
});
// 4
// 8
// 6

再翻译成 CPS：

(function (k) {
  k(2);
  k(4);
  k(3);
})(function (x) {
  console.log(2 * x);
});

现在应该很好理解了，类似于 call/cc 的情况，不过用 reset 限定了一个 scope。 将 shift 之后reset 之内的代码捕捉并封装成一个函数，然后传递给 shift 块里的那个函数。

这里一个要注意的点是，shift 里的k是一个函数，所以它可以多次使用；而 call/cc 里的k调用一次就退出了，后边的都会 ignore。 从这个角度而言，delimited continuation 是纯粹的函数，而 undelimited continuation 不是，因而 delimited continuation 更直观更符合直觉，也就更适合我们用来编程

最后

碍于能力以及篇幅，本文仅是对程序控制流的浅尝辄止。

纵观而言，各种高阶的流程控制结构，都与 continuation 相关，这是因为 continuation 是对(隐式的)控制流本身的抽象。

不过现代的高级语言里，一般不直接提供 first-class 的 continuation, 而是提供如 generator, coroutine 甚至 delimited continuation 等的高阶控制结构，因为它们足够强大而又相对 call/cc 更可控更易于理解。

而它们的实现也不会是像我这里所写的那样简单，甚至也不一定是基于 call/cc 去实现，然而其基本原理是一致的。因此理解 continuation, 理解 CPS，理解 call/cc，将有助于更好的玩转各种流程控制。