3.4 Continuation Passing Style

正如我们在上一节所讨论的那样，Continuation 等待每一个表达式的值。特别地，Continuation 与每个函数调用相关联。当一个函数非尾调用另外一个函数时，被调函数接收一个隐含的 Continuation，负责完成主调函数的函数体剩余的部分，并将结果返回给主调函数的 Continuation。如果是尾部调用，则被调函数只是简单地接收主调函数的 Continuation。

我们可以通过在每次调用中传递显式的封装在函数参数中的“做什么”来使 continuation 显式化。例如，在下面的表达式中

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

调用f的 continuation 将符号b cons 到f的返回值里，然后再将结果返回给g的 continuation. g的 continuation 与 h 的 continuation 是同一个，它的任务是将符号d cons 到它接收到的值里面。我们可以使用 continuation-passing style (延续传递风格，简称CPS) 重写, 通过传递显式的函数参数来替换隐式的 continuation

(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))))

像前面的例子中，h和g的隐含 continuation 一样，下面是显式传递给 h和g的 continuation：

(lambda (v) (cons 'd v))

它将符号d cons 到它接收到的值上面。类似地，传递给f的 continuation

(lambda (v) (k (cons 'b v)))

将符号b cons 到它接收到的值上面，然后再将结果传递给g的 continuation.

用 CPS 编写的表达式更复杂，但是这种编程风格有一些有用的应用。CPS 允许一个函数将多个结果传递给它的 continuation，因为实现 continuation 函数可以接受任意数量的参数。

(define car&cdr
  (lambda (p k)
    (k (car p) (cdr p))))

(car&cdr '(a b c)
  (lambda (x y)
    (list y x))) => ((b c) a)
(car&cdr '(a b c) cons) => (a b c)
(car&cdr '(a b c a d) memv) => (a d)

(返回多个值的用法也可以用"多重返回值"来实现，参见2.8节)。CPS 还允许一个函数视条件采取“成功”的或“失败”的 continuation, 两者可以接受不同数量的参数。例如下面的integer-divide函数，将第一，二个参数的商和余数传递给第三个参数，除非第二个参数是 0；如果第二个参数为 0, 则传递错误信息给它的第四个参数。

(define integer-divide
  (lambda (x y success failure)
    (if (= y 0)
        (failure "divide by zero")
        (let ([q (quotient x y)])
          (success q (- x (* q y)))))))

(integer-divide 10 3 list (lambda (x) x)) => (3 1)
(integer-divide 10 0 list (lambda (x) x)) => "divide by zero"

quotient函数返回两个数的商，截短取整。

Explicit success and failure continuations can sometimes help to avoid the extra communication necessary to separate successful execution of a procedure from unsuccessful execution. Furthermore, it is possible to have multiple success or failure continuations for different flavors of success or failure, each possibly taking different numbers and types of arguments. See Sections 12.10节 and 12.11节for extended examples that employ continuation-passing style.

在这一点上，你可能会想搞清楚 CPS 与通过 call/cc 所捕获的 continuation 之间的关系。事实证明，任何使用call/cc的程序都可以用 CPS 重写，而不需要调用 call/cc。但是可能需要对程序进行完全的重写（甚至有可能包括系统定义的预置函数）。在阅读下面的代码之前，尝试用 CPS 重写 75 页的product函数。

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

(product '(1 2 3 4 5) (lambda (x) x)) => 120
(product '(7 3 8 0 1 9 5) (lambda (x) x)) => 0

练习 3.4.1 重写2.1节的reciprocal函数，像integer-divide函数一样接受“成功”和“失败”两个 continuation.

练习 3.4.2 使用 CPS 重写 75 页的retry函数

练习 3.4.3 用 CPS 重写下面的表达式，避免使用call/cc。

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

(reciprocals '(2 1/3 5 1/4)) => (1/2 3 1/5 4)
(reciprocals '(2 1/3 0 5 1/5) => "zero found"

[提示：46 页有一个单列表版本的map定义]