Magic with continuation

Magic with continuation

Continuation 是时间经过具象化得到的产物,而 call/cc 是对时间进行操作的魔法,

这是一篇介绍延续(Continuation)的文章,本文针对的是对 continuation 没有太多了解的人(比如我),所以废话很多。

什么是 Continuation ?

先看维基百科的描述

In computer science and computer programming, a continuation is an abstract representation) of the control state of a computer program.

计算机科学程序设计中,计算续体(continuation)是计算机程序的控制状态的一种抽象表现。

简而言之,continuation 是一种描述“我们接下来做什么”的东西。

举个栗子

1
(+ (* 1 2) (* 3 4))

在上面的计算过程中,我们考虑计算时介入了 1 的这个时间点,对于 1 而言,它接下来需要参与的运算是

1
(+ (* _ 2) (* 3 4))

或者我们使用函数来表示

1
(λ (x) (+ (* x 2) (* 3 4)))

当程序运行到 1 的地方时,我们把 1 喂给上面这个类似于函数的东西,来进行接下来的计算。

所以说,continuation 是一种在程序运行时隐式地存在并活动着地东西。某种意义上它很像时间,看不见摸不着,但确实存在着并能“使”世界发生变化。Continuation 保存着之前你已经做过的事情和你接下来即将要做的事情。它是当前程序运行时的一个快照,任何时候,我们把它需要的那个值喂给它,他就会取代当前的 continuation 并使程序进入它所在的世界线。如果能把它保存下来的话,就能在之后回到当时的情形。

为了把它们保存下来,很多语言支持了“First-class continuations”,即 continuation 和函数、数据一样,都能作为变量的值参与运算和调用。Scheme 是实现了 first-class continuations 的语言之一,我们接下来主要以 Scheme 语言作为示例语言。

什么是 call-with-current-continuation ?

Continuation 在程序中隐式地不断的产生并使用。通过普通的手段我们无法得到这么一个 <continuation> 对象,所以 Scheme 提供了一个函数作为“控制时间”的接口,叫做 call-with-current-continuation(缩写为 call/cc)。正如它的名字所言,它接受一个函数这个函数能接受一个参数,call/cc 将 current-continuation (当前延续) 、也就是调用 call/cc 时的上下文,作为参数传进这个函数,并调用

先来看一个简单的例子:对于 (+ (* 1 2) (* 3 4)) 中的 1 我们知道它的 continuation

1
((λ (x) (+ (* x 2) (* 3 4))))

我们只需要喂给它一个 1 就能得到运算的结果。

我们如果把 1 换成 (call/cc (lambda (k) (k 1)))

1
(+ (* (call/cc (lambda (k) (k 1))) 2) (* 3 4))

这样得到的式子和原来的式子是等价的。

通过 call/cc 我们可以实现 get/cc获取当前延续. 只需要喂给它一个 id 就可以了

1
(define (get/cc) (call/cc (lambda (x) x)))

get/cc 调用的结果就是当前延续。

利用 call/cc 可以合成绝大多数的控制流结构,例如循环/分支/异常/协程/生成器等等。下面是一份利用 call/cc 实现 generator 的代码(其实这里是有 bug 的,这并不是一份正确的代码)

1
2
3
4
5
6
7
8
(define (make-generator lst)
(define (control return)
(for-each (lambda (e)
(call/cc (lambda (r)
(set! control r)
(return e)))) lst))
(define (generator) (call/cc control))
generator)

调用结果如下:

1
2
3
4
5
6
(define a (make-generator '(1 2 3 4)))
(a) ; -- 1
(a) ; -- 2
(a) ; -- 3
(a) ; -- 4
(a) ; -- nothing happened

我们来看一看这里究竟发生了什么。

1
(define (control return) ;

control 最开始定义时是一个接受一个 continuation 并做一些事情 的函数,它对 lst 中的每一个元素依次调用了下面这个函数

1
2
3
4
(lambda (e)
(call/cc (lambda (r)
(set! control r)
(return e))))

这个函数用 e 绑定了 lst 中的一个元素,随即对另一个函数调用了 call/cc ,注意到,另一个函数在接收到 current continuation 后并没有直接调用它,而是把它赋值给了control ,然后用调用 control 时接受的 continuation 拿着当前元素 e 返回了。

然后定义了作为返回值的 generator 函数,它是对 control 调用 call/cc 得到的东西。

说了这么多你可能仍然没有明白这一段代码是啥,那么我们来看 a 在调用时究竟发生了什么

a 绑定到了 generator 上,也就是 (call/cc control) ,我们把 current continuation 塞进 control

1
2
3
4
5
6
(define (control return) ;; 这里的 return 就是在调用 generator 时的 current continuation
(for-each (lambda (e) ;; 第一次调用时 e 是 1
(call/cc (lambda (r) ;; 在这里用 call/cc 对程序做了个快照,以便日后回到这里
(set! control r) ;; 把这个快照绑定到 control
(return e)))) ; 使用外界 continuation 返回获取的值
lst)) ; for-each 的参数列表

这样,第一次调用的结果就出来了,是 1, 那么第二次调用时又发生了什么呢?

第二次调用 (a) ,相当于 (call/cc control) 。这里的 control 是在上面用 call/cc 获取的 for-each 内的 continuation,我们把调用 a 时的 current continuation 传给了这个捕获的 continuation ,程序回到了调用 call/cc 的地方。for-each 对第一个元素的调用已经结束,并开始的对 lst 中的第二个元素 2 调用这个函数。在修改了 control 之后,我们使用的是闭包中的 return 来返回第二个元素 。在命令行调用 (a) 时不会产生区别,但之后每次调用 (a) 时都会使用第一次调用 (a) 时捕获的 continuation ,比如我们这样:

1
2
3
4
5
(define a (make-generator '(1 2 3 4)))
(display (+ 1 (a))) ; -- 2
(display (+ 2 (a))) ; -- 3
(display (+ 3 (a))) ; -- 4
(display (+ 4 (a))) ; -- 5

就会发现,它每一次调用时都会返回到最开始调用的位置。这也是像 call/cc 这样的 full continuation 在使用时必须注意的一点。

阴阳谜题

提到 call/cc ,肯定会提到的另一个东西就是阴阳谜题。

思考一下,下面这一段代码会输出什么?

1
2
3
4
5
(let* ((yin
((lambda (cc) (display #\@) cc) (get/cc)))
(yang
((lambda (cc) (display #\*) cc) (get/cc)))
(yin yang))

答案并不是一眼就能看出来的(如果你能你也不会在这里看这篇文章了):

1
@*@**@***@****@*****@******@*******....

为什么会变成这样呢?(
我们使用 let* 产生了两个绑定,分别是 yinyang

yin 在绑定时使用 get/cc 获取了 current continuation,我们把它叫做 $c_0$ 。

$c_0$ 可以写作:

1
2
3
4
5
(let* ((yin
((lambda (cc) (display #\@) cc) _ ))
(yang
((lambda (cc) (display #\*) cc) (get/cc)))
(yin yang))

对于 yang 而言,令它调用 get/cc 获取的 current continuation 为 $c_1$, 如下

1
2
3
4
(let* ((yin c0)
(yang
((lambda (cc) (display #\*) cc) _ ))
(yin yang))

需要注意的是,$c_0$ 中的 yang 还没有被绑定,而 $c_1$ 里 yin中的 get/cc 已经被求值且值为 $c_0$

在绑定结束后,yinyang 中 带了输出副作用的 id 函数 分别输出了 @ 和 *,式子变成了

1
(c0 c1)

我们对 continuation 进行调用时,世界线会回到 continuation 被捕获的瞬间,也就是:

1
2
3
4
5
(let* ((yin
((lambda (cc) (display #\@) cc) c1 ))
(yang
((lambda (cc) (display #\*) cc) (get/cc)))
(yin yang))

同样的,我们把在这里用 get/cc 捕获的 continuation 叫做 $c_2$ 。

$c_2$ 是

1
2
3
4
(let* ((yin c1)
(yang
((lambda (cc) (display #\*) cc) _ ))
(yin yang))

那么经过化简我们又输出了一组 “@*” ,式子成为了 (c1 c2) ,然后我们展开 $c_1$ :

1
2
3
4
(let* ((yin c0)
(yang
((lambda (cc) (display #\*) cc) c2 ))
(yin yang))

$c_1$ 中的 yin 已经被化简,所以这次的化简中只会输出一个 “*” ,并成为 (c0 c2) 。然后带入 $c_0$ :

1
2
3
4
5
(let* ((yin
((lambda (cc) (display #\@) cc) c2 ))
(yang
((lambda (cc) (display #\*) cc) (get/cc)))
(yin yang))

重新命名新的 continuation 为 $c_3$ ,再一次输出 @* 后变成 (c2 c3) ,把 c2 带入会得到:

1
2
3
4
(let* ((yin c1)
(yang
((lambda (cc) (display #\*) cc) c3 ))
(yin yang))

又输出了一个 ,然后 $c_2$ 变成了 $c_1$ 。 $c_1$ 经过调用再输出了一个 ,回到了 $c_0$ ,也即 yin 仍然没有被绑定的状态。在这里我们又一次地创造了新的 continuation : $c_4$。

想必到这里大家已经知道这里究竟发生了什么吧,每次通过 $c_0$ 创造了新的 continuation $c_n$ ,然后从 $n - 1$ 开始,每个 $c_i$ 都会对 $c_n$ 调用一次直至 $c_0$ ,期间会输出 $n - 1$ 个 ,而在调用 $c_0$ 时会同时输出 @ 并创造另一个 continuation $c_{n+1}$ ,yinyang 在其间进行着无尽的轮回。


但是大多数的程序语言中都没有 first-class full continuations,它们会提供一些其它的强大的控制流结构。比如 C 语言中的 setjmp()longjmp() ,可以显式地保存当前的调用栈并执行 escape-only 的跳转操作,我们可以用它来实现异常等高级特性。异常与 escape continuation 是等价的,它们都只能向“外”抛出。还有一种 continuation 叫做 delimited continuation。正如它的名字所示,这个 continuation 是有局限的,我们可以限制 continuation 的范围,而且相较于 full continuation 更适合使用的一点是,这里捕获的 continuation 是一个函数,可以返回

什么是 Continuation-Passing-Style

call/cc 非常强大,但我们该如何实现它呢?考虑到 continuation 的特性,它在程序中隐式的传递,调用时从不返回, 那么我们可以用某种方法把隐式的 continuation 转化为显式的,这样对 continuation 的调用就成了函数的尾调用。这种把 continuation 显式地进行传递的方式就叫 Continuation-Passing-Style。

下面是几个例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(lambda (x) x) => (lambda (x cont) (cont x))
(lambda (x) (+ x 1)) => (lambda (x cont) (cont (+ x 1)))
(lambda (x) (lambda (y) (y x))) => (lambda (x cont) (cont (lambda (y cont2) (y x cont2))))
(define (map f lst)
(if (empty? lst)
lst
(cons (f (car lst))
(map f (cdr lst)))))
=>
(define (map' f lst cont)
(if (empty? lst)
(cont `())
(f (car lst) (lambda (x)
(map' f (cdr lst) (lambda (xs)
(cont (cons x xs))))))))

Continuation-Passing-Style 的可读性非常的差,就像上面的示例那样,而且对于写的人也是很大的挑战,我们需要一种方法把程序自动地转换为 CPS。

考虑最简单的 lambda calculi:
$$
\begin{align}
T &::= var \
&| \space (T \space T) \
&| \space (\lambda x. T)
\end{align}
$$
在进行 CPS 变换的时候需要一个东西来记录之前我们已经转换过的部分并把当前转换后的结果传过去,也就是 current continuation,所以说 CPS 变换本身也是 CPS 的。

我们把那个作为参数传进来的 continuation 叫做 k ,然后开始我们的工作。

首先对于最基本的结构,单个元素,我们只需要把当前的 continuation 应用在它上面就行了:

然后是 抽象(Abstraction),也就是 lambda 表达式,我们在它的参数后面添上一个 continuation,然后把 k 应用到对 lambda 的 body 进行 CPS 的结果上。在对它的 body 进行转换时的 current continuation 就是这个添上的 continuation。

最后是 应用(Application)。我们把函数先进行 CPS 变换,这个变换的 continuation 获取的是经过 CPS 变换的函数,它需要将参数进行 CPS 变换,这里变换的 continuation 获取了 经过 CPS 变换的参数,随即我们把 current continuation 和 函数参数喂给经过变换后的函数。

下面给出一个 js 版本的实现

1
2
3
4
5
6
7
8
9
10
11
12
function convert_cps(exp, cont) {
if (exp.t === "lambda") {
let k = createSymbol();
return call(cont, [lambda([exp.par, k], convert_cps(exp.body, k))]);
}
else if (exp.t === "call") {
let f = createSymbol();
let e = createSymbol();
return convert_cps(exp.fun, lambda([f],
convert_cps(exp.par, lambda([e], call(f, [e, cont])))));
} else return call(cont, [exp]);
}

这里面的 calllambda 都是构造函数。

在最外层调用 convert_cps 时的 continuation 使用 id 函数即可。结果:

($\lambda$ (x) x) $\Rightarrow$ (($\lambda$ (x) x) ($\lambda$ (x v0) (v0 x)))

($\lambda$ (x) ($\lambda$ (y) (y x))) $\Rightarrow$ (($\lambda$ (x) x) ($\lambda$ (x v1) (v1 ($\lambda$ (y v2) (($\lambda$ (v3) (($\lambda$ (v4) (v3 v4 v2)) x)) y)))))

经过简单的化简可以发现,它们和我们的期望是一致的。

既然通过 CPS 变换,所有的 continuation 都已经被提到了程序中,那么现在 call/cc 的实现也就非常平凡了。

1
2
3
call/cc => (λ (f cc) 
(f (λ (x _) (cc x))
cc))

call/cc 会接受两个参数,第一个参数是函数 f ,而第二个参数是接受 call/cc 调用后的结果的 continuation。因为 call/cc 调用的结果实际上就是 f 调用的结果,所以 cc 也将作为新增的 continuation 传进 f 。那么 f 原本的参数又是什么呢? f 原本接受的是一个 continuation这个 continuation 接受任意一个参数然后让时间跳转到它被捕获的地方;所以经过 CPS 后,这个 continuation 会成为一个接受两个参数的函数,第一个参数是它原本准备捕获的参数,而第二个参数是在 f 中调用这个 continuation 时的 current continuation,因为一旦在程序中调用了 continuation,原本的 continuation 就会被丢弃,所以这里的第二参数是没有意义的。然后我们只需要把 x 喂给在 call/cc 调用时被捕获的 continuation cc 就能”返回到 call/cc 被调用的地方“。

实现也很简单:

1
2
3
4
5
6
7
8
9
10
11
12
if (exp.fun === "callcc") {
let k = createSymbol();
let h = createSymbol();
let f = createSymbol();
return convert_cps(exp.par,
lambda([k],
call(k,
[lambda([f, h],
call(cont,
[f])), cont]))
);
}

来看几个简单的例子(经过化简的):

1
2
3
(call/cc (lambda (k) (k 1))) => 1
(callcc (lambda (k) x)) => x
(lambda (x) (callcc (lambda (k) (x (k x)))) => (lambda (x v0) (v0 x))

看到这里再去看王垠的 40 行代码应该不会有太大障碍了。

经过 CPS 变换的代码,所有的函数调用都会变成尾调用,而尾调用是可以通过优化充分利用栈空间的,所以 CPS 经常被应用在编译器的控制流分析和优化上;而与 CPS 等价但更加简洁的 ANF 在生成机器代码时要更加优秀和方便,这里也不加赘述。

没了?

没了。

magic with continuation 中的 magic 呢

通篇都是 magic,只有对魔法敏锐的人才能感受到它的美。