什么是continuation?

love_wisdom

continuation概念及意义

OwnWaterloo

粗略地说， continuation就是“接下来要做什么”。。。

1. 
   
2. void f(int x, int y, int root)
   
3. {
   
4.   printf("%s x+y = %d\n", root? "#": "$", x+y);
   
5.   printf("%s x-y = %d\n", root? "#": "$", x-y);
   
6. }
   

复制代码

“printf("%s x+y = %d\n", root? "#": "$", x+y)” 的continuation就是：
1. 继续执行下面一条printf
2. f返回它的调用者
3. 在返回处继续执行知道这个线程中止（continuation是有界限的）


“x+y”的continuation说明起来就更复杂一些。 假设 v 是 “x+y”的结果， “x+y”的continuation可能是：
1. “printf("%s x+y = %d\n", root? "#": "$", v)” 接着是这整个表达式的continuation， 就是上面说的直到这个线程中止的剩余部分。
2. “printf("%s x+y = %d\n", "$" , v)” 以及后续continuation
3. “printf("%s x+y = %d\n", "#" , v)” 以及后续continuation
...
C语言规定了两个printf的顺序， 必须先执行第1个， 再执行第2个。 所以前一个printf的continuation说明起来更容易一些。
C语言并没有规定printf的参数的求值顺序， 所以就此处就不像前面那样容易说明。。。
如果 root? "#": "$" 比 “x+y”后求值， 那就是1的情况。
如果 root? "#": "$" 比 “x+y”先求值， 那2就是root非0的情况， 3就是root为0的情况。

实际上还可以继续细分， 比如 “root” “"%s x+y = %d\n"”这些子表达式。
总之， continuation 是等待这一个值的。
“printf("%s x+y = %d\n", root? "#": "$", x+y)” 也等待这printf的返回值， 只是立即丢弃了， 不容易看出来。
而“x+y”的continuation就需要“x+y”的求值结果。


因此， 哪怕是C语言，也存在continuation。 但这些continuation不能拿给程序员继进行操作， 所以没啥卵用。。。
C语言也有可以让程序员使用的continuation， 就是jmp_buf。

1. 
   
2. jmp_buf k;
   
3. int x = setjmp(k);
   
4. ...
   

复制代码

“setjmp(k)”的continuation就是“int x = v; ...”， 即对x赋值， 以及后续表达式， 直到线程中止。 其中v是setjmp(k)的值。
这个continuation就是程序员可以操作的了。 可以通过“longjmp(k, val)” 调用该continuation， 即是回到“setjmp(k)”处， 为x提供一个值， 并继续执行。

不过C语言规定longjmp只能从调用链的“深处”往“浅处”跳， 不能反过来。 于是限制了它的用处。。。
并且用的时候还要各种小心。。。 C++的析构函数。。。 volatile。。。 sign mask。。。。 于是肯定就会出现“setjmp/longjmp  Considered Harmful”这样的论点。。。

除了C语言标准外， windows下有fiber， posix里有ucontext。 它们都让程序员可以操作continuation。


continuation最出名的应该是Scheme里的call-with-current-continuation（一般简称为call/cc， 但前者才是r5rs里有的， call/cc不是）。
call/cc 是一种 undelimited continuation ， 其实不如 delimited continuation 好用。。。
delimited continuation好像正是源自ML系列的语言。。。  你可以去搜一下， reset/shift或者prompt/control之类的， 它们都是delimited continuation。


还有一种与continuation有关的概念叫continuation passing style。 俗称callback或callback hell。。。

love_wisdom

回复 2# OwnWaterloo


    谢谢，那么call/cc和delimited continutation是什么？

love_wisdom

continutation passing style又是什么？

OwnWaterloo

比较理论地说， 可以将各种所谓的control structure看作对continuation的使用。
不过还是整点实际的吧。。。

比如， 进行一个文件读写操作(可以是regular file, pipe, socket, ...)。
可以选择使用blocking read/write。
这样的好处是代码依然是“正常”的， 坏处就是一个线程被阻塞了。

也可以不选择blocking read/write， 而是等待它可以读写的时候再进行read/write或者等待read/write完成后处理数据。

从continuation的角度来分析， 这个所谓的等待， 其实就是传递continuation。。。
区别在于是语言帮程序员提取一个continuation， 还是程序员自己人肉提取。。。

OwnWaterloo

回复 3# love_wisdom

1. 
   
2. (call/cc
   
3.   (lambda (k)
   
4.     ...))
   

复制代码

k就是整个call/cc表达式的continuation。
它的界限标准里似乎并没有说。

1. 
   
2. (shift k ...)
   

复制代码

k就是整个shift表达式的continuation。
它的界限是到最近的一个reset为止。
reset/shift是delimited continuation的一种。

love_wisdom

OwnWaterloo 发表于 2016-07-26 20:55
回复 3# love_wisdom k就是整个call/cc表达式的continuation。
它的界限标准里似乎并没有说。k就是整个shi ...

说了等于没说

OwnWaterloo

回复 4# love_wisdom

1. 
   
2. (define (ls dir)
   
3.   (let*((files (readdir dir))
   
4.         (files (cons "." (cons ".." files)))
   
5.         (files (map (lambda (file) (string-append dir file)) files)))
   
6.     (map lstat files)))
   

复制代码

这个就是direct style的样子。 其中readdir返回一个list， 里面是string， 元素是dir里的所有文件但不包含"."和".."。
lstat就是。。。 就是lstat(2)的绑定。。。 它返回文件的stat。。。

其他函数也都是传递参数／返回。。。


然而。。。  有个叫nodejs的平台。。。  它的readdir和lstat是这样的。。。

1. 
   
2. (define (readdir& dir k)
   
3.   (let ((files ...))
   
4.     (k files)))
   
5. 
   
6. (define (lstat& file k)
   
7.   (let ((stat ...))
   
8.     (k stat)))
   

复制代码

它接受一个continuation k， 当readdir(2)或lstat(2)完成后调用k。

这个就是 continutation passing style。 函数不再是直接的返回， 而是要求调用者传递自己的continutation（俗称callback）。
在direct style里， 通过返回给调用者提供值的时候， continutation passing style通过调用continutation 给调用者提供值。


如果语言没有提取continutation的机制， 那么continutation passing style是传染性的， 一旦有一处是这个样子， 就会让其他地方也变成这个样子， 比如：

1. 
   
2. (define (ls& k dir)
   
3.   (readdir& dir
   
4.     (lambda (files)
   
5.       (let loop
   
6.           ((files (map (lambda (file) (string-append dir file)) (cons "." (cons ".." files))))
   
7.            (stats '()))
   
8.         (if (not (null? files))
   
9.           (lstat& files
   
10.             (lambda (stat) (set! stats (cons stat stats))))
    
11.           (k stats))))))
    

复制代码

如果要调用 readdir& 和 lstat& ， ls也不能直接返回了， 而是要继续写成continutation passing style。
ls& 要求调用者传递一个k给它， 它在搜集完stats的时候调用这个k。


而如果语言可以帮助程序员提取continutation， 就可以恢复成direct style：

1. 
   
2. (define (readdir dir)
   
3.   (shift k (readdir& dir k)))
   
4. 
   
5. (define (lstat file)
   
6.   (shift k (lstat& file k)))
   

复制代码

此处用readdir&和lstat&实现一个direct style的readdir和lstat。

它们内部依然是continutation passing style。 readdir和lstat要将一个continuation传递给readdir&和lstat&。 只是这个continutation是语言帮忙提取的。

对readdir和lstat的调用者来说， 它们会返回， 是direct style的。

love_wisdom

回复 8# OwnWaterloo


    delimited continuation 是什么？