怎样理解 Continuation-passing style?

呃, 这东西首先是用 Wiki 的... en.wikipedia.org/wiki/C 搜了一遍, 中文资源不是一般的少..
关注者
498
被浏览
42222

12 个回答

要理解CPS,首先要理解Continuation是什么。

计算是有先后顺序的,比如要在Racket里计算1+2+3:

(+ 1 (+ 2 3))

显然需要首先计算(+ 2 3),再计算(+ 1 5),在得到(+ 2 3)的结果之前是无法计算(+ 1 ...)的。

我们把(+ 1 ...)这个表达式中缺少的部分叫做hole,一个带有hole的表达式就是continuation,它需要另一个东西来填补这个hole才能进行进一步的计算(这个其实就是Evaluation Contexts的概念)。

Continuation是链式的,一个Continuation还链接着另一个Continuation。可以把Continuation理解为[e_w_hole, cont]的二元组,完成当前的e_w_hole的求值后,把结果填补给下一个cont的hole,直到cont是halt停机为止。比如

(+ 1 (+ 2 (+ 3 4)))

(+ 3 4)的continuation是 [(+ 2 ...), cont1],而cont1则是[(+ 1 ...), halt]。

那么CPS就是把continuation作为一个函数显式地暴露出来,这个函数的参数就是hole,当我们apply这个continuation(函数)就是在填补这个hole,并进行进一步的计算。

上面的代码很容易转换为CPS(虽然加法操作是primitive的,但我们仍然可以自己编写一个CPS版本的k+来模拟,同时我们还有一个identity continuation作为halt):

(define k+ (lambda (x y k) (k (+ x y))))
(define id (lambda (x) x))
(k+ 2 3 (lambda (five) (k+ 1 five id)))

至于call/cc其实并不属于pure CPS的一部分,call/cc是语言提供给程序员用以获得当前continuation的机制。

上面的(+ 1 (+ 2 3))例子也可以用call/cc来实现:

(+ 1 (call/cc (lambda (k) (k (+ 2 3)))))

这时候k便是当前的continuation,也就是(+ 1 ...)。 通过获取当前的continuation,实际上获得了『此刻』以后所有的计算过程,于是便可以做一些有意思的事情,比如nont-deterministic的amb,比如coroutine等。

因为最少形式的纯CPS的程序只需要有lambda和function application,因此CPS程序中所有的递归函数调用都是尾递归。

比如正常map函数可以这样实现:

(define (map f xs)
  (if (empty? xs) '()
      (cons (f (first xs)) (map f (rest xs)))))
(map (λ (x) (+ x 1)) '(1 2 3))

在这里并不是尾递归,因为在第3行在(rest xs)上调用完map之后我们仍然有continuation要做,就是和(f (first xs))的结果cons起来。

而CPS版的map则是:

(define (map-k f xs k)
  (if (empty? xs) (k '())
      (f (first xs) (λ (v) (map-k f (rest xs)
                                  (λ (rest-v) (k (cons v rest-v))))))))
(map-k (λ (x k) (k (+ x 1))) '(1 2 3) (λ (x) x))

可以看到,在map-k中,所有的函数调用都是尾递归,也就不存在由递归引起的stack空间的消耗(在支持tail-call opt的语言中)。

CPS在在过去是函数式语言常用的IR,在编译和程序分析中有很多应用。当程序被转换为CPS的时候,Continuation是直接在lexical scope中暴露出来的,而一切control flow的转移都通过continuation来实现,这样可以直接进行control flow analysis。在进行Partial Evaluation的时候CPS也可以获得更好的特化效果。

但是CPS的可读性太差了,后来direct style的A-Normal Form在编译和程序分析中流行起来。而ANF和CPS是等价的,A-Normalize的过程等价于CPS convert->Beta normalize->un-CPS convert,请参考The Essence of Compiling with Continuation。

CPS同Static Single Assignment也是correspondence的,在CPS中每个变量都通过lambda来引入,变量的mutation也是通过新的continuation来引入;正对应于SSA中每个变量只被赋值一次,并dominate接下来的use,而Phi Node则在CPS中通过对于同一个cont传入不同的值来实现。可参考A Correspondence between Continuation Passing Style and Static Single Assignment Form。

CPS同Monad也是等价的,理论上任何Monad都可以通过等价的CPS形式表达出来,这部分可以看The Essence of Functional Programming。

很久以前听说CPS可以用来表达一切你能想到的控制流,所以我就尝试了一下。我做了个小语言(tinymoe/StandardLibrary.txt at master · vczh/tinymoe · GitHub),在语法上支持CPS变换,然后除了select-case和地柜之外什么都不提供,最终用这两个东西(见链接,这是我用这个语言写的一个库)做出了所有的if、for、try-catch、甚至是有些人莫名其妙的引以为豪的coroutine等基础设施。然后我把CPS变换后的代码编译成了C#,在实际上做到了,凡是尾递归都会自动在stack上变成循环的这样一个东西。


实现的时候我山寨了x86处理器做exception handling的小技巧,把很多continuation串成了一个链表,然后就可以在上面选择你要jump到什么地方去了。在看这段代码的时候,不要通过debug,而要通过在纸上推导来看,不然是看不懂的(除非你原本就明白)。


经典的CPS定义就是说所有闭包都返回void,算出来的结果用调用一个参数指向的闭包返回,我的tinymoe作为一个教学项目也是这么做的,概念都很直接。不过实际上这也只是一个概念,就跟说lambda-calculus跟图灵机等价的这么个说法差不多。你当然可以做,不过实际上没什么意义。真正在处理语言的时候,很少会出现真正的continuation,都是用很多奇怪的技巧,最后产生一些高度inline后的代码,然后就什么都看不出来了,就像C#的async-await和yield return一样。