神器Continuation

Continuation、Coroutine和Generator是异步编程中的一些概念。通过Continuation能够实现Coroutine和Generator。

Continuation常有两种实现,一种是以call/cc(call with current contination)为代表的语言级别的实现;另一种对于不能原生支持Continuation的语言但是支持闭包(函数作为一等公民)的语言,可以使用CPS(continuation-passing style)来实现Continuation。

Continuation

call/cc

维基百科上面的一个例子来说

(define (f return)
  (return 2)
  3)
(display (f (lambda (x) x))) ; displays 3
(display (call-with-current-continuation f)) ; displays 2

其中(define (func_name arg1 ... argn) exp)表示定义函数。
查看第一行调用,display打印得到3,这是由于f始终返回最后一个表达式的值3。无论return是个什么,哪怕return是个回调函数,f的计算结果也是3。
查看第二行调用,display打印得到2。这是由于在调用call-with-current-continuation时,首先Lisp会把当前的环境打包成一个叫Continuation的东西,并且以它作为参数调用f Continuation。查看f的代码,下面我们要执行return 2,也就是Continuation 2。而call-with-current-continuation打包的Continuation这个东西可以看做一个的函数,调用Continuation就会f会退出,程序上下文返回到调用call-with-current-continuation时的状态,并且(call-with-current-continuation f)会被替换成Continuation的参数2,于是实际上运行的是display 2

还可以这样理解,在本来程序是要执行(display xxx)的,Lisp一看xxx原来是一个call/cc f,那就把现在的状态(下面要运行display啦)打包成一个Continuation,然后程序就不往下面运行了display了,而是立即跳转去执行f函数。那这个f函数有点特别,他会被系统喂刚才得到的Continuation参数return,函数通过调用return就相当于从f函数中退出,并继续执行调用f前要执行的display,这里display需要一个参数,所以调用return 2,这里可以近似理解Continuation参数return就是下面要执行的display函数的别名。

CPS

对于没有call/cc这机制的语言,可以使用闭包进行模拟。

callback

通常的语言如C++中,常使用return命令返回结果,例如

1
2
3
4
int add(int x, int y){
return x + y;
}
int result = add(1, 2);

其中int result = add(1, 2);语句将resultadd函数的返回值return x + y进行了绑定。这样的方式对我们屏蔽了绑定的细节。我们需要通过额外的了解能够得知,并且还要取决于具体的代码和编译环境。例如一般int返回值会被放入eax中,再调ret,而有些时候浮点数会被放在FPU或XMM上返回。当然也许会说编译语言没必要去讨论它的目标代码,不过至少我们只有通过把函数的返回值和某个名字进行绑定这一种默认的处理返回值的方式。
对于有些异步的需求,常常有回调函数的概念。函数接受一个额外的回调函数作为参数callback

1
2
3
4
5
6
7
template <typename F>
void add(int x, int y, F f){
return f(x + y);
}
add(1, 2, [&] (int result) {
});

将这段代码与上面的代码进行对比,我们发现实际上我们返回的是一个函数,而不是一个

CPS function

Continuation和callback都是可以调用的,不同的是在A里面调用一个callback B后,程序进入B然后从B返回到A继续执行;而在A里面调用一个Continuation B后,程序立刻进入B运行,并且不会在B再返回到A。
因此对于没有call/cc这样的first-class Continuation的语言可以通过callback实现CPS function。方法如同上面的add函数一样,add函数通过在函数结尾调用该回调函数,自己的计算结果传给该回调函数,来完成返回操作。这样的回调函数方案借助了尾递归(在函数的末尾调用另一个函数)。
此时,函数实际上将自己的剩余部分作为callback(此时该callback称为continuation),该函数即CPS function。
相对于命令式语言的if/elsedo/while/break/continuetry/catch/finallygoto等控制语句,CPS function的好处是能够更灵活地操作control flow,因为下一步要做什么不是根据你是顺序结构/选择结构/循环结构,而是你在continuation里面写了什么。
这样还会带来一个好处是程序可以任意被中断(此时只需要保存回调函数的指针f),然后从中断的地方调用f开始继续执行。于是常常使用Continuation/Coroutine代替多线程(毕竟线程的开销还是很高的)。