漫谈程序控制流
Closed this issue · 2 comments
前言
随着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交替输出简单描述一下程序的执行：
- 执行第一个run
- continuation指向point A，然后它被enqueue, 此时queue为[A]
- 执行doSomething("A")
- 输出A
- 执行
$yield()- 将当前continuation enqueue, 此时queue为[A, C-A]
- dequeue并执行，此时queue为[C-A], 从point A处执行
- point A, 执行第二个run
- continuation指向point B, 然后它被enqueue，此时queue为[C-A, B]
- 执行doSomething("B")
- 输出B
- 执行
$yield()- 将当前continuation enqueue, 此时queue为[C-A, B, C-B]
- dequeue并执行，此时queue为[B, C-B], 从C-A处执行
- C-A处
- 输出A
- 执行
$yield()- enqueue, queue为[B, C-B, C-A]
- dequeue并执行，此时queue为[C-B, C-A], 从B处执行
- B处，dequeue并执行，从C-B处执行，输出B，并enqueue, 此时queue为[C-A, C-B]
- [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，将有助于更好的玩转各种流程控制。
1
hello