CPS Lecture

原文链接
目前出版的书籍里还没有正确做出这个题的。

(f (g (h i) j) k) 的哪一部分先被完成？ (h i) , 因为它必须在 (g (h i) j) 可以应用之前先完成求值。
(f (g (h i) (j k))) 呢？Scheme没有指定参数的求值顺序，因此可以是 (h i) 或 (j k)。
让我们来行动。(h i (lambda (hi) ...)) 我们假定 hi 是应用 (h i) 的结果。然后， 我们把其他内容放到 ... 的位置：

(f (g (h i) (j l)))

就变成了

(h i (lambda (hi) (f (g hi (j l)))))

(lambda (hi) (f (g hi (j l)))) 就是一个连续(continuation)。hi在连续中只出现一次，因为hi的目的仅仅是替代 (h i) 。

让我们以CPS形式重写rember。首先直接形式：

(define rember8
  (lambda (ls)
      (cond
        [(null? ls) '()]
        [(= (car ls) 8) (cdr ls)]
        [else (cons (car ls) (rember8 (cdr ls)))])))

规则一: 在想要CPS的定义中，只要看到lambda，就必须添加一个参数，然后处理它的体。

(lambda (x ...) ...)  =>  (lambda (x ... k) ...^)

让我们从添加k到外层的lambda开始：

(define rember8
  (lambda (ls k)
    (cond
      [(null? ls) '()]
      [(= (car ls) 8) (cdr ls)]
      [else (cons (car ls) (rember8 (cdr ls)))])))

现在，对于程序的其他部分，我们引入一条新的规则。

规则二：不要管那些小部件。
小部件就是那些我们知道它会马上终止的东西。
如果我们知道它会被求值，就不要管它。
如果我们知道它·可能·会被求值，就将它传递给k。
第一个好例子就是 (null? ls) ，在条件从句的第一行。我们知道它会被求值，并且它是一个小部件，所以我们不管它。
那么被作为返回值的 '()呢？第二条规则的另一部分：如果一些小部件可能被求值，我们就将其传递给k。
在应用第二条规则到条件从句第一行后，我们得到了：

(define rember8
  (lambda (ls k)
    (cond
      [(null? ls) (k '())]
      [(= (car ls) 8) (cdr ls)]
      [else (cons (car ls) (rember8 (cdr ls)))])))

cond 的第二行同样有作为测试和返回值的小部件，所以我们如同第一行一样处理。

(define rember8
  (lambda (ls k)
    (cond 
      [(null? ls) (k '())]
      [(= (car ls) 8) (k (cdr ls))]
      [else (cons (car ls) (rember8 (cdr ls)))])))

条件else，没有作为返回值的小部件，所以我们需要制造一个新的连续:

(define rember8
  (lambda (ls k)
    (cond
      [(null? ls) (k '())]
      [(= (car ls) 8) (k (cdr ls))]
      [else (rember8 (cdr ls) (lambda (x) (cons (car ls) x)))])))

我们还没有完全搞定，因为现在在连续的体内有了些小部件。所以我们把它传递给k:

(define rember8
  (lambda (ls k)
    (cond 
      [(null? ls) (k '())]
      [(= (car ls) 8) (k (cdr ls))]
      [else (rember8 (cdr ls) (lambda (x) (k (cons (car ls) x))))])))

现在就全部CPS了，但我们如何调用它呢？我们需要一个k来作为参数传递。因为 (rember8 '() k) 应该是 '()，k 可以是(lambda (x) x)：

> (rember8 '(1 2 8 3 4 6 7 8 5) (lambda (x) x))

我们在程序里可以观察到什么属性？

首先，所有的非小件调用都是尾调用。下面是用星号扩起来的尾调用：

(define rember8
  (lambda (ls k)
    (cond
      [(null? ls) (*k* '())]
      [(= (car ls) 8) (*k* (cdr ls))]
      [else (*rember8* (cdr ls) (lambda (x) (*k* (cons (car ls) x))))])))

为什么null?,=,car,cdr,cons不算？因为它们仅仅是小部件，当我们合并小部件时，结果依然是小的......

第二，所有的参数都是小部件。是的，即便是else行中的lambda，因为所有的lambda都是小部件。

注意这个在本质上是一个C程序。我们需要做的只是将连续转换为数据结构（记得我们对闭包做的同样的事）。

让我们追踪一下(rember8 (lambda (x) x))

ls                       |   k
'(1 2 8 3 4 6 7 8 5)   |   (lambda (x) x) = id
'(2 8 3 4 6 7 8 5)     |   (lambda (x) (id (cons 1 x))) = k2
'(8 3 4 6 7 8 5)       |   (lambda (x) (k2 (cons 2 x))) = k3

一但我们遇见了8， 就应用 (k (cdr ls)) 这里k是k3，ls 是 '(3 4 5 6 7 8 5)

(k3 '(3 4 6 7 8 5)) = (k2 (cons 2 '(3 4 6 7 8 5)))
(k2 '(2 3 4 6 7 8 5)) = (id (cons 1 '(2 3 4 6 7 8 5)))
(id '(1 2 3 4 6 7 8 5)) = '(1 2 3 4 6 7 8 5)

然后就完成了。

让我们尝试一个更复杂的程序multirember8。它除了去除第一个8，还要去除剩下所有的8.

(define multirember8
  (lambda (ls)
    (cond
      [(null? ls) '()]
      [(= (car ls) 8) (multirember8 (cdr ls)))]
      [else (cons (car ls) (multirember8 (cdr ls)))])))

现在我们从之前的rember8开始CPS它：

(define multirember8
  (lambda (ls k)
    (cond
      [(null? ls) (k '())]
      [(= (car ls) 8) (multirember8 (cdr ls))] ;; uh-oh~
      [else (multirember8 (cdr ls) (lambda (x) (k (cons (car ls) x))))])))

我们需要对第二行做什么？因为multirember8需要两个参数，我们需要对它传入一个连续。

(define multirember8
  (lambda (ls k)
    (cond
      [(null? ls) (k '())]
      [(= (car ls) 8) (multirember8 (cdr ls) (lambda (x) (k x)))]
      [else (multirember8 (cdr ls) (lambda (x) (k (cons (car ls) x))))])))

但是，(lambda (x) (k x))做了什么呢？它取任意值，然后将其传递给k。这就是全部的表达式，所以它等价于k。

Eta规约： (lambda (x) (M x)) = M 如果x不是自由变量，且M保证可以终止。M是任意满足以上条件的表达式，不仅限于单个变量比如k。

所以，只要你看见一个尾调用，都不需要考虑eta。只要把k传递给它。