Print4D

计算的延续(一):Continuation 介绍

12 Dec 2013

continuation 实在是一个比较晦涩的概念。花了不少时间,看了很多资料,总算是大概弄明白了。这里我试着尽可能清楚地解释一些关于 continuation 的细节。


零,continuation 是什么

Contination 最早出现在 scheme 中,是一种流程控制机制,实现诸如 return、break、thread 以及 exception 等功能。continuation 被翻译成『延续』,表示程序将要进行的计算

这些简单代码应该能提供一个大致的印象:

(define f '())               ;; 0

(+ 2 (* 2
        (call/cc
         (lambda (c)
           (set! f c)
           1))))             ;; 1

(f 5)                        ;; 2
;; => 12

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

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

尽管很多时候在内部实现上被表示为数据结构,然而从含义上看,continuation 本质上确实是一个函数。


一,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)

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

语句 2 中使用参数 5 来调用 f,这里的 f 就是从语句 1 中获取到的 continuation。根据特性二,一旦 continuation 被调用就立即返回,且返回值为调用参数(在这里是 5)。但这个 5 该返回到哪里呢?根据特性三,此时程序跳转到了语句 1 所在的上下文,5 成了 (call/cc (lambda (c) (set! f c 4))) 的返回值。之后程序继续执行 (append (list 1 2 3) (list ...)),最终返回 (1 2 3 5)

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

特性零表面上很好理解,其实很容易被误解。原因在于『当前』这两个字。『当前』的含义是:当 call/cc 被调用时,自其所在的位置,沿着它的调用者,一直到 top-level。也就是说『当前』取决在哪里被调用,而不是在哪里被定义。可见 continuation 不具备引用透明性。

语句 4 到语句 8 展示了 continuation 的非引用透明性。

(define current-cc
  (lambda ()
    (call/cc (lambda (c) c))))       ;; 4

(define x (current-cc))              ;; 5

(x 0)                                ;; 6

(display x)                          ;; 7
;; => 0

((current-cc) 0)                     ;; 8
;; => raise error

语句 5 中将 (current-cc) 赋值给 x,如果具有引用透明性的话,那么语句 6 和 8 应该是等价的。但实际上语句 6 正常执行了,语句 8 却抛出错误。因为 call/cc 获取的 continuation 是基于被调用时的上下文,而不是定义时的环境。

语句 5 (current-cc) 获取到的 continuation 是下面这样的。为什么可以写成这样,在第三节《消除 call/cc》会提到

(lambda (k)
  (define x k))

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

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

这也解释了语句 7 为什么输出 0。但是语句 8 中 (current-cc) 获取到的 continuation 是这样的:

(lambda (k)
  (k 0))

语句 8 实际上是用 0 来调用 0,所以抛出了错误。


二,continuation 的作用

下面根据 continuation 的这些特点,实现了 return、generator 和 thread。


return

作为一门函数型语言,scheme 是没有 return 语句的,每一个函数都会隐式地返回一个值,这个值又传递给上一级函数调用,这样逐级返回指定顶层。也就是说显式的 return 对于 scheme 并没有多大用处。

但如果在 for-each 这样的过程式代码中,想在中途返回一个值就显得比较困难了。

下面这段代码利用了 continuation 来实现在 for-each 循环中 return 的功能。

(define member?
  (lambda (lst element)
    (define member
      (lambda (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) ;; => ()

这个例子是特性二和三的体现,当 member 中的 return(也就是传入 member 的 continuation)被调用,member? 会立即返回,返回值为调用 return 的参数 l

这叫做 non-local exit。和 return 一样,break 也是一种 non-local exit,只是退到哪里的问题。


generator

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

    (define next
      (lambda ()
        (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"

这个例子用了两个 call/cc。

next 中使用 call/cc 是为了实现 return。

next-i 中的 call/cc 则要复杂一些,当第一次执行 (f)next 内部会调用 next-i,这时 next-imake-next 中定义的普通函数,next-i 先获取 continuation 并赋值给自身(next-i),然后再返回 lst 的第一个元素。把 continuation 赋值给 next-i 之后,next-i 就变成 continuation 了。所以第二次调用 next-i 时程序会跳到之前 (set! next-i c) 时的运行上下文,接着当时返回第一个元素的地方继续运行,最终 for-each 迭代第二个元素,并再次保存当前 continuation 到 next-i。类似的,直到第五次执行 (f)next-i 返回 "no element"


thread

前面两个例子,都不是非 continuation 不能实现。不使用 continuation,改变代码的结构程序也可以在任何位置 return;使用闭包,也能实现 generator。下面这个关于 thread 的例子,更能体现 continuation 的强大威力。

这里的 thread 不是指系统级的线程,它更像 lua 的协程,程序在运行时能主动控制执行流程。

(define *queue* '())

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

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

(define start
  (lambda ()
    ((dequeue))))

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

(define print-loop
  (lambda (str)
    (define print-loop-i
      (lambda (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

这个例子来自 Wikipedia,进行了些简化。

这段代码会交替打印 “AAAAA” 和 “BBBBB”,就好像两个线程同时工作。语句 0 和 1 分别将两个打印函数加入全局队列,执行 (start) 后队列启动,先是 (print-loop "AAAAA") 开始工作。print-loop 函数循环打印字符,每打印一条字符后会执行 switch 函数。switch 的作用是保存当前 continuation,将其加入队列尾部,然后将队列头部的函数(或者 continuation)取出并调用。

打印 “AAAAA” 之后,switch 取出打印 “BBBBB” 的任务,反之亦然,如此交替执行。最终程序的运行效果就是循环往复地交替打印两条字符。

switch 是 thread 的核心,它像一个调度员,协调整个队列。(print-loop "AAAAA")(print-loop "BBBBB") 调用的是同一个 switch 函数,但其中获取到的 continuation 却不一样(又一个非引用透明的例子)。


三,消除 call/cc

现代语言中常见的 return、break、goto、thread、exception 都可以算作 continuation 的子集。然而 continuation 并不太容易理解,我们可以根据 continuation 的特性,通过变形来消除 call/cc。

比如前面提到过的一个例子:

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

既然 continuation 本质是函数,那完全可以把上面的例子改写成函数:

语句 1 中的 call/cc 获取到的 continuation 应该具有这种形式:

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

cont 中的 ... 是什么呢?

答案在特性二中:call/cc 的返回值取决于 continuation 有没有被调用,被什么调用。因此在消除 callcc 时遵循两个原则:

显然,代码中的 continuation 只是赋值给了 f,没有被调用,最终获取到的 continuation 是这样的:

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

所以 (f 5) 返回 (1 2 3 5)

另一个例子:

(((call/cc (lambda (c) c))
  (lambda (x) x)) "xxx")    ;; => "xxx"

这个例子中 call/cc 将 continuation 直接返回了,返回后的 continuation 立即被 (lambda (x) x) 调用。根据原则一,获取到的 continuation 是这样的:

(define cont
  (lambda (x) x))

将 cont 代入代码:

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

这样消除 call/cc 后的代码和原代码是完全等价的。

(完)

参考链接: