或许在加入continuation之前要先讲讲费这么大劲做这个有什么意义。 毕竟用不用continuation的计算结果都是一样的。 不过，这是一个兴趣使然的系列，学习这些知识应该完全出于好奇与好玩的想法。 所以我才不会告诉你们通过控制continuation可以实现call-with-current-continuation和异常处理等功能呢。
我先简要描述一下加入continuation后解释器是怎么工作的。 加入continuation后的解释器是以迭代的方式工作的。 迭代的状态量有两个，第一个是一个待求值的表达式或者求到的值，第二个是Continuation。 假设解释器的输入是$M$，那么一开始的状态表示为$left<M, {mt} ight>_v$。 第一个状态量是个表达式$M$，这时解释器开始对$M$求值。 这个过程用记号$ ightarrow_{v}$表示。 这个过程可能会将一些“下一步要做的事”保存到continuation。 求值到最后，状态会变为$left<V, kappa ight>_c$（如果没有无限循环）。 注意到下标变成c，$V$是一个值，所以不能再求值了，下一步要做的是从continuation $kappa$中取出“下一步要做的事”执行。 这个过程也叫做“将continuation $kappa$应用到值$V$”，用记号$ ightarrow_{c}$表示。 一个解释器的执行过程就是$ ightarrow_{v}$和$ ightarrow_{c}$交替运行，就好像太极里阴阳交替一样。 解释器执行到最后状态会变成$left<V, {mt} ight>_c$，已求得值$V$，又没有“下一步要做的事”，也就是运行结束了，输出$V$。 说了这么多，本质上整个过程还是一句话：递归转迭代。顺便一提，加入continuation后的解释器叫做CK machine。
先列出目前为止的所有求值过程（call-by-value）： egin{equation*}egin{array}{lcl} eval(X) &=& X \ eval(b) &=& b \ eval(lambda X.M) &=& lambda X.M \ eval((+ ; M ; N)) &=& eval(M) + eval(N) \ eval((- ; M ; N)) &=& eval(M) - eval(N) \ eval(({iszero} ; M)) &=& {true} \ && ext{其中} eval(M) = 0 \ eval(({iszero} ; M)) &=& {false}, \ && ext{其中} eval(M) eq 0 \ eval((M ; N)) &=& eval(L[X leftarrow eval(N)]) \ && ext{其中} eval(M) = lambda X.L \ eval(({fix} ; X_1 ; X_2 ; M)) &=& lambda X_2.M[X_1 leftarrow ({fix} ; X_1 ; X_2 ; M)] end{array}end{equation*} 下面分别介绍各个情况下如何加入continuation。
值与fix表达式
值是最简单的情况，直接应用continuation。 egin{equation*}egin{array}{lcl} left<X, kappa ight>_v & ightarrow_v& left<X, kappa ight>_c \ left<b, kappa ight>_v & ightarrow_v& left<b, kappa ight>_c \ left<lambda X.M, kappa ight>_v & ightarrow_v& left<lambda X.M, kappa ight>_c \ end{array}end{equation*}
fix表达式和值的情况类似： egin{equation*}egin{array}{lcl} left<({fix} ; X_1 ; X_2 ; M), kappa ight>_v & ightarrow_v& left<lambda X_2.M[X_1 leftarrow ({fix} ; X_1 ; X_2 ; M)], kappa ight>_c end{array}end{equation*}
基本运算
用$(o^n ; M_1 ; M_2 ; ... ; M_n)$表示基本运算，其中$o^n$是运算符，$M_1, ..., M_n$是参数，$n$是代表参数个数。 在我们的语言里目前有两个两参数的基本运算$o^2={+, -}$和一个单参数的基本运算$o^1={{iszero}}$。
计算基本运算前要先对所有参数求值。这里规定从左到右求值。 当解释器在求第$i$个参数$M_i$的值时，需要保存到continuation的数据有： 运算符$o^n$、 已求到的值$V_1, ..., V_{i-1}$（其中$V_1=eval(M), ..., V_{i-1}=eval(M_{i-1})$） 以及还没求值的参数$M_{i+1}, ..., M_n$。 因此，包含基本运算的continuation定义为： egin{equation*}egin{array}{lcl} kappa &=& {mt} \ &|& left<{opd}, kappa, o^n, (V_1 ; ... ; V_{i-1}), (M_{i+1} ; ... ; M_n) ight> end{array} end{equation*}
求值过程为： egin{equation*}egin{array}{lcl} left<(o^n ; M_1 ; M_2 ; ... ; M_n), kappa ight>_v & ightarrow_v& left<M_1, left<{opd}, kappa, o^n, (M_2 ; ... ; M_n), () ight> ight>_v \ left<V, left<{opd}, kappa, o^n, (M_{i+1} ; ... ; M_n), (V_1 ; ... ; V_{i-1}) ight> ight>_c & ightarrow_c& left<M_{i+1}, left<{opd}, kappa, o^n, (... ; M_n), (V_1 ; ... ; V_{i-1} V) ight> ight>_v \ left<V, left<{opd}, kappa, o^n, (), (V_1 ; ... ; V_{n-1}) ight> ight>_c & ightarrow_c& left<V', kappa ight>_c \ && ext{其中} V' = o^n(V_1, ..., V_{n-1}, V) end{array}end{equation*}
函数调用
函数调用$(M ; N)$先计算$M$的值，$N$保存到continuation： egin{equation*}egin{array}{lcl} left<(M ; N), kappa ight>_v & ightarrow_v& left<M, left<{arg}, kappa, N ight> ight>_v end{array}end{equation*} $M$计算完后从continuation取出$N$计算（我们采用call-by-value的调用方式），同时保存$M$的计算结果$V$： egin{equation*}egin{array}{lcl} left<V, left<{arg}, kappa, N ight> ight>_c & ightarrow_c& left<N, left<{fun}, kappa, V ight> ight>_v end{array}end{equation*} $N$也计算完后，进行$eta$归约： egin{equation*}egin{array}{lcl} left<V, left<{fun}, kappa, lambda X.L ight> ight>_c & ightarrow_c& left<L[X leftarrow V], kappa ight>_v end{array}end{equation*} 这个地方很有意思，可以看到函数调用最后$eta$归约的过程不会使continuation增长。 所有求值过程中，会导致continuation增长的几个过程是基本运算中对参数的计算过程、函数调用中对函数的计算过程以及对参数的计算过程。 一般也认为函数调用中函数的这个位置（也就是$(M ; N)$中$M$这个位置）也算参数位置， 所以判断一个函数调用是不是尾调用的依据是： 这个函数调用表达式是不是在一个参数位置，如果在参数位置，就不是尾调用。
上面分析的求值过程里增加了两种continuation： egin{equation*}egin{array}{lcl} kappa &=& ... \ &|& left<{arg}, kappa, N ight> \ &|& left<{fun}, kappa, V ight> end{array} end{equation*}
代码实现
函数value-of/k是$ ightarrow_v$。 函数apply-cont是$ ightarrow_c$。 编写代码要注意对value-of/和apply-cont的调用都必须是尾调用。
过程$ ightarrow_v$的代码：
出于写起来方便的原因，使用函数来保存continuation。 用(end-cont)表示空的continuation mt。 (end-cont)只有在程序结束的时候才会运行一次。 这里让(end-cont)打印了个">> Done!"，这个打印只会运行一次。 如果打印了超过一次，或者没打印，那么代码肯定有错。
过程$ ightarrow_c$的代码：
寄存器风格的代码实现
这小节换个方式写代码。 求值过程有两个状态量：当前计算的表达式和当前的continuation。 我们用两个全局变量the-exp和the-cont来保存这两个状态量。 使用全局变量后，函数value-of/k和apply-cont就不再需要参数。 另外，还需要一个全局变量来保存下一步是要进行$ ightarrow_v$还是$ ightarrow_c$。 这个全局变量叫the-pc。 这三个全局变量被称作寄存器（所以叫寄存器风格）。 当the-pc的值为逻辑假#f时，解释器运行结束。 现在解释器运行时就是不断的执行the-pc直到the-pc的值是#f。 mainloop是这个主循环的过程：
进入主循环的过程前要先初始化寄存器：
过程value-of/k不再需要参数，用寄存器the-exp代替原来的exp1，the-cont代替原来的cont。 当然还有其他一些修改。代码如下：
过程apply-cont的修改和value-of/k类似。 代码如下：
思考
- 对宏展开过程translate和替换过程substitute做递归转迭代是否意义不大，为什么？
- 加入continuation后call-by-name的调用方式下的求值过程和代码实现？