call/cc 总结 | Scheme

Continuation

Continuation 也是一个老生常谈的东西了,我们来回顾一下。首先我们看一下 TSPL4 中定义的表达式求值需要做的事:

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 即为其中的(2),即表达式被求值以后,接下来要对表达式做的计算R5RS 中 continuation 的定义为:

The continuation represents an entire (default) future for the computation.

比如 (+ (* 2 3) (+ 1 7)) 表达式中,(* 2 3)的 continuation 为:保存 (* 2 3) 计算出的值 6,然后计算 (+ 1 7) 的值,最后将两表达式的值相加,结束;(+ 1 7) 的 continuation 为:保存 (+ 1 7) 的值 8,将其与前面计算出的 6 相加,结束。

Scheme 中的 continuation 是 first-class 的,也就是说它可以被当做参数进行传递和返回;并且 Scheme 中可以将 continuation 视为一个 procedure,也就是说可以调用 continuation 执行后续的运算。

call/cc

每个表达式在求值的时候,都会有一个对应的 current continuation,它在等着当前表达式求值完毕然后把值传递给它。那么如何捕捉 current continuation 呢?这就要用到 Scheme 中强大的 call/cc 了。call/cc 的全名是 call-with-current-continuation ,它可以捕捉当前环境下的 current continuation 并利用它做各种各样的事情,如改变控制流,实现非本地退出(non-local exit)、协程(coroutine)、多任务(multi-tasking)等,非常方便。注意这里的 continuation 将当前 context 一并打包保存起来了,而不只是保存程序运行的位置。下面我们来举几个例子说明一下 call/cc 的用法。

current continuation

我们先来看个最简单的例子 —— 用它来捕捉 current continuation 并作为 procedure 调用。call/cc 接受一个函数,该函数接受一个参数,此参数即为 current continuation。以之前 (+ (* 2 3) (+ 1 7)) 表达式中 (* 2 3) 的 continuation 为例:

1
2
3
4
5
(define cc #f)
(+ (call/cc (lambda (return)
(set! cc return)
(* 2 3)))
(+ 1 7))

我们将 (* 2 3) 的 current continuation (用(+ ? (+ 1 7))表示) 绑定给 cc 变量。现在 cc 就对应了一个 continuation ,它相当于过程 (define (cc x) (+ (x) (+ 1 7))),等待一个值然后进行后续的运算:

1
2
3
4
5
6
> cc
#<continuation>
> (cc 10)
18
> (cc (* 2 3))
14

这个例子很好理解,我们下面引入 call/cc 的本质 —— 控制流变换。在 Scheme 中,假设 call/cc 捕捉到的 current continuation 为 cc(位于 lambda 中),如果 cc 作为过程 直接或间接地被调用(即给它传值),call/cc 会立即返回,返回值即为传入 cc 的值。即一旦 current continuation 被调用,控制流会跳到 call/cc 处。因此,利用 call/cc,我们可以摆脱顺序执行的限制,在程序中跳来跳去,非常灵活。下面我们举几个 non-local exit 的例子来说明。

Non-local exit

Scheme 中没有 breakreturn 关键字,因此在循环中如果想 break 并提前返回的话就得借助 call/cc。比如下面的例子寻找传入的 list 中是否包含 5

1
2
3
4
5
6
7
8
9
10
11
12
(define (do-with element return)
(if (= element 5)
(return 'find-five)
(void)))
(define (check-lst lst)
(call/cc (lambda (return)
(for-each (lambda (element)
(do-with element return)
(printf "~a~%" element))
lst)
'not-found)))

测试:

1
2
3
4
5
6
7
8
9
> (check-lst '(0 2 4))
0
2
4
'not-found
> (check-lst '(0 3 5 1))
0
3
'find-five

check-lst 过程会遍历列表中的元素,每次都会将 current continuation 传给 do-with 过程并进行调用,一旦do-with 遇到 5,我们就将结果传给 current continuation (即 return),此时控制流会马上跳回 check-lst 过程中的 call/cc 处,这时候就已经终止遍历了(跳出了循环)。call/cc 的返回值为 'find-five,所以最后会在控制台上打印出 'find-five

我们再来看一个经典的 generator 的例子,它非常像 Python 和 ES 6 中的 yield,每次调用的时候都会返回 list 中的一个元素:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(define (generate-one-element-at-a-time lst)
;; Hand the next item from a-list to "return" or an end-of-list marker
(define (control-state return)
(for-each
(lambda (element)
(set! return (call/cc
(lambda (resume-here)
;; Grab the current continuation
(set! control-state resume-here)
(return element)))))
lst)
(return 'you-fell-off-the-end))
;; This is the actual generator, producing one item from a-list at a time
(define (generator)
(call/cc control-state))
;; Return the generator
generator)
(define generate-digit
(generate-one-element-at-a-time '(0 1 2)))

调用:

1
2
3
4
5
6
7
8
> (generate-digit)
0
> (generate-digit)
1
> (generate-digit)
2
> (generate-digit)
'you-fell-off-the-end

注意到这个例子里有两个 call/cc,大家刚看到的时候可能会有点晕,其实这两个 call/cc 各司其职,互不干扰。第一个 call/cc 负责保存遍历的状态(从此处恢复),而 generator 中的 call/cc 才是真正生成值的地方(非本地退出)。其中一个需要注意的地方就是 control-state,它在第一次调用的时候还是个 procedure,在第一次调用的过程中它就被重新绑定成一个 continuation,之后再调用 generator 生成器的时候,控制流就可以跳到之前遍历的位置继续执行下面的过程,从而达到生成器的效果。

阴阳谜题

continuation 环境嵌套。后面有时间专开一篇分析~

1
2
3
4
5
(let* ((yin
((lambda (cc) (display #\@) cc) (call-with-current-continuation (lambda (c) c))))
(yang
((lambda (cc) (display #\*) cc) (call-with-current-continuation (lambda (c) c)))))
(yin yang))

call/cc与数理逻辑

这里简单提一下 call/cc 与类型系统和数理逻辑的联系。call/cc 的类型是 ((P → Q) → P) → P,通过 Curry-Howard 同构,它可以对应到经典逻辑中的 Peirce’s law

$$((P \to Q) \to P) \to P$$

Peirce’s law 代表排中律 $P \land \lnot P$,这条逻辑无法在 λ演算所对应的直觉逻辑中表示(直觉逻辑中双重否定不成立),因此 call/cc 无法用 λ表达式定义。通常我们用扩展后的 $\lambda \mu \ calculus$ 来定义 call/cc,$\lambda \mu \ calculus$ 经 Curry-Howard 同构可以得到经典逻辑。


References

文章目录
  1. 1. Continuation
  2. 2. call/cc
    1. 2.1. current continuation
    2. 2.2. Non-local exit
  3. 3. 阴阳谜题
  4. 4. call/cc与数理逻辑
  5. 5. References