续延传递

2016-07-06 01:09:00

续延传递（Continuation Passing Style, CPS）是一种编程手法，不要相信我能够将它讲清楚——在敲这些字的时候，我刚刚开始看《The Little Schemer》的第八章的 multirember&co 这个函数的定义，而且是因为看不懂，所以才写此文。

阶乘

下面是阶乘函数的定义：

(define (factorial n)
(cond ((= n 1) 1)
(else (* n (factorial (- n 1))))))
如果看不懂这个函数的定义，就没必要再看下去了，应该先阅读 SICP 的第一章。

下面是阶乘函数的另一种形式的定义：

(define (factorial-cps n k)
(cond ((= n 1) (k 1))
(else (factorial-cps (- n 1) (lambda (v) (k (* v n)))))))
看不懂这个函数的定义，是正常现象，因为它是续延传递风格的函数。

不要理睬 factorial-cps 的定义，来看一下它的用法。下面的代码可以计算 3!：

(factorial-cps 3 (lambda (z) z))
6
下面是 factorial-cps 在接受实参 3 与 (lambda (z) z) 之后的执行过程：

第一步：

(factorial-cps 2 (lambda (v) ((lambda (z) z) (* v 3))))
第二步:

(factorial-cps 1 (lambda (v') ((lambda (v) ((lambda (z) z) ( v 3))) ( v' 2))))
第三步：

((lambda (v') ((lambda (v) ((lambda (z) z) ( v 3))) ( v' 2))) 1)
最后得到的这个表达式虽然复杂，但它只不过是让一个函数——三个逐层嵌套的匿名函数构成的函数作用于实参 1 而已。如果将这个表达式复制到 Guile 交互解释器中，求值结果为 6，恰好是 3!. 也就是说，这个表达式是真正的阶乘计算过程。factorial-cps 函数本身并未在阶乘方面进行任何计算，它所做的工作就是生成这个阶乘计算过程。

承诺链

虽然可以将 factorial-cps 的过程完全展开，代码中的任何一个局部都能够理解，但是依然不理解代码的完整含义。因为我们的思维里还没有完全的接纳续延的概念。

下面的代码

(factorial-cps 3 (lambda (z) z))
它作出了一个承诺：算出 3! 的结果后，我会将它传递给匿名函数 (lambda (z) z)。这个匿名函数只是简单的将参数作为返回值。

进入 factorial-cps 计算过程后，该函数会作出承诺：我要先计算　2!，然后将计算结果 v 交给一个匿名函数　(lambda (v) ((lambda (z) z) (* v 3)))，由这个函数负责算出 3! 的结果。

当 factorial-cps 接受了实参 2 与 (lambda (v) ((lambda (z) z) ( v 3))) 时，它承诺：我要先计算 1!，然后将计算结果 v' 交给匿名函数 (factorial-cps 1 (lambda (v') ((lambda (v) ((lambda (z) z) ( v 3))) (* v' 2))))，由这个函数负责算出 3! 的结果。

当 factorial-cps 传递接受实参 1 与 (factorial-cps 1 (lambda (v') ((lambda (v) ((lambda (z) z) ( v 3))) ( v' 2)))) 时，factorial-cps 的第一个谓词为真，于是，就得到了：

((lambda (v') ((lambda (v) ((lambda (z) z) ( v 3))) ( v' 2))) 1)
这是一条承诺链，随着递归层次的增加，这条承诺链会越来越长。当递归达到终点时，承诺链便建好了。接下来，以从新到旧的顺序完成每个承诺，便可得到 3! .

Fibonacci

下面是 Fibonacci 函数的定义：

(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1)) (fib (- n 2))))))
如果看不懂这个函数的定义，就没必要再看下去了，应该先阅读 SICP 的第一章。

下面是 Fibonacci 函数的续延传递版本：

(define (fib-cps n k)
(cond ((= n 0) (k 0))
((= n 1) (k 1))
(else (fib-cps (- n 1)
(lambda (v)
(fib-cps (- n 2)
(lambda (v')
(k (+ v v')))))))))
假设使用 fib-cps 计算 (fib n)：

(fib-cps n (lambda (z) z))
这行代码作出了第一个承诺：我要算出 (fib n)，将结果传给 (lambda (z) z)。

对于 (fib-cps n (lambda (z) z)) 这个任务，fib-cps 函数作出承诺：我要先算出 (fib (- n 1)) 的结果 v，然后将 v 传递给下面这个匿名函数：

(lambda (v)
(fib-cps (- n 2)
(lambda (v')
(k (+ v v')))))
这个匿名函数也是在作承诺：我先算出 (fib (- n 2)) 的值 v'，然后将 v' 传给下面这个匿名函数：

(lambda (v')
(k (+ v v')))
这个匿名函数也是在作承诺：我先算出 (+ v v')，然后将结果传给函数 k，而这里的 k 恰好是 (lambda (z) z)。

续延传递

假设使用 fib-cps 计算 (fib n)：

(fib-cps n (lambda (z) z))
(lambda (z) z)) 是一个续延，表示 fib-cps 函数在算出 (fib n) 的结果之后要做的事。这个几乎什么也没做的非常普通的匿名函数之所以能成为续延，是因为它接受的参数 z 是 fib-cps 在应用这个匿名函数之前得到的计算结果——函数本来要作为结果返回的值变成了这个函数的续延的参数了。

将一个函数的续延作为参数传递给这个函数，这就是续延传递。

来看：

(lambda (v)
(fib-cps (- n 2)
(lambda (v')
(k (+ v v')))))
这是 fib-cps 在计算出 (fib (- n 1)) 之后要做的事。这件事是什么呢？是 (k (+ (fib (- n 1)) (fib (- n 2))))，而 k 就是 fib-cps 在计算出 (fib n) 之后要做的事，即 (lambda (z) z)。

有什么用？

将原本很直白的

(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1)) (fib (- n 2))))))
写成

(define (fib-cps n k)
(cond ((= n 0) (k 0))
((= n 1) (k 1))
(else (fib-cps (- n 1)
(lambda (v)
(fib-cps (- n 2)
(lambda (v')
(k (+ v v')))))))))
这样做有什么好处？

注意 fib 与 fib-cps 的递归形式的不同，前者是符合人类思维模式的普通递归，后者是尾递归——函数的求值结果是其自身的应用。尾递归的好处是，编译/解释器有机会将其优化为不会导致栈溢出的形式。

非尾递归形式的递归函数，因为上层递归过程在下层递归过程返回计算结果之前不会退出，所以它们占据的栈空间不会被释放。这样，每执行一次递归都会消耗一部分栈空间——当递归深度过大时，栈空间会耗尽，导致运算过程中断。如果将这种递归形式改写为续延传递形式，那么它就变成尾递归了。由于尾递归函数，每次递归时，其上层递归过程已经完全执行完了，它们没必要再占据栈空间，因此编译器/解释器可以将它们所占用的栈空间释放——尾递归优化。

王垠写了 40 行我们看不懂的 Scheme 代码。据说这 40 行代码可以自动将非尾递归形式的递归函数『翻译』为续延传递风格的函数。如果真的是这样，这似乎是非常强大的技术。有了这种技术，再也不用担心递归会导致栈溢出。不过，fib-cps 虽然是尾递归的，但其运算效率可能还不及 fib！下面的 fib* 是效率更高的尾递归形式：

(define (fib* n)
(define (fib-iter a b count)
(cond ((= count 0) b)
(else (fib-iter (+ a b) a (- count 1)))))
(fib-iter 1 0 n))
这种尾递归形式可能不可能存在类似王垠 40 行代码的代码自动变换出来，它是基于动态规划方法构造出来的。基于动态规划方法所构造的运算过程通常与具体的问题密切相关。

事实上，fib-cps 只是从机器层面消除了递归栈，但逻辑上的递归栈依然是存在的，这个栈就是作为函数参数的续延，它会随着递归的深度不断的累积着。从机器角度来看，续延传递变换将递归过程所用的栈空间转换为存储递归过程的堆空间——前提是编译器/解释器不会将续延对象复制到栈空间再传递给函数，而是传递续延对象的引用。

也就是说，虽然基于续延传递变换，可以将任何递归函数变化为尾递归形式，但是这并非续延传递变换真正重要的应用场景。甚至可以说续延传递变换与尾递归没有必然联系，只不过续延传递变换恰好在形式上是尾递归而已。

那么续延传递变换真正重要的应用场景是什么？通过阶乘与 Fibonacci 函数的例子可以看出，续延传递风格的函数可以将特定的计算过程在递归函数的参数中积累起来。换句话说，基于续延传递，可以将特定的递归运算过程展开为一个层层嵌套的函数构成的表达式，就像在做泰勒展开运算一样，使得编译器/解释器有机会对展开结果进行优化。不过，我不清楚具体可以优化什么，这是函数式编程语言编译/解释器专家关心的事。