論壇

在第2章里, 我们运用环境这一概念对于绑定和过程的行为进行了建模. 在第3章里, 我们运用抽象内存这一概念对于变动和参数传递进行了建模. 在本章中, 我们将运用延续这一概念对于编程语言的控制行为进行建模.

延续是对于控制的抽象, 包裹了剩余的计算. 这个定义并不容易凭空理解, 让我们慢慢解释.

以下是两个典型的Scheme过程, fact和gcd.

几乎每个Schemer都知道gcd是尾递归的, 而fact不是, 但不一定每个Schemer都能解释清楚原因.

让我们观察这两个过程的调用实例.

可以看到, 在对于(fact 3)求值的过程中, 先是膨胀, 后是收缩. 这与对于(gcd 9 6)的求值过程很不一样, 因为不论怎样调用gcd, 其计算过程只会像一条直线. 而且, 可以想见, 随着自然数n的增长, (fact n)的最大膨胀程度也会线性地增长.

很容易解释fact的行为, 因为对于非零的自然数n, (fact n)就等价于(* n (fact (- n 1))), 在对于(fact (- n 1))求值的过程中, 系统必须「记住」要给最终的结果乘上n, 这种记忆, 或者说上下文, 不断地累积, 直到对于(fact 0)求值后开始收缩.

我们将这样的控制上下文称为延续, 它代表了当得到一个结果的时候, 之后该做什么以完成整个计算. 如果在求值过程中延续是有界的, 那么就称其呈现了迭代计算行为, 否则的话就称其呈现了递归计算行为. 计算行为和实际的形式无关, 例如虽然表面上fact和gcd都是递归的, 但是fact呈现了递归计算行为, 而gcd呈现了迭代计算行为.

所谓的延续传递风格变换 (CPS conversion/transformation) 可以使我们的讨论变得更加显然. 延续传递风格 (continuation-passing style) 是一种显式传递延续的风格, 也就是说, 将控制暴露出来.

这里的k均代表延续. 可以看到, gcd-cps不用修饰其延续, 而fact-cps需要记住给结果乘上n才行. 现在fact-cps也是尾递归的了, 但是本质上计算没有得到任何的简化, 因为它只是将原本在台面下发挥作用的延续搬到台面上而已.

接着, 请读者阅读fact-aps.

这里的a代表accumulator (累积器), 因此aps的意思是accumulator-passing style (累积器传递风格). 读者应该明白对于每个自然数n, (fact-aps n 1)就等于(fact n). 实际上, 读者可以将a视为对于延续的一种「表示」, 因为fact-cps的延续只是在累积需要乘上的一连串数字, 而这些数字之积就是a (如果最初的a是1的话). 这个想法不仅限于fact-cps和fact-aps.

关于对于每个自然数n和过程k, (fact-cps n k)等价于(k (fact n)), 以及关于对于每个自然数n和整数a, (fact-aps n a)等于(* (fact n) a)的证明, 见附录.

让我们再看一个例子, 比上面两个更复杂一些.

实际上, 按照语义, 先对于(fib (- n 1))求值还是先对于(fib (- n 2))求值都是可以的, 这也正是高级编程语言的优美之处, 它让我们从显式指定计算顺序中解放出来. 不过, 如果我们要将fib变换为延续传递风格的话, 我们就必须考虑安排顺序, 且非得给每个中间结果命名. 这听起来很像汇编, 不是吗? 的确, 在控制方面, 延续传递风格更接近于汇编而不是一般的高级编程语言. 关于以延续传递风格作为中间表示的编译已经有了很长的研究历史, 读者首先可以参考RABBIT: A Compiler for SCHEME以及Compiling with Continuations.