Continuation Passing Style

By guenchi at 2018-02-06 • 0人收藏 • 224人看过

Continuation Passing Style

一个 CPS 的例子

即使没有 call/cc, Scheme 同样可以使用 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 '())))

这里有几个看不到的 continuation. 我们从最开始的函数调用说起,

  • 在调用 h 时,也就是这句:

(cons 'd (h '()))

这里的 continuation 是说:“我想使用参数 '() 调用 h, 得到它 的返回值(起个名字叫v吧), 然后我把 (cons 'd v) 返回给我的调用 者。

  • 在函数 h 内部调用 g 时的 continuation 是说:“用参数 (cons 'c x) 调用 g, 然后把它返回的值返回给我的调用者。”

  • 在函数 g 内部调用 f 时的 continuation 是说:“用参数 x 调 用 f, 得到它的返回值 v, 然后把 (cons 'b v) 返回给我的调用 者。

  • 函数 f 的 continuation 是说:“把 (cons 'a x) 返回给我的调 用者。”

于是,我们就可以把这些 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))))

这里每个函数多了一个参数 k, 表示一个 continuation。

看我们调用 h 的地方:

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

我把 (lambda (v) (cons 'd v)) 作为参数 k 的值传递给了 h, 就 是在告诉 h:“我想得到你的返回值 v,然后把 'd 和 v cons 在一 起,然后返回给上一层调用。这样 h 就可以在内部调用这个 k,把 应该返回的值,按照调用者的意图处理。这里,“调用者的意图”就 是 continuation。

接着看:h 调用 g 时,把 k 直接传递给了 g, 意思是说:“g, 你 的返回值,我将把它原封不动返回给我的调用者。” 这样,g 想返 回的时候就调用这个 k, 这样就会把值原封不动传递给 h 的调用者, 也就是最上层调用。

g 调用 f 时,使用了 

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

作为第二个参数,这是说:“f, 你返回给我的值 v, 我将把 'b 和 v cons 在一起(cons 'b v),然后把它返回给我的调用者。”

f 没有调用其它函数,所以它只是说:“得到 (cons 'a x) 的值, 然后把它返回给我的调用者。”

CPS 的用途

看起来 CPS 是把事情搞的很复杂。上面这个例子当然是不恰当的使 用 CPS。CPS 可以实现所有 call/cc 能实现的功能,但是你的程序 有可能需要完全重写。

所有的 

   thunk1
   (call/cc (lambda (x) ...))
   thunk2

都可以被改写为:

((lambda ((lambda (v) thunk1 v thunk2)) ...))

但是,这个 thunk1 和 thunk2 到底有多长?它们有可能是经过了很 多次函数嵌套调用到达 call/cc 的,如果要使用 CPS,这些函数全 部要加一个参数 k,就像上面的例子。这是不实际的。

但是 CPS 有某些 call/cc 没有的功能。

  • CPS 能实现多参数 continuation,而 call/cc 不行。举个例子:

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

这里,函数 car&cdr 接受一个两个参数,第一个参数是一个 pair p, 第二个参数是一个 continuation k. 它返回

(k (car p) (cdr p))

也就是说,我把 (car p) 和 (cdr p) 作为参数传递给 k, 随便 k 是干什么的。

这样,如果用 

(lambda (x y)
    (list y x))

作为 k,传递给 car&cdr,那么意思就是说:“亲爱的car&cdr函数, 你返回给我的两个值 x 和 y,我将要把它们作为 list 的参数,我 将要把 (list y x) 返回给我的调用者。

另外两个,cons 和 memv 也很好理解了。

  • CPS 能够传递多个 continuation,函数可以按情况选择把结果交 给哪一个. 举个例子:

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

调用 integer-divide 的时候,我们传递两个 continuation 给它, 第一个是在成功的时候使用的,是说:“把返回值做成一个 list 返 回给我的上层。” 第二个是在失败的时候使用的,是说:“把返回 值原封不动返回给我的上层。”


登录后方可回帖

登 录
信息栏

Scheme中文社区

推荐实现 ChezScheme / r6rs / r7rs large
theschemer.org
Q群: 724577239

精华导览

社区项目

包管理器:Raven
HTTP服务器:Igropyr (希腊火)
官方插件:vscode-chez

社区目标:

完善足以使Scheme工程化和商业化的库,特别是开发极致速度的Web服务器和ANN模块。

一直以来Scheme缺少一个活跃的中文社区,同时中文资料的稀少,导致大多数因为黑客与画家和SICP而接触Scheme的朋友,在学完SICP后无事可做,不能将Scheme转换为实际的生产力。最后渐渐的放弃。
同时Chicken等实现,却因效率问题无法与其他语言竞争。本社区只有一个目的,传播Scheme的文明之火,在最快的编译器实现上,集众人之力发展出足够与其他语言竞争的社区和库。


友情链接:

Clojure 中文论坛
函数式·China


Loading...