Enjoyable Continuations


基本的scheme内容不多说了,Friedman 为了讨论方便,搞了一个记号用来表示 escape,在函数后面加上^。这样表示的函数就具有了escape的性质,简单地说,会在计算完成后作为answer,不过这个表示方式并不在语言的标准里。

(* 3 (+ 4 5)) ; => 27
(* 3 (+^ 4 5)) ; => 9

如果考虑到id函数

(define I
  (lambda (x) x))

那么上面的计算可以等价为

(* 3 (I^ (+ 4 5))) ; => 9

这里还存在着control stack的问题,尽管计算的结果是相同的,但是栈却是不同的。

如果将匿名函数的表达赋予这样的性质,就得到了用于构造一般性escape procedure的算子 lambda^。Scheme里当然有能够创造escape procedure的手段。利用call/cc函数,可以捕捉到current continuation

(call-with-current-continuation e)

这个函数名很直白,但是它太长了,通常就简写为call/cc,在racket可以直接用call/cc

(call/cc e)

关于call/cc的用法,首先要记住的是这个调用的效果是(e k^),先来一个例子

(* (+ (call/cc
        (lambda (k^)
          (/ (k^ 5) 4)))
      8)
   3)

首先,k^在这里的形式是

(lambda^ (v)
  (* (+ v 8) 
     3))

其实就是延续传递的感觉,所以根据call/cc的结果,只要把5代入进去就可以了,结果是39.

更加有趣的事情包含在里面,如果对下面的表达式进行求值,可以得到求值结果是13

(+ (call/cc
     (lambda (k^)
       (begin
         (set! I k^)
         (display "inside body")
         5)))
   8)

一方面,这说明了Continuations是 first-class objects,但是另一方面也表明了一个问题,这里5这个值并没有显式地传给k^,但是却出现了我们想要看到的求值结果。

为什么呢?因为有 call/cc Law

(call/cc (lambda (k^) e))
; is equal to 
(call/cc (lambda (k^) (k^ e)))

所以上面的表达式也可以写成

(+ (call/cc
     (lambda (k^)
       (k^ (begin
             (set! I k^)
             (display "inside body")
             5))))
   8)

但是一定要注意到,这里用的是 lambda 而不是 lambda^ ,对于后面的情况,这个Law是不成立的。continuation被set!给保存了起来,这样一来,无论何时都可以直接再调用它。

很多语言里都有return关键字,可以在需要的时候直接进行函数返回,Scheme本身没有这项定义,但是完全可以根据call/cc来实现一个。假如现在需要在一个list中查找一个特定的值,找到后直接从循环或递归中跳出返回,可以这样写

(define (search wanted? lst) 
  (call/cc 
    (lambda (return) 
      (for-each (lambda (element) 
                  (if (wanted? element) 
                      (return element)
                      (void))) 
                lst) 
      #f)))

call/cc的基本概念就是这样子的,用它能搞出不少花样出来,比如协程,yield之类的特性,可以看看call/cc的wiki里面的内容。

再来看看CPS(Continuation-passing-style),就是所谓的延续传递风格。 在延续传递风格(CPS)中,函数都会额外带一个参数,表明当前求值的结果接下来要做些什么,这其实是scheme表达式求值时的关键部分。

During the evaluation of a Scheme expression, the implementation must keep track of two things:

(1) what to evaluate and
(2) what to do with the value.

所以这个额外的参数是要把continuation给表达出来的。wiki里有一个haskell的例子很有意思,可以先来看这个。

对于Pythagorean theorem的基本实现

pow2 :: Float -> Float
pow2 a = a ** 2

add :: Float -> Float -> Float
add a b = a + b

pyth :: Float -> Float -> Float
pyth a b = sqrt $ add (pow2 a) (pow2 b)

现在用CPS来改写,给每个函数多带一个参数,用来表示continuation

-- note that cont means Continuation
pow2' :: Float -> (Float -> a) -> a
pow2' a cont = cont (a ** 2)

add' :: Float -> Float -> (Float -> a) -> a
add' a b cont = cont (a + b)

sqrt' :: Float -> ((Float -> a) -> a)
sqrt' a = \cont -> cont (sqrt a)

pyth' :: Float -> Float -> (Float -> a) -> a
pyth' a b cont = pow2' a (\a2 -> pow2' b (\b2 -> add' a2 b2 (\c -> sqrt' c cont)))

其实不难发现这和Monad有相近之处,不过这个是后话了,相关内容在Philip Wadler的paper里。

现在用scheme重写一下,这次应该能很轻松理解了

(define (pyth& a b k)
  (*& a a (lambda (a2)
            (*& b b (lambda (b2)
                      (+& a2 b2 (lambda (c)
                                  (sqrt& c k))))))))

唯一需要解释的是,这里的函数都已经换成了相应的CPS版本,就像上面haskell代码那样。

比如我们来定义这里的 *&

(define (*& a b cont)
  (cont (* a b)))

其它的几个CPS风格的函数也是大同小异。

现在假设已经写好了二叉树的定义,来写一个把所有节点的值加起来的函数,如果遇到值为零的情况,结果返回零

(define sum-bst
  (lambda (t)
    (call/cc
     (lambda (return^)
       (letrec
           ((sum-bst(lambda (t)
                       (cond ((null? t) 0)
                             ((zero? (info t)) (return^ 0))
                             (else (+ (info t)
                                      (sum-bst (left t))
                                      (sum-bst (right t))))))))
         (sum-bst t))))))

不用call/cc,我们可以用CPS来改写它

(define sum-bst
  (lambda (t)
    (letrec
        ((sum-bst
          (lambda (t k)
            (cond
              ((null? t) (k 0))
              ((zero? (info t)) 0)
              (else (sum-bst (left t)
                             (lambda (result-left)
                               (sum-bst (right t)
                                        (lambda (result-right)
                                          (k (+ (info t)
                                                result-left
                                                result-right)))))))))))
      (sum-bst t (lambda (x) x)))))

到这里,我想CPS的基本内容也差不多比较清晰了。

Friedman的文章里还有不少其他的内容,包括提供的10道练习题,这些可能会给理解Continuation带来帮助。如果有时间的话,可以揣摩一番。