作为程序员，我们的思维往往被使用的编程语言潜移默化地塑造而不自知。语法层面，我们对 C-family 语法感到熟悉，但面对 ML-family 与 Lisp-family 的代码，就会感到陌生甚至不适。在控制流(control flow)方面，我们习惯的是顺序、分支、循环，以及函数调用、异常等等，如果要让大脑学适应新的控制流机制，则要花费相当多的精力。我在学习 C 的 setjmp/longjmp 和 Python 的 generator 时就感觉到，已经习惯的旧东西会成为学习新东西的阻碍。
有一句名言，A language that doesn’t affect the way you think about programming is not worth knowing，call/cc 与 continuation 正是能够改变我们编程思维方式的东西。call/cc 与 continuation 是一种更强大的控制流机制，有了 call/cc 与 continuation，所有控制结构都可以「退化」为库函数。许多公认只能在语言层面实现的特性，比如 exception，generator，coroutine 等，都可以通过 call/cc 与 continuation 自己 DIY 出来。
什么是 continuation？
Whenever a Scheme expression is evaluated there is a continuation wanting the result of the expression. The continuation represents an entire (default) future for the computation.
Continuation 是程序运行时的概念。作为基于表达式的语言，一个 Scheme 程序运行时，就是对一个个的表达式求值。对一个表达式求值时，拿到值之后的「所有后续计算」，就是它的 continuation。
从表达式的「所有后续计算」这个意义来说，所有语言都有 continuation 的概念。然而只有 Scheme 系语言(包括 Racket)，支持通过 call/cc 函数捕获 continuation，并且操作它。所以，在 Scheme/Racket 中 continuation 是 first-class 的。
我们来看几个例子。
> (+ 1 2)
> (+ 1
(* 2 3))
> (define x '(1 2 3)
> (if (null? x) '() (cdr x))
> (define (foo) 42)
> (let ([x 1])
(+ 1 x))
在 (+ 1 2) 中，表达式 1 的 continuation 是将之与 2 相加；表达式 2 的 continuation 是将之与 1 相加。
在 (+ 1 (* 2 3)) 中，表达式 (* 2 3) 的 continuation 是，将其值 6 与 1 相加；表达式 1 的 continuation 是将之与已经计算出的 6 相加。而表达式 2 的 continuation 是，将之与 3 相乘后，将积与 1 相加。
在 (if (null? x) '() (cdr x)) 中，表达式 (null? x) 的 continuation 是，如果其值为真则返回 '()，否则返回 (cdr x) 的值。而表达式 '() 没有 continuation，因为 x 非空，导致 '() 不会被求值。表达式 (cdr x) 的 continuation 是，返回其值。
在 (define (foo) 42) 中，42 的 continuation 是，将其值作为函数返回值返回。
在 (let ([x 1]) (+ 1 x)) 中，[x 1] 的 continuation 是，将 1 绑定到 x 并计算 (+ 1 x) 的值作为 let 表达式的值。而 (+ 1 x) 的 continuation 则是，以其值作为 let 表达式的返回值。
需要特别注意的是，函数作为程序的最小构造，「以函数为单位进行思考」已经深深根植于我们的思维之中，甚至成为思想钢印。但 continuation 天然是跨越函数边界的，它代表的是「所有后续计算」，着眼于整个程序。意识到这一点有助于我们正确理解 continuation。上面的简单例子均未体现这一点，在后续的例子中我们会逐步加深理解。
call/cc 与 continuation
Scheme/Racket 提供的 call-with-current-continuation 函数，可以捕获 continuation，我们一般使用缩写名 call/cc。
一个表达式的 continuation，是拿着表达式的值所进行的「所有后续计算」。从函数的角度看，continuation 很像函数，它接受一个参数，即表达式的值。事实上 call/cc 捕获的 continuation 我们可以当作函数使用。
call/cc 接受一个函数为参数，以捕获的 continuation 为参数调用这个函数，并以函数的返回值作为 call/cc 的返回值。我们通常使用 lambda 表达式作为 call/cc 的参数，如：
> (call/cc (lambda (k)
(printf "procedure? ~a\n" (procedure? k))
(printf "continuation? ~a\n" (continuation? k))
42))
procedure? #t
continuation? #t
42
这个例子中，call/cc 捕获了 continuation 并作为参数传给 lambda 表达式，而且以 lambda 表达式的返回值为 call/cc 的返回值。
procedure? 返回 #t，说明 continuation 同时是一个函数。而且，在 Racket 中我们可以用 continuation? 函数判断一个值是否为 continuation (Chez Scheme 无此函数)。
我们可以把 continuation 保存下来，像对待其他值那样。
> (define cc #f)
> (call/cc (lambda (k)
(set! cc k)))
> cc
#<procedure>
接下来，我们要搞明白两个问题：
- call/cc 捕获的是谁的 continuation？
- 我们把 continuation 当作函数进行调用时，会发生什么？
call/cc 捕获的是谁的 continuation？
第一个问题比较简单，我们捕获的是函数调用表达式 (call/cc ...) 的 continuation，这个 continuation 以 (call/cc ...) 的返回值为参数，执行「所有后续计算」。
我们可以通过一个例子来了解概念的细节之处。
> (+ 1 (call/cc (lambda (k) 2)))
3
这里，call/cc 捕获的是函数调用表达式 (call/cc ...) 的 continuation，这个 continuation 将 (call/cc ...) 的返回值与 1 相加。注意，捕获的不是表达式 call/cc 的 continuation，这个 continuation 是「将 call/cc 当作函数调用，取其结果与 1 相加」。
我们可以这样验证：
> (define cc #f)
> (+ 1 (call/cc (lambda (k)
(set! cc k)
2)))
3
> (cc 2)
3
> (cc 1)
2
将捕获的 continuation 保存到 cc 变量，然后把 cc 当作函数调用。作为函数，cc 将参数值与 1 相加并返回，符合我们对这个 continuation 的描述。
实际应用时，我们想要捕获哪个表达式的 continuation，就可以将它以 (call/cc ...) 替换，并把表达式放到 ... 里面的 lambda 表达式里。
正如这个例子所示，想要捕获 (+ 1 2) 中 2 的 continuation，就把 2 替换掉，整个表达式改写为 (+ 1 (call/cc (lambda (k) 2)))。如果要捕获 (+ 1 (* 2 3)) 中 (* 2 3) 的 continuation，就改写为 (+ 1 (call/cc (lambda (k) (* 2 3))))。如果要捕获 (if (null? x) '() (cdr x)) 中 (null? x) 的 continuation，就改写为 (if (call/cc (lambda (k) (null? x))) '() (cdr x))。依此类推。
调用 continuation 时，会发生什么？
再看第二个问题。如果把 continuation 当作函数进行调用，就会有神奇的事情发生，这也是 call/cc 与 continuation 强大但又难以理解的原因。
如果前所述，一个表达式的 continuation 就像一个函数，它以表达式的值为参数，执行该表达式的「所有后续计算」。作为函数调用 continuation 时，Scheme/Racket 会立即丢弃当前上下文，并恢复捕获 continuation 时的上下文，此上下文中 (call/cc ...) 刚刚返回，返回值则是调用 continuation 的参数值，并执行「所有后续计算」。注意，作为函数调用 continuation，会跳到 (call/cc ...) 刚刚返回的位置（因此不会执行 call/cc 里面的 lambda 表达式），再往后执行。
以函数调用进行不精确类比的话，调用 continuation 时，Scheme/Racket 立即清空当前调用栈，恢复捕获 continuation 时的调用栈，此调用栈的状态是，(call/cc ...) 刚刚返回，返回值是传给 continuation 的参数，然后继续执行。这意味着 continuation 可以从某个函数中间(通过清空调用栈方式)，直接跳到不相干的任意位置（由 (call/cc ...) 标识），继续执行。
> (+ 1
(call/cc (lambda (k)
(k 666)
2)))
667
在这个例子中，(k 666) 将会丢弃当前上下文(lambda 表达式的上下文)，所以后面的表达式 2 将不会被执行。此时恢复到的上下文中， (call/cc ...) 刚刚返回，返回值为传入的参数 666，然后继续执行后续计算，因此得到 667。
我们换个例子，「丢弃当前上下文，并恢复捕获 continuation 时的上下文」这一行为将会体现得更加明显。
> (define cc #f)
> (let ([x (call/cc (lambda (k)
(printf "binding x...\n")
(set! cc k)
1))]
[y (begin
(printf "binding y...\n")
2)])
(printf "x=~a, y=~a\n" x y)
(+ x y))
binding x...
binding y...
x=1, y=2
3
> (define (foo)
(printf "entering foo\n")
(cc 666)
(printf "exiting foo\n"))
> (define z (foo))
entering foo
binding y...
x=666, y=2
668
> z
z: undefined;
cannot reference an identifier before its definition
in module: top-level
[,bt for context]
这个例子中，我们捕获的 continuation 是：将 (call/cc ...) 的返回值绑定到 x；打印 binding y... 并把 2 绑定到 y，然后执行 let 语句的 body 部分，即打印 x 和 y 的值并返回二者的和。
第一次执行 let 表达式时，一切平平无奇。先对函数调用 (call/cc ...) 求值，它捕获了 continuation 并执行 lambda 表达式。lambda 表达式打印 binding x ...，将捕获的 continuation 赋值给 cc，并返回 1。此时 (call/cc ...) 的返回值即为 lambda 表达式的值 1。接着按照 let 表达式的规则，将 1 绑定到 x，然后打印 binding y... 并把 2 绑定到 y。最后执行 let 语句的 body 部分，打印 x 和 y 的值。
当我们定义了 foo 函数并且调用 (define z (foo)) 时，神奇的事情发生了。它先正常执行，打印 entering foo，然后通过 (cc 666) 调用 continuation，此时 Scheme/Racket 立即丢弃当前 foo 的上下文，foo 函数的最后一行不会被执行，z 也未绑定。此时控制流恢复到捕获 continuation 时的上下文，开始执行 let 表达式。它将传入的参数 666 作为 (call/cc ...) 的返回值（这次不会执行 call/cc 里面的 lambda 表达式了），继续执行 let 的剩余部分。
有几个点值得强调一下。调用 continuation 时，是以传入的参数作为 (call/cc ...) 的返回值，不会执行 （call/cc ...) 里面的 lambda 表达式，证据是没有打印 binding x...。而且 (define z (foo)) 上下文直接被丢弃了，控制流在 foo 执行到一半就跳走了，foo 没有返回，z 也变成未定义。
至此，第二个问题「我们把 continuation 当作函数进行调用时，会发生什么」也可以回答了。如果我们将捕获的 continuation 当作函数调用，就会发生神奇的事情。运行时将立即丢弃当前上下文，恢复捕获 continuation 时的上下文，并且以传给 continuation 的参数作为 (call/cc ...) 的返回值，程序从「(call/cc ...) 刚刚返回」这个点开始执行「所有后续计算」。
call/cc 与 continuation 为何如此强大？
调用 (call/cc ...) 时，会捕获 continuation 并「保存上下文」，作为函数调用 continuation 时则会恢复保存的上下文，并跳转到此处。这种「保存上下文」并随时跳转到任意指定位置的能力，是一种强大且灵活的控制流。前面提到，有了 call/cc 与 continuation，所有控制结构都可以退化为库函数，正是这个原因。
我们熟悉的分支与循环结构，可直接对应到硬件层面的跳转指令，而且无法跳出当前函数。异常，则借助调用栈，抛出异常时进行栈展开(unwind)操作，一次 pop 一个栈帧，对应跨越一个函数，但它只是「单向跳转」。
而 continuation，则直接丢掉当前调用栈，替换成捕获 continuation 时保存的调用栈（语义如此，不一定实现也如此）。它不借助调用栈单向跳转，可跨越任意函数，支持任意方向，比分支、循环、异常等机制强大且灵活得多。有趣的是，Racket 的异常系统，就是通过 continuation 实现的。
更复杂的控制结构，比如 generator 和 coroutine，也可借助 call/cc 与 continuation 来实现。
call/cc 与 continuation 的使用
提前退出
Lisp 语言不支持 return，但只要我们把函数的主体代码放到 (call/cc ...) 里面，即可实现 return，拥有提前退出的能力。
(define (foo)
(call/cc
(lambda (return)
(...)
(when ready (return 42))
(...))))
这个例子中，捕获的 continuation 是，使函数 foo 返回（及所有后续步骤）。在 foo 内部任意位置调用捕获的 continuation (return)，就会导致 foo 立即返回。
TSPL 中就有类似的例子：
(define product
(lambda (ls)
(call/cc
(lambda (break)
(let f ([ls ls])
(cond
[(null? ls) 1]
[(= (car ls) 0) (break 0)]
[else (* (car ls) (f (cdr ls)))]))))))
(product '(1 2 3 4 5)) ; 120
(product '(7 3 8 0 1 9 5)) ; 0
product 函数对列表中所有元素相乘，并返回乘积。但是，如果遍历的时候遇到 0，就直接返回 0，避免执行多余的乘法操作。
循环
另外，Lisp 语言天生不支持循环，通过 call/cc 与 continuation 实现循环，及相应的 break，continue 功能，也是非常简单的。
> (define (loop)
(define i 0)
(define reborn #f)
(call/cc (lambda (k)
(set! reborn k)))
(when (< i 5)
(printf "i=~a\n" i)
(set! i (+ i 1))
(reborn)))
> (loop)
i=0
i=1
i=2
i=3
i=4
这个 loop 函数，演示了通过 call/cc 和 continuation 实现循环的方法。先通过 (call/cc ...) 设置好循环标识，需要进行下一轮循环时，调用 continuation 就会跳转回这个标识。
以下代码展示了使用这个技术实现的猜数字游戏。
;;; read a integer from stdin.
(define (read-integer)
(printf "Enter your guess: ")
(let ([n (read)])
(if (integer? n)
n
(begin (printf "Invalid input! Please enter an integer.\n")
(read-integer)))))
(define (guess-game)
(define answer (random 100))
(define remaining-attempts 5)
(define (read-guess)
(set! remaining-attempts (- remaining-attempts 1))
(read-integer))
(define reborn #f)
(call/cc (lambda (k)
(set! reborn k)))
(define guess (read-guess))
(cond
[(= guess answer) (printf "Correct! You WIN!\n")]
[(<= remaining-attempts 0) (printf "You lose! The answer is ~a\n" answer)]
[else
(let ([prompt (if (< guess answer) "Too low!" "Too high")])
(printf "~a\n" prompt)
(reborn))]))
运行结果如下：
> (guess-game)
Enter your guess: 50
Too high
Enter your guess: 24
Too high
Enter your guess: 11
Too low!
Enter your guess: 17
Too high
Enter your guess: 14
You lose! The answer is 16
这个例子有一点值得注意。我们在通过 (reborn) 调用 continuation 时，并没有提供参数。事实上，调用 continuation 时是否需要提供参数，完全视 (call/cc ...) 所属表达式的需要，有可能需要提供 0 个、1 个或多个参数。假如调用 continuation 时传入了多个参数，那么 (call/cc ...) 的返回值就是多值，我们需要通过 define-values 或 let-values 之类的表达式来处理。这样我们可以视需要，决定跳转时传回的值的数量。
此例子中，(call/cc ...) 的返回值直接被丢弃，所以这里不提供参数，或者提供 1 个或多个参数，都是可以的。假如把示例中的 (call/cc (lambda (k) (set! reborn k))) 这一行改为 (define x (call/cc (lambda (k) (set! reborn k))))，那么我们调用 continuation 时就必须传入一个参数。如果改为 (define-values (x y) (call/cc (lambda (k) (set! reborn k) (values 1 2))))，那么调用 continuation 时必须传入两个参数。
只允许「穿越」一次
前面强调过，我们习惯于以函数为单位进行思考，而 continuation 天然是跨越函数边界的，它代表的是「所有后续计算」，着眼于整个程序。这意味着，当我们读函数代码时遇到 call/cc，需要关注这个函数是如何被调用（及间接被调用）的，才能真正理解。前面的例子都是在 REPL 里面，即 top-level 演示 call/cc 的用法，鲜少涉及函数，容易让我们忽略这个问题。
这里我们看一个有点绕的例子：
> (define (current-continuation)
(call/cc (lambda (cc) (cc cc))))
> (define x (current-continuation))
> x
#<procedure>
> (continuation? x)
#t
> (x 123)
> x
123
current-continuation 函数中的 (call/cc ...) 捕获的 continuation 是，让 current-continuation 函数返回（及所有后续，即，将返回值绑定到 x）。在 lambda 表达式中直接调用这个 continuation (cc cc)，则让 current-continuation 立即返回，返回值为 cc。于是 x 的值绑定为 cc。当我们调用 (x 123) 时，即调用了捕获的 continuation，此时将导致之前捕获 continuation 时的上下文，使得 (call/cc ...) 再次返回，返回值为 123，并把 123 绑定到 x 上。于是，x 的值变为 123 了。
这个例子很好的展示了，我们读函数代码时遇到 call/cc，一定要关注这个函数是如何被调用（甚至间接被调用）的，才能真正理解。
当然，这个 current-continuatin 有点故意写得很绕，简单一点行为是一样的。
> (define (current-continuation2)
(call/cc (lambda (cc) cc)))
> (define x2 (current-continuation2))
> x2
#<procedure>
> (continuation? x2)
#t
> (x2 123)
> x2
123
>
这个函数，可用来实现「只允许穿越一次」的模式。因为调用 x 一次之后，它就不再是 continuation 了，无法再次被调用。
(let ([k (current-continuation)])
(cond
[(continuation? k)
; do the job...
(printf "first run\n")
(k 42)]
[else (printf "back from the future, with value = ~a\n" k)]))
generator
接下来，我们再演示一下如何用 call/cc 与 continuation 实现 generator。Python 的 generator 示例如下，我们的实现尽量与 Python 版的接近。
def gen():
x = 0
while x < 3:
yield x
x += 1
g = gen()
next(g) # 0
next(g) # 1
next(g) # 2
next(g) # raise StopIteration
这里的关键点是，创建 generator 实例时，并不立即执行。当通过 next 调用时，则开始执行，并以 yield 处的值作为返回值，并且将执行状态保存下来。再次调用 next 时，从保存的状态中恢复，从上次 yield 的地方继续往后执行，直到再次遇到 yield，就再次暂停并返回。执行完毕后，再次调用 next 将会抛出 StopIteration 异常。
用 call/cc 与 continuation 实现的异常如下：
(define (make-generator procedure)
(define last-return #f)
(define (last-continuation)
(let ((_result (procedure yield)))
(error 'StopIteration)))
(define (yield value)
(call/cc (lambda (continuation)
(set! last-continuation continuation)
(last-return value))))
(lambda ()
(call/cc (lambda (return)
(set! last-return return)
(last-continuation)))))
注：这个 generator 的实现来自于这里，并稍加改动以贴近 Python generator 的行为。
我们演示一下：
> (define g (make-generator (lambda (yield)
(let loop ([x 0])
(when (< x 3)
(yield x)
(loop (+ x 1)))))))
> (g)
0
> (g)
1
> (g)
2
> (g)
error: StopIteration [,bt for context]
yield 是 Python 的关键字，这里以函数方式提供。make-generator 接受一个 lambda 表达式，里面是 generator 本身的逻辑。lambda 表达式接受一个参数 yield，用于产生一个值并暂停执行。
make-generator 返回的是也 lambda 表达式，因此 generator 实例同时也是函数，每次调用便产生一个值。这个 lambda 表达式里只有一个 (call/cc ...)，捕获的 continuation 被调用时将使得 lambda 表达式返回。这个 continuation 在 yield 函数中被使用，每次 yield 时就通过它从 lambda 表达式返回。
而且 yield 函数也捕获了 continuation，它代表 generator 的执行状态。第一次执行 (g) 时，会调用 last-continuation 函数，这个函数的主体是 let 表达式，它对 generator 的主体逻辑(procedure) 求值，驱动 generator 的执行。执行过程中，yield 捕获 continuation 时，仍处在 let 的上下文中。因此 continuation 的逻辑，是包括「完成对 procedure 的调用，并抛出 'StopIteration」的。虽然每次调用 yield 时，都将 last-continuation 赋值为刚刚捕获的 continuation，但每个 continuation 的逻辑均包含「完成对 procedure 的调用，并抛出 'StopIteration」。正因为如此，虽然第二次及之后调用 (g)，last-continuation 已被替换为 continuation 对象，而非原始的函数，最后当 (procedure yield) 完成求值之后，仍然会抛出 'StopIteration。
这个例子是比较难理解的。如果我们能够明白每一个步骤，那么对 call/cc 与 continuation 的理解，就比较到位了。在尝试理解的过程中，一定要关注一个包含 call/cc 函数是如何被调用（甚至间接被调用）的，才能真正理解，并且摒弃「以函数为最小单元」的思维惯性。另外，即使理解了 call/cc 与 continuation，想要写出这样复杂烧脑的代码，恐怕还是很难的。
至于 exception 和 coroutine，也都可以通过 call/cc 与 continuation 来实现，这里就不再举例子了。Racket 标准库已提供了 exception 和 generator
总结
表达式的 continuation 就像一个函数，它以表达式的值为参数，执行「所有后续计算」。所有语言均存在 continuation，但只有 Scheme/Racket 允许我们通过 call/cc 捕获并操作 continuation。在 Scheme/Racket 中，continuation 是 first-class 的。
call/cc 捕获的是函数调用表达式 (call/cc ...) 的 continuation，它以 (call/cc ...) 的返回值为参数，执行「所有后续计算」。而 (call/cc ...) 的返回值，是调用它里面的 lambda 表达式的值。
如果我们将捕获的 continuation 当作函数调用，就会发生神奇的事情。运行时将立即丢弃当前上下文，恢复捕获 continuation 时的上下文，并且以传给 continuation 的参数作为 (call/cc ...) 的返回值，程序从「(call/cc ...) 刚刚返回」这个点开始执行「所有后续计算」。
函数作为程序的最小构造，「以函数为单位进行思考」已经深深根植于我们的思维之中，甚至成为思想钢印。但 continuation 天然是跨越函数边界的，它代表的是「所有后续计算」，着眼于整个程序。我们阅读函数代码时遇到 call/cc，一定要关注这个函数是如何被调用（甚至间接被调用）的，才能真正理解。