Continuation 和 call/cc

By guenchi at 2017-12-04 • 0人收藏 • 360人看过

http://sighingnow.github.io/编程语言/continuation_and_call_cc.html


Continuation,延续性,是对程序的控制状态/流程的抽象表达,Continuation 使得程序的控制流程具体化。

Current continuation,也就是 continuation of the computation step,指的是源自于程序当前运行点的一种 continuation。Scheme中,在代码某处调用call/cc后,产生了一个等待着参数的过程,这个参数是程序在该处的上下文, 在参数之后的程序就叫做 current continuation。Continuation 一词也指 first-class continuations, 指的是编程语言中使得编程语言具有保存任意一点的运行状态,并从之后的程序中回到这一状态(可能多次返回)的可能 的结构和概念。

First-class continuations

First-class continuations 指的是一门编程语言能够完全控制程序的执行顺序的能力。程序既可以跳转到一个将要调用 当前函数的函数,也可以跳转到之前已经退出的函数。first-class continuation可以被看作是保存程序的执行状态(仅仅 是上下文,而不是程序数据,区别于 processing image)。First-class, 是指 Continuation 可以被当作参数传递和 作为返回值。

一个解释 continuation 与普通的程序调用和返回的区别的例子:

此处,我们并没有调用一个用来 make sandwich 的函数并返回,而是调用了一个 make sandwich with current continuation 的函数,然后 create the sandwish,最后返回到之前离开时的continuation(fron of the refrigerator)。

Scheme的call/cc

Scheme是第一个提供Continuation支持的产品级编程语言,Scheme提供了使用call/cc(call-with-current-continuation) 的控制流运算符,call/cc的参数是只能接受一个参数的函数。在Scheme中,Continuation被表达为一个函数, 假设 call/cc 捕捉了当前的 continuation,并绑定到 lambda 的参数 cc,那么在 lambda 函数体内,一旦 cc 被直接或间接的作为过程调用,那么 call/cc 会立即返回,并且提供给 cc 的参数即为 call/cc 的返回值。

call/cc 本质上其实是非本地返回(non-local return),其他的例如 setjump/longjump, exception 等机制也属于 non-local return 的范畴。call/cc 机制主要用来实现一些复杂的流程控制结构。Scheme并没有提供像C语言那样的break语句,可以用 call/cc来实现退出函数的功能。在过程的入口调用call/cc,将这个函数体都放在call/cc的参数里。在需要中途退出的地方 参数调用continuation,就可以直接退出函数。本质上是借助调用continuation将会把上下文设置为执行call/cc的位置,即 调用call/cc之后的下一条语句。


(define (test e cc) (if (zero? e) (cc "find zero")))(define (search-zero test lst)
  (call-with-current-continuation
    (lambda (ret) (for-each (lambda (e) (test e ret) (display e)) lst))))(display (search-zero test '(-3 -2 -1 0 1 2 3)))

执行的输出结果(R5RS):

-3-2-1find zero

我们使用 call/cc 来实现一个功能类似于 Haskell 的 product 的函数:

(define product
  (lambda (ns)
    (call-with-current-continuation
      (lambda (exit)
        (let f ((ns ns))
          (cond ((null? ns) 1)
                ((= (car ns) 0) (exit "zero"))
                (else (* (car ns) (f (cdr ns))))))))))(product '(1 2 3 4 5 6))(product '(1 2 3 0 4 5 6))

为了方便叙述,我们称包含call/cc的函数为callee,在该函数外部,无参数调用continuation的函数为caller。 关于call/cc的代码执行流程,在首次运行callee函数时,cc会被赋值,用于保存一个上下文环境。当在caller中无 参数调用continuation时,拿之前保存的上下文环境来运行call/cc的参数函数,并一直执行到函数的callee函数的末尾, 以callee函数的值作为返回值,返回给caller函数,call函数继续执行。下一次在caller中无参数调用continuation, 接着用之前保存的上下文环境来运行call/cc的参数函数,知道callee末尾,返回值给caller。下面的例子可以很好地 说明这个过程:

(define the-continuation #f) ; dummy value - will be used to store continuation later(define (func)
  (let ((x 0))
    (call-with-current-continuation
      (lambda (cc) (set! the-continuation cc)))  ; set cc to the continuation.
    (set! x (+ x 1)) x))(func)(the-continuation)(the-continuation)(the-continuation)

运行结果:

1 2 3 4

如果调用(the-continuation)之前不先调用(func),the-continuation就无法被初始化,后面调用(the-continuation)就会出错。

call/cc 的引用透明性

引用透明性(referential transparent)是纯函数式编程语言的重要特性,而是用call/cc,可以写出非引用透明性的函数:

(define (get-cc) (call/cc (lambda (c) c)))

get-cc 函数捕捉到当前的 continuation,然后返回,显然,这个函数的返回值会受到上下文的影响。

Welcome to DrRacket, version 6.2 [3m].
Language: R5RS; memory limit: 128 MB.
> ((get-cc) 10)
. . application: not a procedure;
 expected a procedure that can be applied to arguments
  given: 10
  arguments.:
> (define x (get-cc))
> x
#<continuation>
> (x 10)
> x
10

(get-cc) 获取它这个位置上的 continuation, (get-cc) 自己被用来做了什么事,它返回的 continuation 就 对别人做同样的事。 经过define之后,x 获得一个 continuation,这个continuation 的作用就是获取一个值, 然后返回这个值,当以参数 10 来调用 x 时,continuation 返回一个值:10,并把这个值绑定到 x,x 被重新绑定, 变成了数字10。但是直接以((get-cc) 10) 来调用的时候,(get-cc) 被当成了函数调用,显然就会出现错误了。

(get-cc) 的非引用透明性来源于它的语义,它总是捕捉当前的 continuation 并返回之。可以这么理解 call/cc,它 可以出现在任何一个本应是表达式的地方(它占了表达式的位置)。凡是表达式都要求值,并且还要求它的后续表达式的 值,我们通过call/cc,可以在该表达式出现的地方捕捉(catch)到该表达式的后续操作。被捕捉到的后续操作即为 continuation,调用捕捉到的 continuation 可以回到过去。但是注意调用 continuation 和非本地退出的区别,后者 是在 call/cc 的函数体内(直接或间接)调用捕捉到的 cc,这是 continuation 的特殊用法,它能立即退出,而且可以 在非本地退出;而前者是在相应 continuation 的 call/cc 之外调用,它的作用就是重复后续操作。

  • (let ((x (get-cc))) (x (lambda (unused) “result”)))

  • (((get-cc) (lambda (x) x)) “result”)

根据上面的原理不难理解,这两个表达式的值都是 "result"。

call/cc 模拟多任务

多任务控制流的一个关键就是,保存每个任务的上下文,让它切出去再返回的时候能接着执行,就像没有发生过切换一样。 这个任务,continuation 完全胜任。生产者-消费者问题是检验多任务机制的经典问题,我们可以用 continuation 模拟这个过程。利用call/cc来捕获上下文,利用调用continuation来在不同的上下文之间切换。

#lang racket(define dish #f)(define (put! fruit) (set! dish fruit))(define (get!) (let ((fruit dish)) (set! dish #f) fruit))(define (consumer do-other-stuff)
  (let loop ()
    (when dish
      (printf "C: get ~a~%" (get!))
      (set! do-other-stuff (call/cc do-other-stuff))
      (loop))))(define (producer do-other-stuff)
  (for-each (lambda (fruit)
              (put! fruit)
              (printf "P: put ~a~%" fruit)
              (set! do-other-stuff (call/cc do-other-stuff)))
            '("a" "b" "c" "d" "e")))(producer consumer)

call/cc的实现

在Scheme中,运行效率更高的continuation可以通过更低级的直接操作栈空间的方法来实现,但这仅仅是一种优化。在Scheme 中,当我们使用了 CPS 后,call/cc可以被如下的等价表达式替代:

(lambda (f k) (f (lambda (v k0) (k v)) k))

在这个式子中,k 是需要保存的continuation,(lambda (v k0) (k v)) 用来重新保存(restore) continuation。

Call-with-current-continuation for C programmers 一文介绍了C语言中的 setjump/longjump 机制与 continuation 的异同,并从更加 low-level 的方式阐述了大多数主流 Scheme 解释器的 call/cc 的实现细节。Continuation 操作程序控制流的原理与命令式语言中的goto有着本质的不同。 Parent pointer tree (也作Spaghetti stack) 就是编译器 中实现call/cc,进行垃圾回收的一种方法。在并发领域,Coroutine就是基于Continuation实现的。Continuation可认为 是对PCB的抽象,其实它就是函数当前的执行栈,并且是实实在在可以被保存的东西,因此,很容易通过CPS来实现协程、 non-local-return 等。


登录后方可回帖

登 录
信息栏

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...