看过《Essentials of Programming Languages》之后,才明白 scheme 中的 continuation 为什么会具有那些特点。这里试着从解释器实现的角度,解释一下 continuation 是如何工作的。
1. Continuation-Passing Interpreters
假设有一种叫 BLAH 的程序语言,语法简单直观,与 JavaScript 相似,我们用 scheme 为它编写一个解释器 demo,以观察 continuation 的工作方式。
这是 BLAH 语言中两个函数调用:
iszero(add(1, 2))
针对这段代码,在任何一门解释器入门课程中,给出的处理方法大致是这样:
(define value-of
(lambda (exp env)
(cases expression exp
(iszero-exp iszero-body
(= 0 (value-of iszero-body env)))
(add-exp add-body1 add-body2
(+
(value-of add-body1 env)
(value-of add-body2 env)))
)))
除了直接在 value-of
中计算求值,还有另一种处理方式:解释器在执行代码时,会构建一个代码执行上下文(control context),作为解释函数的第三个参数,往下一层一层传递,直到必要时再求值。我们给这种新的解释器函数取名叫 value-of/k
:
(define value-of/k
(lambda (exp env cont)
(cases expression exp
(iszero-exp iszero-body
(value-of/k iszero-body env
(build-iszero-cont cont)))
(add-exp add-body1 add-body2
(value-of/k add-body1 env
(build-add-cont add-body2 cont)))
)))
其中 cont
参数即执行上下文,可以发现,value-of
由于需要立即求值所以不得不递归地调用自身,从而导致运行时堆栈的增长。value-of/k
中虽然也会调用自己,但都是尾递归。
value-of/k
之所以能避免递归求值,正是因为其将求值的步骤放入了 cont
中。不难猜到构建 cont
大致的方式:
(define iszero-cont
(lambda (v)
(= v 0)))
(define add-cont
(lambda (v1)
(lambda (v2)
(+ v1 v2))))
cont
构建好了之后应该何时被执行呢?cont
返回一个函数,该函数接受一个参数。它表示的含义为『我期待一个 value,当 value 准备好了我会对它进行计算』。所以当 value-of/k
遇到 value 时,就将它传给 cont
进行计算。
(define apply-cont ;; new stuff
(lambda (cont val)
(cont val)))
(define value-of/k
(lambda (exp env cont)
(cases expression exp
(const-exp val ;; new stuff
(apply-cont cont val))
(iszero-exp iszero-body
(value-of/k iszero-body env
(build-iszero-cont cont)))
(add-exp add-body1 add-body2
(value-of/k add-body1 env
(build-add-cont add-body2 cont)))
)))
相应地,cont
中的求值结果也应该传给上一个 cont
继续进行计算。两个 build-cont 函数的完整实现如下:
(define build-iszero-cont
(lambda (cont)
(lambda (v)
(apply-cont cont (= v 0)))))
(define build-add-cont
(lambda (add-body2 env cont)
(lambda (v1)
(value-of/k add-body2 env
(lambda (v2)
(apply-cont cont (+ v1 v2)))))))
cont
其实就是 continuation,这样的解释器被称为 Continuation-Passing Interpreters。这种设计除了可以避免 value-of
运行堆栈的增长,还有一个更重要的作用,为实现 exception 和 thread 等机制提供了便利。
2. Exception
BLAH 代码如下:
let foo = function (n) {
if (iszero(n)) {
throw -100
} else {
return add(n, 1)
}
}
let bar = function (x) {
try {
return add(foo(x), 2)
} catch (e) {
return add(e, 100)
}
}
add(bar(y), 3)
如果代码顺利执行(没有抛出异常),y 会先加 1,然后再加上 2,最后加上 3。continuation 为:
(lambda (v1)
(lambda (v2)
(lambda (v3)
(+ (+ (+ y v1) v2) v3)))) ;; 实际参数 1、2、3 会被依次传入
如果 n 为零程序抛出异常,加 1 和加 2 的动作会被忽略,程序进入 catch block,转而执行加 100 再加 3 的步骤。continuation 为:
(lambda (v1)
(lambda (v2)
(+ (+ y v1) v2))) ;; 实际参数 100、3 会被依次传入
两种情况对应的执行流程并不相同,所以我们给 value-of/k
添加第四个参数 catch-cont
,表示出现异常时程序的执行流程:
(define value-of/k
(lambda (exp env cont catch-cont)
(cases expression exp
(const-exp val
(apply-cont cont val))
(iszero-exp iszero-body
(value-of/k iszero-body env
(build-iszero-cont cont) catch-cont))
(add-exp add-body1 add-body2
(value-of/k add-body1 env
(build-add-cont add-body2 cont) catch-cont))
(try-exp try-body catch-var catch-body
(value-of/k try-body env
(build-try-cont ... )
(build-catch-cont ... )))
(throw-exp throw-body
(value-of/k raise-body env
(build-throw-cont ... ) catch-cont))
)))
catch-cont
是指 BLAH 代码抛出异常时对应的处理逻辑,除了 try catch block 以外,value-of/k
在处理其他表达式时,都是将 catch-cont
原样传下去。也就是说,如果目标代码没有使用 try catch 捕获异常,那么 catch-cont
就是第一次调动 value-of/k
时传入的值,也就是程序默认对异常的处理逻辑(一般来说是打印堆栈信息然后错误退出)。
同样地,除了 catch-cont
,在第一次调用 value-of/k
时还需要传入 cont
的初始值。这个值的含义为,当整个 BLAH 代码求值完毕后,所得到的值应该如何处理。一些程序语言会将它打印到标准输出,有的会将它忽略。作为 demo 代码,为了观察方便,我们将其打印出来。
(value-of/k the-whole-exp init-env end-cont end-catch-cont)
(define end-cont
(lambda (val)
(display (format "End of computation. final value: ~s ~%" val))))
(define end-catch-cont
(lambda (val)
(display (format "Exception occurred. exception value: ~s ~%" val))))
接下来,还有三个构建 continuation 的函数。
2.1. build-try-cont
try-cont 的构建比较容易,它属于程序正常执行的流程(没有抛出异常)。可以这样想,如果没有异常抛出,那么 catch 代码块根本不会执行,try catch 语句其实是可以去掉的。上面 BLAH 代码中的 bar
函数,可以简写成这样:
let bar = function (y) {
return add(foo(y), 2)
}
所以 build-try-cont
不需要多余的动作,直接将 try-body
的求值结果(val
)和原始执行流程(cont
)传给 apply-cont
即可。
2.2. build-catch-cont
catch-cont
为捕获异常后,代码的执行逻辑。异常本身也是一个 value,抛出后被 catch 代码块捕获,并绑定到变量上。之后对 catch 代码块的表达式求值,最后将求值结果作为整个 try catch 代码块的值返回给上层。
对应 BLAH 代码为例。foo
函数抛出 value 为 -100 的异常,传入 bar
函数的 catch 代码块,绑定到变量 e
上。接着对 add(e, 100)
求值,最后将求值结果传给 add(_, 3)
。
2.3. build-throw-cont
当 value-of/k
遇到 throw 语句,说明代码需要抛出一个异常。value-of/k
先对 throw 后的表达式求值,然后将结果传给异常处理流程(catch-cont
)。注意是传给 catch-cont
而不是 cont
,因为代码执行流程直接跳到了上层的 catch 语句块(如果有的话,没有程序就直接退出),所以正常的执行流程 cont
被丢弃了。
完整的代码:
(define value-of/k
(lambda (exp env cont catch-cont)
(cases expression exp
...
(try-exp try-body catch-var catch-body
(value-of/k try-body env
(build-try-cont cont)
(build-catch-cont catch-var catch-body env cont)))
(throw-exp throw-body
(value-of/k raise-body env
(build-throw-cont catch-cont) catch-cont))
)))
(define build-try-cont
(lambda (cont)
(lambda (val)
(apply-cont cont val))))
(define build-catch-cont
(lambda (var catch-exp env cont)
(lambda (val)
(value-of/k catch-exp
(extend-env var val env) ;; 绑定新的变量(var)和值(val)到 environment。
cont ;; 原始的 cont 依然需要,
;; 就像示例代码中抛出了异常后也依然会执行加 4 操作。
end-catch-cont)))) ;; catch 中的代码如果没有放入新的 try catch 代码块,
;; 那当再次抛出异常时,将不会被捕获,
;; 所以这里设置 catch-cont 为默认的 end-catch-cont。
(define build-throw-cont
(lambda (catch-cont) ;; 正常的执行流程(cont)被丢弃了,
(lambda (val) ;; 所以当抛出异常后,try 语句块中的代码将不再执行。
(apply-catch catch-cont val))))
3. Thread
这里的 thread 更像是 lua 的 coroutine,是程序运行时的执行流程切换。执行流程的切换其实就是 continuation 之间的切换。
BLAH 程序代码如下:
let x = 0
spawn(function () {x = add(x, 1)}) // thread 1
spawn(function () {x = add(x, 2)}) // thread 2
x = add(x, 100)
spawn
接受一个函数,将该函数作为一个新的线程执行。
最简单的实现:将所有线程放入一个线程池(thread-queue
),且不考虑线程间切换的问题,即主线程执行完后再执行子线程,一个子线程执行完后再执行下一个子线程,直到线程池为空后程序退出。
原本处理程序最终返回值的逻辑(end-cont
)是在主线程执行完后打印结果并退出,现在改为主线程结束后执行子线程:
(value-of/k the-whole-exp init-env end-main-thread-cont)
(define end-main-thread-cont ;; 原来的 end-cont 函数。
(lambda (val)
(display (format
"End of main thread, final value: ~s. Start to run sub-threads ~%"
val)) ;; 为了简单,在执行子线程之前就把结果打印出来了。
(run-next-thread)))
(define run-next-thread
(lambda ()
(if (null? thread-queue)
"No threads. End of computation." ;; 如果线程池为空,退出。
(let ((first-thread (car thread-queue))
(other-threads (cdr thread-queue)))
(set! thread-queue other-threads)
(first-thread)))))
spawn
创建的线程都是异步执行,spawn
自身也不返回有意义的值。可以这样认为,它除了新建一个线程加入线程池外,本身对整个代码的执行上下文没有任何影响。所以 value-of/k
遇到 spawn 语句时,构建的 cont
同 build-try-cont
一样,直接传给 apply-cont
。
(define value-of/k
(lambda (exp env cont)
(cases expression exp
...
(spawn-exp spawn-body
(value-of/k spawn-body env (build-spawn-cont cont)))
)))
(define build-spawn-cont
(lambda (cont)
(lambda (func)
(add-to-thread-queue
(lambda ()
(apply-call func "dummy" ;; 线程对应函数都没有参数,这里随意传入一个值。
end-subthread-cont))) ;; apply-call 的第四个参数,
;; 表示函数调用完成后该做什么。
(apply-cont cont "dummy")))) ;; 这个 dummy 可以看成是 spawn 函数的返回值,
;; 为了保持所有函数都有返回值这个简单统一的模型,
;; 这里也随意传入一个值。
(define end-subthread-cont
(lambda (dummy)
(run-next-thread))) ;; 当一个子线程执行结束,再执行下一个子线程。
(define add-to-thread-queue
(lambda (thread)
(set! thread-queue
(cons thread thread-queue))))
apply-call
处理所有函数调用。func 为函数的结构体,包含函数的形参、函数体、以及 env。arg 为实际参数。
apply-call
会对函数体求值,所以需要传入 cont
,告诉 value-of/k
求完值之后干什么。
(define apply-call
(lambda (func arg cont)
(let ((var (get-func-var func))
(body (get-func-body func))
(env (get-func-env func)))
(value-of/k body
(extend-env var arg env) ;; 绑定函数的实参和形参。
cont))))
这个线程模型虽然可以工作,但有些简单。比如缺少了线程间通信和加锁的机制,以及与 continuation 更相关且更重要的线程间切换机制。
3.1. 线程间切换
上面的简单模型中,主线程子线程依次执行,最终实现的效果和下面这段不使用线程的代码是完全等价的。
let x = 0
x = add(x, 100)
x = add(x, 1)
x = add(x, 2)
程序代码中之所以使用多线程,是为了充分利用 CPU 资源。当一个线程处于 I/O 等待时,让 CPU 继续执行其他的线程,从而避免 CPU 资源的浪费。
我们尝试加入一种简单的切换模型,每个线程执行 5 步(即 5 次 apply-cont
),然后切换到下一个线程。设置一个计数器(time-remaining
),在每次执行 apply-cont
时检查这个计数器,如果为 0 即切换到下一个线程,否则继续执行并减小计数器的值。
(define apply-cont
(lambda (cont val)
(if (= time-remaining 0)
(begin
(add-to-thread-queue
(lambda () (apply-cont cont val))) ;; 下次开始执行时继续执行 apply-cont。
(run-next-thread))
(begin
(set! time-remaining (- time-remaining 1))
(cont val)))))
从 thread-queue
取得新的线程执行前,需要将 time-remaining
重新设为 5。
(define run-next-thread
(lambda ()
(if (null? thread-queue)
"No threads. End of computation."
(let ((first-thread (car thread-queue))
(other-threads (cdr thread-queue)))
(set! thread-queue other-threads)
(set! time-remaining 5) ;; new stuff
(first-thread)))))
模型虽然简单,但基本的方法就是这样,不同的切换方式只是选择在哪里执行 run-next-thread
。像 golang 会在进入阻塞式系统调用时切换 goroutine,也很有道理,如果一个 goroutine 中没有系统调用,说明它可能在做纯计算的任务,CPU 也没闲着。
3.2. 主动切换线程
除了由解释器判断是否切换线程外,还可以提供一种机制让程序主动地在线程间切换。这里使用 yield 关键字显式地声明切换到下一线程。
虽然 BLAH 代码使用了 JavaScript 的语法,但这里的 yield 和 JavaScript 的 yield 并不相同。
let x = 0
spawn(function () {
x = add(x, 1)
yield
x = add(x, 1)
}) // thread 1
spawn(function () {
x = add(x, 2)
yield
x = add(x, 2)
}) // thread 2
x = add(x, 100)
yield 语句用于告知解释器切换到下一个线程。当 value-of/k
遇到 yield 时应当:
- 将当前的执行上下文保存到线程池
- 取出下一个线程并执行
(define value-of/k
(lambda (exp env cont)
(cases expression exp
...
(yield-exp
(apply-cont
(build-yield-cont cont)
"dummy"))
)))
(define build-yield-cont
(lambda (cont)
(begin
(add-to-thread-queue ;; 将当前的执行上下文保存到线程池。
(lambda ()
(apply-cont cont "dummy")))
(run-next-thread)))) ;; 取出下一个线程并执行。
因为 yield 语句不接受参数也不返回值,所以用 “dummy” 占位。
3.3. Generators
python 的 generator 也可以看成两个线程之间来回切换。
def my_gen():
n = 1
while True:
yield n
n += 1
def my_caller():
g = my_gen()
print(next(g)) # output: 1
print(next(g)) # output: 2
print(next(g)) # output: 3
my_caller()
第一次调用 next(g)
,my_caller
所在的线程被挂起,my_gen
作为一个新的线程开始执行。遇到 yield
后切换回 my_caller
继续执行,并将 n
返回给 my_caller
。当 my_caller
再一次调用 next(g)
,则又切换到 my_gen
。
BLAH 中实现的 yield 和 python 的 yield 已经很相近了,还有两点不同:
- python 的 generator 并不是一个线程池,程序有选择地执行某一个线程,子线程遇到 yield 后返回之前调用它的线程
- python 的 yield 接受一个参数并将其返回给调用线程
根据这两点不同,我们修改一下解释器代码:
(define value-of/k
(lambda (exp env cont)
(cases expression exp
...
(generator-exp g
(build-generator-cont cont g))
(yield-exp yield-body
(value-of/k yield-body env (build-yield-cont cont))
)))
(define build-generator-cont
(lambda (cont g)
(begin
(set! caller-thread ;; 保存当前线程(调用线程)。
(lambda (val) ;; 因为 yield 会返回一个值到调用线程,
;; 这里的 val 参数用于接收这个值。
(apply-cont cont val)))
(run-thread g)))) ;; 执行 generator 对应的线程。
(define build-yield-cont
(lambda (cont)
(lambda (val)
(begin
(set! generator-thread ;; 保存 generator 线程
(lambda ()
(apply-cont cont "dummy")))
(caller-thread val))))) ;; 将结果返回给调用线程。
在 build-yield-cont
中保存 generator 线程时,依然传入了 "dummy"
。因为这里的 cont
指的是 generator 内部的上下文,而 yield
是将值返回给调用它的线程,在它自身的 generator 线程内,它是不返回值的。用 python 举一个例子:
def my_gen():
n = 1
while True:
print(yield n)
n += 1
def my_caller():
g = my_gen()
next(g)
next(g)
my_caller() # output: None
执行这段代码会输出一个 None
。因为 yield n
会将 n 返回给 my_caller
,但在 my_gen
内部它不返回值,所以 print
得到了 None
。
4. call/cc
在大多数解释器实现中,continuation 被表示为数据结构,而不是函数。但我们仍然选择将 continuation 表示为函数,除了简单之外,更因为这样可以直观地展示出『continuation 可以被调用』这个特点。
continuation 是一个匿名函数,接受一个值,表示它将如何处理这个值。在我们的解释器代码中,continuation 总是在解释器内部被调用。能不能提供一种机制,把 continuation 暴露给程序代码,让用户自己控制如何处理 continuation?
在 scheme 中这种机制就是 call/cc。call/cc 接受一个函数作为参数,这个函数也接受一个参数,这个参数会被解释器绑定为当前的 continuation。
比如这段 scheme 代码:
(define f '())
(+ 1
(call/cc
(lambda (c)
(set! f c)
0)))
(+ 4 (f 2)) ;; => 3
解释器遇到 call/cc
后,会将当前 continuation 作为参数,调用 call/cc
中的函数。代码中 f
被绑定到了 call/cc
所在位置的 continuation。
执行 (+ 4 (f 2))
后会返回 3,不是 7。即代码执行了 1 + 2,加 4 的步骤被忽略了。至于为什么会这样,我们将 call/cc 引入 BLAH:
let f = null
add(1, callcc(
function(c) {
f = c
return 0
}))
add(4, f(2))
在 value-of/k
中对 callcc 函数特殊处理:
(define value-of/k
(lambda (exp env cont)
(cases expression exp
...
(callcc-exp body
(value-of/k body env (build-callcc-cont cont)))
)))
(define build-callcc-cont
(lambda (cont)
(lambda (func)
(apply-call func cont cont))))
(define apply-call ;; apply-call 被扩展为处理普通的函数调用和 cont 调用。
(lambda (func arg cont)
(if (is-a-cont func)
(apply-call-cont func arg cont) ;; 当 func 是 continuation 时,
;; apply-cont 的第三个参数 cont 会被丢弃。
(apply-call-function func arg cont))))
(define apply-call-function
(lambda (func arg cont)
(let ((var (get-func-var func))
(body (get-func-body func))
(env (get-func-env func)))
(value-of/k body (extend-env var arg env) cont))))
(define apply-call-cont
(lambda (cont arg)
(apply-cont cont arg)))
调用 build-callcc-cont
传入的参数 cont
最终会在 apply-call-function
中通过 extend-env
被绑定到 func
的参数上,也就是 BLAH 代码的参数 c
,这个 cont
为:
(lambda (val)
(end-cont (+ 1 val)))
因为 continuation 的调用方式和普通函数一致,apply-call
被扩展成了处理普通函数调用与 continuation 的调用。和普通函数调用不同的是,调用一个 continuation 时不会再传入当前的 continuation,即当前的 continuation 会被丢弃。
当代码 add(4, f(2))
中的 f
被调用时,这时当前的 continuation 为:
(lambda (val)
(end-cont (+ 4 (f val))))
f
被调用,apply-call
进入了 apply-call-cont
,因而当前的 continuation 被丢弃了。所以程序最后执行 ((lambda (val) (end-cont (+ 1 val))) 2)
,返回 3。
5. play with call/cc
从实现可以看出,continuation 之所以可以方便的实现 Exceptions 和 Threads,因为它将复杂的控制流程抽象为一种数据结构。
现在可以忘了 BLAH,回到 scheme 中再看看 call/cc,看它是如何在代码层面实现那些原本应该在解释器中实现机制:计算的延续(一):Continuation 介绍
(完)
参考链接: