Print4D

Understanding Continuation

12 Dec 2013

花了不少时间,看了很多资料,终于把 Continuation 弄明白了。一上来就写 Continuation,好在关于 Continuation 的轮子还不多,而且大都不太好懂。所以我觉得还是应该再花一点点时间,试着尽可能地讲清楚关于 Continuation 的一些细节。


0. Continuation 是什么

Contination 最早出现在 Scheme 中,是一种流程控制的机制,实现诸如 return、break、goto、协程等功能。Continuation 被翻译成“延续”,像它的名字一样,一个延续中包含程序将要进行的计算,即函数调用。

为了能有一个大概的印象,举一个简单的例子:

(define f '())                                       ;; 0
(+ 2 (* 2 (call/cc (lambda (c) (set! f c) 1))))      ;; 1
(f 5)                                                ;; 2
;; => 12

第 1 条语句的含义是,将当前延续赋值给变量 f,但是当前延续是什么呢?既然延续表示程序中将要进行的函数调用,那么它应该是乘以 2,在加上 2。所以 (f 5) 返回 12。可以用一个函数来表示:

(lambda (val)
  (+ 2 (* 2 val)))

实际上,延续本质上就是一个函数,或者说闭包。


1. Continuation 的特性

一个稍微复杂的例子可以说明这四个特点:

(define f '())                                 ;; 0
(append (list 1 2 3)
        (list (call/cc (lambda (c)
                         (set! f c)
                         4))))                 ;; 1
;; => (1 2 3 4)
(f 5)                                          ;; 2
;; => (1 2 3 5)
(+ 1 (f 5))                                    ;; 3
;; => (1 2 3 5)

(define (current-cc)
  (call/cc (lambda (c) c)))                    ;; 4
(define x (current-cc))                        ;; 5
(x 0)                                          ;; 6
(display x)                                    ;; 7
;; => 0
((current-cc) 0)                               ;; 8
;; => raise error

语句 1 中使用 call/cc 抽取了当前延续,并且存放在 (lambda) 的参数 c 中。之后将 c,也就是当前的延续赋值给变量 f,由于过程中 c 没有被调用,所以 call/cc 顺序执行,call/cc 返回 4。程序最后返回 (1 2 3 4)

语句 2 中使用参数 5 来调用 f,注意,这里的 f 就是从语句 1 中抽取出来的延续。根据特性二,一旦延续被调用,立即返回,且返回值为调用延续的参数,在这里是 5。但这个 5 返回给哪里呢?根据特性三,此时程序跳转到了语句 1 所在的堆栈,5 成了其 call/cc 的返回值。之后程序继续执行,最终返回 (1 2 3 5)

既然语句 2 的返回值是一个 list,那么在语句 3 中使用这个 list 和一个整数来调用加法,为什么不会抛异常呢?因为特性三:一旦 f 被调用,当前程序立即被挂起,不再执行。

特性零表面上很好理解,其实很能让人迷惑。原因在于当前这两个字。“当前”的含义是:当 call/cc 被调用时,自其所在的位置,沿着它的调用者,一直到 top-level。也就是说“当前”取决在哪里被调用,而不是在哪里被定义。由此可以看出延续是不具备引用透明性的。

语句 4 到语句 8 是关于延续非引用透明性的演示。语句 5 中将 (current-cc) 赋值给 x,如果具有引用透明性的话,那么语句 6 和 8 应该是等价的。但实际上语句 6 正常执行了,语句 8 却抛出错误。这正是因为 call/cc 抽取的延续是基于被调用时程序上下文(确切地说是下文),而不是定义其的环境。

语句 5 (current-cc) 抽取的延续是这样的:

(lambda (k)
  (define x k))
;; 至于语句 5 中的延续为什么可以写成这样,在第 3 节“消除 call/cc”会提到

所以,语句 6 可以写成这样:

((lambda (k)
   (define x k)) 0)

这也解释了为什么语句 7 打印 x 的值会是 0。但是语句 8 中 (current-cc) 抽取的延续是这样的:

(lambda (k)
  (k 0))

语句 8 实际上是用 0 来调用 0,当然会抛出错误了。


2. Continuation 可以干什么

根据延续的四个特点,可以实现诸如 return、break、goto、协程等功能。

2.0. 实现 return

作为一门函数型语言,Scheme 是没有 return 语句的,每一个函数都会隐式地 “return” 一个值,这个值又传递给上一级函数调用,这样逐级返回,直到 top-level。这就是说,显示的 return 对于 Scheme 实际上是没多大用处的,但是为了展示延续的功用,我还是来实现一个 return。

(define (member? lst element)
 (define (member lst element return)
   (for-each (lambda (l)
               (if (equal? l element)
                   (return l))) lst)
   '())
 (call/cc (lambda (c)
            (member lst element c))))

(member? '(1 2 3 4 5) 3)
;; => 3
(member? '(1 2 3 4 5) 6)
;; => ()

这个例子是特性二和三的体现,当延续被调用是,call/cc,也就是 (member?) 的函数体,立即返回调用它的参数 l,不再执行之后的代码。这叫做 non-local exit。和 return 一样,break 也是一种 non-local exit,只是退到哪里的问题。

2.1. 实现生成器

(define (make-next lst)
  (define (next-i lst return)
    (for-each (lambda (l)
                (call/cc (lambda (c)
                           (set! next-i c)
                           (return l))))
              lst) "no element")

  (define (next)
    (call/cc (lambda (c)
               (next-i lst c))))
  next)
(define f (make-next '(1 2 3 4)))
(f)
;; => 1
(f)
;; => 2
(f)
;; => 3
(f)
;; => 4
(f)
;; => "no element"

这个例子比 return 要复杂一些,它有两个 call/cc,(next) 中使用 call/cc 的是为了实现 return。而 (next-i) 中的 call/cc 要稍稍麻烦一点,当第一次调用 (f),(f) 内部会调用 (next-i),这时的 next-i 是 (make-next) 中定义的普通函数,函数中 (for-each) 首先迭代 lst 的第一个元素,然后抽取当前延续,保存到变量 c 中,之后再将 c(延续)赋值给 next-i,最后返回 lst 的第一个元素。把 c 赋值给 next-i 之后,next-i 就不再是之前 (make-next) 中定义的那个函数了,而是当前的延续。所以,当 (next-i) 第二次被调用,程序回到第一次调用 (next-i) 时的运行堆栈上,接着当时返回第一个元素地方继续执行,即 (for-each) 迭代第二个元素,然后再次保存当前延续到 next-i,最后返回第二个元素。类似的,直到第五次调用 (next-i) 返回 “no element” 。

2.2. 协程

前面两个例子,其实都不是非延续不能实现的。不使用延续,程序也可以很顺利地 return;使用闭包,也可以很轻易地实现生成器。下面这个关于协程的例子,似乎才更能体现延续的强大威力。

(define *queue* '())

(define (enqueue task)
  (set! *queue* (append *queue* (list task))))

(define (dequeue)
  (let ((task (car *queue*)))
    (set! *queue* (cdr *queue*))
    task))

(define (start)
  ((dequeue)))

(define (switch)
  (call/cc (lambda (c)
             (enqueue c)
             ((dequeue)))))

(define (print-loop str)
  (define (print-loop-i str n)
    (format #t "~A ~A\n" str n)
    (switch)
    (print-loop-i str (+ n 1)))
  (lambda ()
    (print-loop-i str 1)))

(enqueue (print-loop "AAAAA"))                   ;; 0
(enqueue (print-loop "BBBBB"))                   ;; 1
(start)                                          ;; 2

这个例子来自维基百科,我修改了一下,因为维基上的示例使用了一个 (fork) 函数来将延续加入队列。但这个延续其实只起到占位的作用,不会参与打印。另外,它还使用 (thread-exit) 来判断队列是否为空,而实际上这时候队列是不会为空的。(thread-exit) 仅仅相当一个 (start) 函数,让队列可以跑起来。我觉得这些会给新手造成困扰,所以把这两个函数去掉了,稍稍改动了一下。

这段代码会交替打印 “AAAAA” 和 “BBBBB”,就好像两个线程同时工作。语句 0 和 1 分别将两个打印函数加入全局队列中,然后 (start) 启动队列,先是 (print-loop “AAAAA”) 开始工作。这是一个无限循环打印字符的函数,本来应该永不停歇地打印 “AAAAA”,但是当它每打印一条字符之后,会执行 (switch) 函数。它的作用是保存当前延续,将其加入队列尾部,然后将队列头部的函数(或者延续)取出,再调用之。打印 “AAAAA” 之后,(switch) 取出的是打印 “BBBBB” 的函数(或延续),反之亦然。因此,程序就可以循环往复地交替打印两条字符。

(switch) 是协程的核心所在,它像一个调度员,协调整个队列。(print-loop “AAAAA”) 和 (print-loop “BBBBB”) 调用的是同一个 (switch) 函数,但是其中抽取到的延续却是不一样的,这又是一个非引用透明的例子。

这个打印字符的示例虽然简单,不过这种方法是非常有用的。一个比较典型的用途是两颗树的比较。试想一下,通常的比较方法是先将树展开然后在比较。但如果树非常大,而且两颗树仅仅在开头就出现不同,这样后面的展开全是做了无用功。利用延续,可以定义两个函数分别展开两颗树,展开一部分,保存状态之后将函数挂起,然后比较已经展开的部分,一旦发现不同就不用继续之后的展开了。


3. 消除 call/cc

现代语言中常见的 return、break、goto、以及异常都可以算作延续的一个子集。延续威力强大,但不太容易理解。好在根据延续的特性,可以变形来消除 call/cc。比如前面提到过的一个例子:

;; 示例 0:
(define f '())                                ;; 0
(append (list 1 2 3)
        (list (call/cc (lambda (c)
                         (set! f c)
                         4))))                ;; 1
(f 5)                                         ;; 2
;; => (1 2 3 5)

本质上延续是一个函数,所以完全可以把延续改写成一个函数:延续可以被调用,并且接受一个参数;延续包含自 call/cc 所在一直上溯到 top-level。那么示例 0 中的 call/cc 在抽取延续时首先取到的这样的形式:

;; 示例 1:
(define cont
  (lambda (k)
    (append (list 1 2 3)
            (list {continuation}))))

{continuation} 是抽取时延续所在的位置,cont 最终的结果就取决于 {continuation}{continuation} 最后是什么呢?答案在延续的特性二中:call/cc 的返回值取决于延续被什么调用,被什么调用,call/cc 就返回什么。因此在消除 callcc 时遵循两个原则,第一,如果在抽取时延续被调用,call/cc 直接返回调用延续的参数。第二,如果抽取时延续没有被调用,那么延续一定会在外部被调用,否则延续就没有存在的意义。当延续在外部被调用时,call/cc 的返回值依然是调用延续的参数,也就是 cont 中最外层的 lambda 的参数, k。

显然,示例 1 中的延续只是赋值给了 f,没有被调用。所以,最终抽取到的延续是这样的:

(define cont
  (lambda (k)
    (append (list 1 2 3)
            (list k))))

这也解释了为什么示例 0 中 (f 5) 的返回结果是 (1 2 3 5)

另一个例子:

;; 示例 2:
(((call/cc (lambda (c) c))
  (lambda (x) x)) "xxx")
;; => "xxx"

这个例子有点不太一样,因为 call/cc 直接返回了延续,而且延续之后立即被 (lambda (x) x) 调用了。根据原则一,最后抽取的延续是这个样子的:

(define cont
  (lambda (x) x))

将 cont 带入示例 2:

(((lambda (x) x) (lambda (x) x)) "xxx")
;; => "xxx"

这样消除 call/cc 后的代码和原代码是完全等价的,而且更简单易懂。

作为进一步阅读,可以看看王垠的《Understanding the Yin-Yang Puzzle》,是如何将阴阳谜题中晦涩的 Continuation 消除的。

(完)

参考资料: