[原]重新开始学习Scheme（8）：理解CPS

上一篇通过一些例子讲述了如何来理解continuation，这一篇讲主要讲述如何理解著名的Continuation Passing Style，即CPS。

在TSPL的第三章“”里，Kent Dybvig在对Continuation总结的基础上，引出了CPS的概念。因为Continuation是某个计算完成之后，要继续进行的计算，那么，对于每一个函数调用，都隐含了一个Continuation即：函数调用返回后，要继续进行的计算——或者是返回函数的返回值，或者是更进一步的计算。Kent在书中写道：

“In particular, a continuation is associated with each procedure call. When one procedure invokes another via a nontail call, the called procedure receives an implicit continuation that is responsible for completing what is left of the calling procedure's body plus returning to the calling procedure's continuation. If the call is a tail call, the called procedure simply receives the continuation of the calling procedure.”

也就是说，函数调用是都被隐式地传递了一个Continuation。如果函数调用不是尾部调用，那么该隐含的continuation将使用函数调用的结果来进行后续计算；如果是一个尾部调用，那么该隐含的continuation就是调用方调用该函数后的continuation。例如：

(/ (- x 3) 10)

对函数“-”的调用显然不是尾部调用，因此，该调用的continuation便是对该调用的返回值进行除以10的操作。

那么，什么叫做CPS——Continuation Passing Style呢？CPS就是指将隐式传递给（关联于）某个函数调用的continuation显式地传递给这个函数。对于上面的例子，如果我们将“-”函数改写成现实传递continuation的版本，那就是：

(define (my-minus x k) (k (- x 3)))

其中，参数k就是显式传递给函数的continuation。为了完成上述除以10的计算，对my-minus的调用就应该写成（假设x值为15）：

(my-minus 10 (lambda (v) (/ v 10)))

这里的匿名函数就是那个k。Kent还写道：

“CPS allows a procedure to pass more than one result to its continuation, because the procedure that implements the continuation can take any number of arguments.”

也就是说，CPS使得一个函数可以传递多个计算结果给其continuation，因为实现continuation的函数可以有任意数量的参数——当然，这也可以用values函数来实现。另外，CPS允许向一个函数传递多个continuation，这样就可以根据不同的情况来进行不同的后续计算。也就是说，通过CPS，我们可以对一个函数的执行过程进行控制（flow control）。

为了加深一下印象，让我们来看看TSPL上的例子：将下面这段代码用CPS改写。

(letrec ([f (lambda (x) (cons 'a x))]
         [g (lambda (x) (cons 'b (f x)))]
         [h (lambda (x) (g (cons 'c x)))])
  (cons 'd (h '())))

（关于letrec，可以参考）。首先，我们来改写f。因为f使用尾部调用方式调用cons，其后续计算是基于cons的返回结果的， 因此， 对于f可以改写为：

[f (lambda (x k) (k (cons 'a x)))]

再来看g函数。由于g函数以非尾部调用的方式调用了f，因此，g传递给f的continuation就不是简单地返回一个值，而是需要进行一定的操作：

[g (lambda (x k) (f x
                    (lambda (v)
                      (k (cons 'b v)))))]

需要注意的是，这里g的含义是：以x和一个continuation调用f，将所得的结果进行continuation指定的计算，并在该计算的结果上应用k。

最后，h函数通过尾部调用的方式调用g，因此，对h调用的continuation就是对g调用的continuation。那么，h可以改写为：

[h (lambda (x k)
     (g (cons 'c x) k))]

最后，将这些组合到一起：

(letrec ([f (lambda (x k) (k (cons 'a x)))]
         [g (lambda (x k) (f x (lambda (v) (k (cons 'b v)))))]
         [h (lambda (x k) (g (cons 'c x) k))])
  (h '() (lambda (v) (cons 'd v))))

通俗一点说来，continuation就像C语言里的long_jump()函数，而CPS则类似于UNIX里的管道：将一些值通过管道传递给下一个处理——只不过CPS的管道是函数级别而非进程级别的。这个观点大家让它烂在心里就好了，否则，如果某天你在宣扬这个观点的时候，不小心碰上一个（自诩的）Scheme高手，他一定会勃然大怒：Scheme为什么要跟C比较？Scheme和C的理念完全不一样！所以，低调，再低调。

理论上，所有使用了call/cc的函数，都可以使用CPS来重写，但Kent也承认，这个难度很大，而且有时候要修改Scheme所提供的基础函数（primitives）。不过，还是让我们来看看几个将使用call/cc的函数用CPS改写的例子。

(define product
  (lambda (ls)
    (call/cc
      (lambda (break)
        (let f ([ls ls])
          (cond
            [(null? ls) 1]
            [(= (car ls) 0) (break 0)]
            [else (* (car ls) (f (cdr ls)))]))))))

首先，将call/cc的调用从函数体中除去，然后，为product函数加上一个参数k，该参数接受一个参数。另外，因为product增加了一个参数，因此对f这个也需要增加一个参数。最后，在f的body里面调用f，也需要改写成CPS形式。因为对f的调用不是尾部调用，因此在f返回之前，需要进行计算，然后才是对该结果进行下一步的计算。此时需要的后续计算为：

(lambda (v) (k (* (car ls) v)))

对于cond的每个分支，都需要对其结果进行后续的k计算，这样，就得到了结果：

(define product/k
  (lambda (ls k)
    (let f ([ls ls] [k k])
      (cond [(null? ls) (k 1)]
            [(= (car ls) 0) (k "error")]
            [else (f (cdr ls)
                   (lambda (x)
                     (k (* (car ls) x))))]))))

需要注意的是，由于product/k是个递归过程，对于每个返回的值，都会有后续操作，因此需要对cond表达式的每个返回值应用continuation。

习题3.4.1是要求用两个continuation来改写reciprocal函数，如下：

(define reciprocal
  (lambda (x ok error)
    (if (= x 0)
        (error)
        (ok (/ 1 x)))))

(define ok
  (lambda (x)
    (display "ok ")
    x))
(define error
  (lambda ()
    (display "error")
    (newline)))

(reciprocal 0 ok error)
(reciprocal 10 ok error)

习题3.4.2要求用CPS改写的retry。

(define retry #f)

(define factorial
  (lambda (x)
    (if (= x 0)
        (call/cc (lambda (k) (set! retry k) 1))
        (* x (factorial (- x 1))))))

同样，需要将factorial改写成接受两个参数的函数，第二个参数为continuation。接下来，把对call/cc的调用去掉，改写成对k的使用。然后，根据对factorial递归调用的非尾部性，确定如何调用新的函数。结果如下：

(define factorial/k
  (lambda (x k)
    (if (= x 0)
        (begin
          ( retry/k k)
          (k 1))
        (factorial/k
         (- x 1)
         (lambda (v)
           (k (* x v)))))))

(factorial/k 4 (lambda (x) x))
(retry/k 2)
(retry/k 3)

习题3.4.3要求用CPS改写下面的函数：

(define reciprocals
  (lambda (ls)
    (call/cc
      (lambda (k)
        (map (lambda (x)
               (if (= x 0)
                   (k "zero found")
                   (/ 1 x)))
             ls)))))

这道题难度很大，因此Kent给出了提示：需要修改map函数为接受continuation作为额外的参数的形式。——至于原因，我也说不清楚。

首先，自己实现一个非CPS版本的map函数map1：

(define map1
  (lambda (p ls)
    (if (null? ls)
        '()
        (cons (p (car ls))
              (map1 p (cdr ls))))))

这里，当ls为空时，需要立刻对返回结果'()进行后续计算。而非空时，通过map1调用自身，并对结果进行后续计算。那这时就应该着重考虑这段代码：

(cons (p (car ls))
      (map1 p (cdr ls)))

根据对函数参数求值的顺序，有两种顺序来进行这段代码的计算。

• 当求值顺序为从左向右时

首先，它计算出(p (car ls))得到v1，其后续计算为(map1 p (cdr ls))得到v2，而后者的后续计算为(cons v1 v2)并返回该结果。那么，计算并得到v1及其后续计算如下：

(p (car ls)
   (lambda (v1)
     (map2/k p (cdr ls) k1)))

随即进行后续的k1计算，而k1为对v1和v2的后续计算：

(lambda (v2)
  (k (cons v1 v2)))

将这两个计算合并起来：

(define (map2/k p ls k)
  (if (null? ls)
      (k '())
      (p (car ls)
         (lambda (v1)
           (map2/k p (cdr ls)
                   (lambda (v2)
                     (k (cons v1 v2))))))))

• 当求值顺序为从右向左时

首先，它计算出(map1 p (cdr ls))得到结果v2，其后续计算为(p (car ls))得到v1，而后者的后续计算为(cons v1 v2)并返回结果。那么，计算得到v2及其后续计算为：

(map1/k p (cdr ls)
        (lambda (v2)
          (p (car ls) k1)))

随后进行对v2和v1的计算，即：

(lambda (v1)
  (k (cons v1 v2)))

最后将这两个计算合并起来：

(define map1/k
  (lambda (p ls k)
    (if (null? ls)
        (k '())
        (map1/k p (cdr ls)
                (lambda (v2)
                  (p (car ls)
                     (lambda (v1)
                       (k (cons v1 v2)))))))))

有了CPS的map函数之后，写出reciprocal的CPS形式就很简单了：

(define reciprocal1/k
  (lambda (ls k)
    (map1/k (lambda (x c)
              (if (= x 0)
                  (k "zero")
                  (c (/ 1 x))))
            ls
            k)))

其中，k是整个reciprocal1/k计算完成后的continuation，因此用于返回错误；而c则是计算完(/ 1 x)的continuation，只不过在这里也是k而已。另外，无论是用map1/k，还是map2/k，其结果应该是一样的。

总结一下，当使用CPS来取代call/cc或者使用CPS时，如果函数中有对含有CPS的函数的调用，那么，传递进去的continuation或者作为函数，应用到传递来的参数上（非尾部调用）；或者作为一个返回值（尾部调用）；如果没有调用含有CPS的函数，则将其应用到返回值上。