简单易懂的程序语言入门小册子(6):基于文本替换的解释器,引入continuation (2)

加入continuation后的求值过程如下: \begin{equation*}\begin{array}{lcl}   \left<double(0), \kappa\right>_v &\rightarrow_{v}& \left<0, \kappa\right>_c \\   \left<double(n), \kappa\right>_v &\rightarrow_{v}& \left<double(m), \left<\kappa, +2\right>\right>_v \\                                         && \text{其中} n \neq 0, m = n - 1 \\   \left<n, \left<\kappa, +2\right>\right>_c &\rightarrow_{c}& \left<m, \kappa\right>_c \\                                      && \text{其中} m = n + 2 \\   \left<n, {mt}\right>_c &\rightarrow_{c}& \text{输出} n \end{array}\end{equation*} 下面解释一下。 计算开始时的状态表示为$\left<double(n), {mt}\right>_v$。 下标v表示第一个状态量是一个表达式,要对这个表达式求值。 用箭头$\rightarrow$表示一步,带下标v的箭头$\rightarrow_v$表示这一步对表达式求值, 带下标c的箭头$\rightarrow_c$表示这一步从continuation中取出一件备忘的事执行。 对于$n \neq 0$,$\left<double(n), \kappa\right>_v$的下一步要做的是,计算$double(n-1)$,同时将加2备忘到$\kappa$, 也就是$\left<double(m), \left<\kappa, +2\right>\right>_v$,其中$m=n-1$。 当$n = 0$时,$double(0)$求得值$0$,所以$\left<double(0), \kappa\right>_v \rightarrow_{v} \left<0, \kappa\right>_c$。 用下标c表示第一个状态是一个数字,下一步该从continuation取出备忘的事来办了。 最后是$\left<n, \kappa\right>_c$的情况,如果$\kappa$不是空:$\kappa=\left<\kappa\',+2\right>$,就加2到$n$上; 如果$\kappa$是空:$\kappa={mt}$,说明continuation没事了,而这时表达式也求完了,于是返回最终结果$n$。

然后是写代码。 针对$\rightarrow_v$和$\rightarrow_c$需要两个函数。 函数value-of/k是$\rightarrow_v$(Lisp命名规范里一般用斜杠表示with的意思)。 函数apply-cont是$\rightarrow_c$。

double1

double2

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

空mt是一个直接返回参数的函数(lambda (v) v)。 $\left<\kappa, +2\right>$先加2,然后应用$\kappa$:(lambda (v) (apply-cont cont v)),其中cont是$\kappa$。 完整代码:

double-proc

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

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

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zgzdsy.html