基于文本替换的解释器：加入整数类型

基于文本替换的解释器：加入整数类型2015-01-09为了有条不紊地实现一个解释器，我将按以下三个步骤走：

1.明确语法

2.针对语法描述求值过程

3.根据求值过程编写代码实现

语法

（lambda）演算不适合作为一门实际使用的程序语言。（lambda）演算只有变量和函数两种类型，而其他常用类型如整数、布尔、字符等都没有。虽然可以通过编码的方式表示这些常用类型，但这样也很麻烦。通常直接扩展（lambda）演算，加入一些常用类型以及针对这些类型的基本运算。这种扩展后的语言简称为ISWIM，全称未知……

为简单起见，我只加入整数类型，以及加法和减法。扩展后的语法如下： egin{eqnarray*} M, N, L &=& X \ &|& b \ &|& lambda X.M \ &|& （+ ; M ; N） \ &|& （- ; M ; N） \ &|& （M ; N） end{eqnarray*} 新加入的第二行（b）表示一个整数，第四行是一个加法运算的表达式，第五行是一个减法运算的表达式。

求值过程

为了描述一个计算这门语言的解释器的求值过程，首先要明确求值停止条件。我们规定当归约到（X），（b），（lambda X.M）这三种表达式之一时，认为解释器已经求出了最终结果。这三种表达式称为值，用字母（V）表示。 egin{eqnarray*} V &=& X \ &|& b \ &|& lambda X.M end{eqnarray*}

用记号（eval（M））表示表达式（M）的求值结果。对于值，求值只需返回它们自身。 egin{eqnarray*} eval（X） &=& X \ eval（b） &=& b \ eval（lambda X.M） &=& lambda X.M end{eqnarray*} 加减法和函数调用这三行是递归定义，所以求值过程也是递归的。 egin{eqnarray*} eval（（+ ; M ; N）） &=& eval（（+ ; V_1 ; V_2）） \ eval（（- ; M ; N）） &=& eval（（- ; V_1 ; V_2）） \ eval（（M ; N）） &=& eval（（V_1 ; V_2）） end{eqnarray*} 其中（V_1=eval（M）），（V_2=eval（N））。

为了让解释器尽量简单，假设输入的程序是正确的。也就是说，对于加减法运算的（V_1）和（V_2）都是整数，记为（b_1）和（b_2）；函数调用里的（V_1）是一个函数（lambda X.L）。

加减法如字面本意，就是作加减法。函数调用过程是一个（eta）归约过程。 egin{eqnarray*} eval（（+ ; b_1 ; b_2）） &=& b_1 + b_2 \ eval（（- ; b_1 ; b_2）） &=& b_1 - b_2 \ eval（（lambda X.L ; V_2）） &=& eval（L[X leftarrow V_2]） end{eqnarray*}

由于加入了新的语法，替换过程也要添加相应的过程。这里列上整个替换过程： egin{eqnarray*} X_1[X_1 leftarrow N] &=& N \ X_2[X_1 leftarrow N] &=& X_2 \ &&其中X_1 eq X_2 \ b[X leftarrow N] &=& b \ （lambda X_1.M）[X_1 leftarrow N] &=& （lambda X_1.M） \ （lambda X_1.M）[X_2 leftarrow N] &=& （lambda X_3.M[X_1 leftarrow X_3][X_2 leftarrow N]） \ &&其中X_1 eq X_2, X_3 otin FV（N）, X_3 otin FV（M）ackslash{X_1} \ （+ ; M_1 ; M_2）[X leftarrow N] &=& （+ ; M_1[X leftarrow N] ; M_2[X leftarrow N]） \ （- ; M_1 ; M_2）[X leftarrow N] &=& （- ; M_1[X leftarrow N] ; M_2[X leftarrow N]） \ （M_1 ; M_2）[X leftarrow N] &=& （M_1[X leftarrow N] ; M_2[X leftarrow N]） end{eqnarray*}

最后总结求值过程如下： egin{eqnarray*} 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（（M ; N）） &=& eval（L[X leftarrow eval（N）]） \ && 其中 eval（M） = lambda X.L end{eqnarray*}

实现

这里使用Racket语言来编写解释器。解释器输入不使用字符串，而是用Racket的符号系统。使用符号系统是为了简化语法分析的工作。利用Racket的模式匹配可以方便地实现语法分析。另外，计算机输入（lambda）还是很麻烦的，所以在具体实现的语言中用（lambda X M）代替（lambda X.M）。

解释器是一个实现了（eval）函数的程序。代码是求值过程的公式逐句转换，就不一一解释了。 value-of是求值过程：