简单易懂的程序语言入门小册子（2）：基于文本替换的解释器，加入整数类型

为了有条不紊地实现一个解释器，我将按以下三个步骤走：

明确语法
针对语法描述求值过程
根据求值过程编写代码实现

语法

(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是求值过程：

substitute是替换过程：

在替换过程中有一处需要生成新变量(new-tmp-var)。新变量不能和被代入的表达式中的自由变量重名。一个选取新变量的方法就是选择程序里肯定不会出现的变量名。我假定输入的程序没有以井号“#”开头的变量。新生成的就以井号加数字的方式命名：#1, #2, #3,...。

测试一下：

'a
>> 'a

12
>> 12

'(+ 12 13)
>> 25

'(- 32 23)
>> 9

'(lambda x (+ x 1))
>> '(lambda x (+ x 1))

'((lambda x (- x 1)) 22)
>> 21

'(((lambda x x) (lambda y y)) 11)
>> 11

'(((lambda x (lambda y x)) y) 0)
>> 'y

惰性求值

惰性求值指对一个表达式，只有在需要它的计算结果时才对它求值。

对于函数调用的求值过程，参数(N)可以先不进行求值： egin{eqnarray*} eval((M ; N)) &=& eval(L[X leftarrow N]) \ && 其中 eval(M) = lambda X.L end{eqnarray*} 这种函数调用的求值方式就叫做call-by-name。 Call-by-name是一种惰性求值的调用方式。

在函数调用过程中先对参数求值的调用方式叫做call-by-value。下面用例子展示这两种调用方式的不同。

Call-by-value： egin{eqnarray*} &&(lambda x.(+ ; x ; x) ; (+ ; 2 ; 3)) \ & ightarrow& (lambda x.(+ ; x ; x) ; 5) \ & ightarrow& (+ ; 5 ; 5) \ & ightarrow& 10 end{eqnarray*}

Call-by-name： egin{eqnarray*} &&(lambda x.(+ ; x ; x) ; (+ ; 2 ; 3)) \ & ightarrow& (+ ; (+ ; 2 ; 3) ; (+ ; 2 ; 3)) \ & ightarrow& (+ ; 5 ; 5) \ & ightarrow& 10 end{eqnarray*} Call-by-name的过程中((+ ; 2 ; 3))被计算了两次。为了避免重复计算，有另一种同为惰性求值的调用方式叫call-by-need。 Call-by-need以后再介绍。

在两者都能成功求值的情况下，call-by-name的求值结果和call-by-value的求值结果是一样的。它们的区别在于两者的求值过程不同。看下面这个表达式： [ ((lambda y.lambda x.x ; (lambda x.(x ; x) ; lambda x.(x ; x))) ; (+ ; 12 ; 21)) ]

如果用call-by-value的方式求值，必然要先求((lambda x.(x ; x) ; lambda x.(x ; x)))的值。而((lambda x.(x ; x) ; lambda x.(x ; x)))是个无限循环。所以call-by-value的调用方式会陷入死循环。

如果用call-by-name的方式求值，由于函数(lambda y.lambda x.x)中的函数体其实没涉及到(y)的，所以((lambda x.(x ; x) ; lambda x.(x ; x)))这个参数就函数调用过程后默默地消失了： egin{eqnarray*} &&((lambda y.lambda x.x ; (lambda x.(x ; x) ; lambda x.(x ; x))) ; (+ ; 12 ; 21)) \ & ightarrow& (lambda x.x ; (+ ; 12 ; 21)) \ & ightarrow& (+ ; 12 ; 21) \ & ightarrow& 33 end{eqnarray*}

Call-by-name的代码实现只需在原来的基础上改一行：