在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.”
- (/ (- x 3) 10)
那么,什么叫做CPS——Continuation Passing Style呢?CPS就是指将隐式传递给(关联于)某个函数调用的continuation显式地传递给这个函数。对于上面的例子,如果我们将“-”函数改写成现实传递continuation的版本,那就是:
- (define (my-minus x k) (k (- x 3)))
- (my-minus 10 (lambda (v) (/ v 10)))
也就是说,CPS使得一个函数可以传递多个计算结果给其continuation,因为实现continuation的函数可以有任意数量的参数——当然,这也可以用values函数来实现。另外,CPS允许向一个函数传递多个continuation,这样就可以根据不同的情况来进行不同的后续计算。也就是说,通过CPS,我们可以对一个函数的执行过程进行控制(flow control)。“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.”
为了加深一下印象,让我们来看看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 '())))
- [f (lambda (x k) (k (cons 'a x)))]
-
[g (lambda (x k) (f x
-
(lambda (v)
- (k (cons 'b v)))))]
最后,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)))]))))))
- (lambda (v) (k (* (car ls) v)))
-
(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)
-
(define retry #f)
-
-
(define factorial
-
(lambda (x)
-
(if (= x 0)
-
(call/cc (lambda (k) (set! retry k) 1))
- (* x (factorial (- x 1))))))
-
(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)
-
(define reciprocals
-
(lambda (ls)
-
(call/cc
-
(lambda (k)
-
(map (lambda (x)
-
(if (= x 0)
-
(k "zero found")
-
(/ 1 x)))
- ls)))))
首先,自己实现一个非CPS版本的map函数map1:
-
(define map1
-
(lambda (p ls)
-
(if (null? ls)
-
'()
-
(cons (p (car ls))
- (map1 p (cdr ls))))))
-
(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)))
总结一下,当使用CPS来取代call/cc或者使用CPS时,如果函数中有对含有CPS的函数的调用,那么,传递进去的continuation或者作为函数,应用到传递来的参数上(非尾部调用);或者作为一个返回值(尾部调用);如果没有调用含有CPS的函数,则将其应用到返回值上。