看过《Essentials of Programming Languages》之后，才明白 scheme 中的 continuation 为什么会具有那些特点。这里试着从解释器实现的角度，解释一下 continuation 是如何工作的。
零，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 等机制提供了便利。
一，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 的函数。
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 即可。
build-catch-cont
catch-cont 为捕获异常后，代码的执行逻辑。异常本身也是一个 value，抛出后被 catch 代码块捕获，并绑定到变量上。之后对 catch 代码块的表达式求值，最后将求值结果作为整个 try catch 代码块的值返回给上层。
对应 BLAH 代码为例。foo 函数抛出 value 为 -100 的异常，传入 bar 函数的 catch 代码块，绑定到变量 e 上。接着对 add(e, 100) 求值，最后将求值结果传给 add(_, 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))))二，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 更相关且更重要的线程间切换机制。
线程间切换
上面的简单模型中，主线程子线程依次执行，最终实现的效果和下面这段不使用线程的代码是完全等价的。
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 也没闲着。
主动切换线程
除了由解释器判断是否切换线程外，还可以提供一种机制让程序主动地在线程间切换。这里使用 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” 占位。
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。
三，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。
四，play with call/cc
从实现可以看出，continuation 之所以可以方便的实现 Exceptions 和 Threads，因为它将复杂的控制流程抽象为一种数据结构。
现在可以忘了 BLAH，回到 scheme 中再看看 call/cc，看它是如何在代码层面实现那些原本应该在解释器中实现机制：计算的延续（一）：Continuation 介绍
（完）
参考链接：