当我写到这里的时候，我自己都吃了一惊。 环境、存储这些比较让人耳熟的还没讲到，continuation先出来了。 维基百科里对continuation的翻译是“延续性”。 这翻译看着总有些违和感而且那个条目也令人不忍直视。 总之continuation似乎没有好的中文翻译，仿佛中国的计算机科学里没有continuation这个概念似的。

Continuation这个概念相当于过程式语言里的函数调用栈。 它是用于保存“现在没空处理，待会再处理的事”的数据结构。 这样说有点抽象，举个例子，函数应用那条表达式的求值过程（call-by-value）是这样：

  eval((MN))                 =eval(L[X←eval(N)])其中eval(M)=λX.L

1. 计算eval(M)<script id="MathJax-Element-2" type="math/tex">eval(M)</script> ，结果是λX.L<script id="MathJax-Element-3" type="math/tex">\lambda X.L</script> ，
2. 计算eval(N)<script id="MathJax-Element-4" type="math/tex">eval(N)</script> ，
3. 做替换L[X←eval(N)]<script id="MathJax-Element-5" type="math/tex">L[X \leftarrow eval(N)]</script> 。

解释器一次只能计算一个表达式，所以当它计算eval(M)<script id="MathJax-Element-6" type="math/tex">eval(M)</script>前，要先把第二步和第三步要做的事备忘到continuation。

假设M<script id="MathJax-Element-7" type="math/tex">M</script>还是个函数调用M=(M1M2)<script id="MathJax-Element-8" type="math/tex">M=(M_1 \; M_2)</script>。 那么，计算eval(M)<script id="MathJax-Element-9" type="math/tex">eval(M)</script>又要分三步： 先计算eval(M1)=λX.L1<script id="MathJax-Element-10" type="math/tex">eval(M_1)=\lambda X.L_1</script>，第二步计算eval(M2)<script id="MathJax-Element-11" type="math/tex">eval(M_2)</script>，第三步做替换L1[X←eval(M2)]<script id="MathJax-Element-12" type="math/tex">L_1[X \leftarrow eval(M_2)]</script>。 解释器只能先计算eval(M1)=λX.L1<script id="MathJax-Element-13" type="math/tex">eval(M_1)=\lambda X.L_1</script>，将第二步计算eval(M2)<script id="MathJax-Element-14" type="math/tex">eval(M_2)</script>，第三步做替换L1[X←eval(M2)]<script id="MathJax-Element-15" type="math/tex">L_1[X \leftarrow eval(M_2)]</script>备忘到continuation。 于是，continuation备忘的事情按待处理的顺序依次是：

1. 计算eval(M2)<script id="MathJax-Element-16" type="math/tex">eval(M_2)</script> ，
2. 做替换L1[X←eval(M2)]<script id="MathJax-Element-17" type="math/tex">L_1[X \leftarrow eval(M_2)]</script> 。
3. 计算eval(N)<script id="MathJax-Element-18" type="math/tex">eval(N)</script> ，
4. 做替换L[X←eval(N)]<script id="MathJax-Element-19" type="math/tex">L[X \leftarrow eval(N)]</script> 。

可以看到，continuation是一个FILO（先进后出）的数据结构，也就是栈。

在之前的解释器里并没有提到continuation，但是解释器仍然能正常工作， 这是因为解释这个解释器的解释器——Racket解释器——帮我们管理了continuation。 这一节的目标是自己管理continuation。

从一个简单的递归函数做起

先说一个概念：尾调用。 假设一个函数体中有一句函数调用表达式(fn)<script id="MathJax-Element-20" type="math/tex">(f \; n)</script>，这个函数调用被称为尾调用，如果这条表达式是函数体里最后求值的表达式。 如λn.(fn)<script id="MathJax-Element-21" type="math/tex">\lambda n.(f \; n)</script>，和λn.(if(iszeron)0(fn))<script id="MathJax-Element-22" type="math/tex">\lambda n.({if} \; ({iszero} \; n) \; 0 \; (f \; n))</script>中的(fn)<script id="MathJax-Element-23" type="math/tex">(f \; n)</script>都是尾调用。 而λn.(+1(fn))<script id="MathJax-Element-24" type="math/tex">\lambda n.(+ \; 1 \; (f \; n))</script>中的(fn)<script id="MathJax-Element-25" type="math/tex">(f \; n)</script>不是尾调用，因为计算完(fn)<script id="MathJax-Element-26" type="math/tex">(f \; n)</script>后还要再算个加法。 一个简单的判断是否尾调用的方法是看这条调用表达式是不是不在一个参数位置（let表达式和if表达式先做宏展开）。

学过C或者C++都知道，调用函数的时候是要保存信息到函数调用栈的（我上学时学的这俩，不知道其他语言的课上会不会讲函数调用栈）。 尾调用的特点是：尾调用理论上不需要保存信息到函数调用栈——实际上也不需要，但是有些语言就不支持，比如说Python。 换句话说，尾调用不会导致continuation增长。 这个很好理解，因为尾调用是最后求值的表达式了，不需要备忘后面要做的事（后面没有事了），所以也就不会导致continuation增长。 后面会从continuation的角度说明为什么尾调用不会令continuation增长。

题外话： 刚才提到“理论上”和“实际上”。 经常能听到这种句式：理论上怎么怎么，可惜，实际上是吧啦吧啦。 其中“吧啦吧啦”是一句对“怎么怎么”的否定。 我觉得这是反科学以及读书无用论的潜意识在作祟，另外有时候是用来逃避责任的借口。 理论上怎么样，实际上就应该怎么样。 如果有套理论的结论和现实的结果不同，那么这就不能称为理论，最多算个猜想，而且是个错误的猜想。

如果一个尾调用是一个递归调用，那么就称为尾递归。 尾递归又叫迭代。 我们现在要做的事其实就是把一个递归程序（之前写的解释器）中的非尾递归全改成尾递归， 也就是递归转迭代。

为了熟悉递归转迭代的套路，先拿一个简单的递归函数练练手。 这个函数就是之前用到的double函数：

  double(0)  double(n)==02+double(n?1),其中n≠0

double(n)

n

κ

κ

  κ         =|mt?κ,+2?

加入continuation后的求值过程如下：

  ?double(0),κ?v  ?double(n),κ?v                                          ?n,?κ,+2??c                                       ?n,mt?c→v→v→c→c?0,κ?c?double(m),?κ,+2??v其中n≠0,m=n?1?m,κ?c其中m=n+2输出n

_v &\rightarrow_{v}& \left<0, \kappa\right>_c \\ \left_v &\rightarrow_{v}& \left\right>_v \\ && \text{其中} n \neq 0, m = n - 1 \\ \left\right>_c &\rightarrow_{c}& \left_c \\ && \text{其中} m = n + 2 \\ \left_c &\rightarrow_{c}& \text{输出} n \end{array}\end{equation*}</script> 下面解释一下。 计算开始时的状态表示为?double(n),mt?v<script id="MathJax-Element-34" type="math/tex">\left_v</script>。 下标v表示第一个状态量是一个表达式，要对这个表达式求值。 用箭头→<script id="MathJax-Element-35" type="math/tex">\rightarrow</script>表示一步，带下标v的箭头→v<script id="MathJax-Element-36" type="math/tex">\rightarrow_v</script>表示这一步对表达式求值， 带下标c的箭头→c<script id="MathJax-Element-37" type="math/tex">\rightarrow_c</script>表示这一步从continuation中取出一件备忘的事执行。 对于n≠0<script id="MathJax-Element-38" type="math/tex">n \neq 0</script>，?double(n),κ?v<script id="MathJax-Element-39" type="math/tex">\left_v</script>的下一步要做的是，计算double(n?1)<script id="MathJax-Element-40" type="math/tex">double(n-1)</script>，同时将加2备忘到κ<script id="MathJax-Element-41" type="math/tex">\kappa</script>， 也就是?double(m),?κ,+2??v<script id="MathJax-Element-42" type="math/tex">\left\right>_v</script>，其中m=n?1<script id="MathJax-Element-43" type="math/tex">m=n-1</script>。 当n=0<script id="MathJax-Element-44" type="math/tex">n = 0</script>时，double(0)<script id="MathJax-Element-45" type="math/tex">double(0)</script>求得值0<script id="MathJax-Element-46" type="math/tex">0</script>，所以?double(0),κ?v→v?0,κ?c<script id="MathJax-Element-47" type="math/tex">\left_v \rightarrow_{v} \left<0, \kappa\right>_c</script>。 用下标c表示第一个状态是一个数字，下一步该从continuation取出备忘的事来办了。 最后是?n,κ?c<script id="MathJax-Element-48" type="math/tex">\left_c</script>的情况，如果κ<script id="MathJax-Element-49" type="math/tex">\kappa</script>不是空：κ=?κ′,+2?<script id="MathJax-Element-50" type="math/tex">\kappa=\left<\kappa‘,+2\right></script>，就加2到n<script id="MathJax-Element-51" type="math/tex">n</script>上； 如果κ<script id="MathJax-Element-52" type="math/tex">\kappa</script>是空：κ=mt<script id="MathJax-Element-53" type="math/tex">\kappa={mt}</script>，说明continuation没事了，而这时表达式也求完了，于是返回最终结果n<script id="MathJax-Element-54" type="math/tex">n</script>。

然后是写代码。 针对→v<script id="MathJax-Element-55" type="math/tex">\rightarrow_v</script>和→c<script id="MathJax-Element-56" type="math/tex">\rightarrow_c</script>需要两个函数。 函数value-of/k是→v<script id="MathJax-Element-57" type="math/tex">\rightarrow_v</script>（Lisp命名规范里一般用斜杠表示with的意思）。 函数apply-cont是→c<script id="MathJax-Element-58" type="math/tex">\rightarrow_c</script>。

上面代码中用Lisp里的list数据结构来保存continuation。 我们可以不用list来保存continuation。 Continuation备忘的是“待做的事”。 这个“待做的事”可以理解为一个过程，也就是一个函数。 所以，可以用函数来保存continuation！

空mt是一个直接返回参数的函数(lambda (v) v)。 ?κ,+2?<script id="MathJax-Element-59" type="math/tex">\left<\kappa, +2\right></script>先加2，然后应用κ<script id="MathJax-Element-60" type="math/tex">\kappa</script>：(lambda (v) (apply-cont cont v))，其中cont是κ<script id="MathJax-Element-61" type="math/tex">\kappa</script>。 完整代码：

用函数来保存continuation的写法看起来蛮像回调函数（callback）。 Lisp的一个噱头是程序与数据统一对待，这也算是一个体现吧。 用函数还能实现对象（面向对象编程的对象），这是题外话了。 用函数保存数据一个好处是熟悉这种方法后写起来很方便； 坏处是扩展访问方式比较麻烦，并且调试的时候不能打印详细信息。

顺便再说一下，这种带着一个continuation当参数传来传去的代码风格叫continuation passing style，也就是传说中的CPS。 将一段不带continuation的代码转换成continuation passing style的过程叫CPS变换。 （更准确的说，CPS变换是指将代码中的非尾调用转换成尾调用。）