基于文本替换的解释器：加入continuation，重构解释器2015-01-12或许在加入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*}（fixX1X2M）,κv→v λX2.M[X1←（fixX1X2M）],κc
基本运算
用$（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*}（onM1M2...Mn）,κv V,opd,κ,on,（Mi+1...Mn）,（V1...Vi1）c V,opd,κ,on,（）,（V1...Vn1）c →v→c→c M1,opd,κ,on,（M2...Mn）,（）v Mi+1,opd,κ,on,（...Mn）,（V1...Vi1V）v V′,κc其中V′=on（V1,...,Vn1,V）
函数调用
函数调用$（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*}κ =||...arg,κ,Nfun,κ,V
代码实现
函数value-of/k是$
ightarrow_v$。 函数apply-cont是$
ightarrow_c$。 编写代码要注意对value-of/和apply-cont的调用都必须是尾调用。过程$
ightarrow_v$的代码：
易网时代-编程资源站