简单易懂的程序语言入门小册子（3）：基于文本替换的解释器，let表达式，布尔类型，if表达式...

let表达式

let表达式用来声明一个变量。 比如我们正在写一个模拟掷骰子游戏的程序。 一个骰子有6个面。 所以这个程序多次用到了6这个数字。 有一天&＃xff0c;我们忽然改变主意&＃xff0c;要玩12个面的骰子。 于是我们不得不仔细查找源代码&＃xff0c;把里面的6改成12。 对于一个较大的程序&＃xff0c;这是灾难的开始。 有时我们会漏掉几个6&＃xff0c;有时我们会把几个指的不是骰子面数的6误改成12。 这种灾难被称作“魔术数字”。 避免魔术数字的方法一般是声明一个变量——比如说变量\(a\)——让这个变量等于6&＃xff08;\(a&＃61;6\)&＃xff09;。 这个例子的let表达式包含三个元素&＃xff1a;变量\(a\)&＃xff0c;要赋予变量的值6&＃xff0c;以及程序主体\(M\)。 我将这条let表达式写成下面的样子&＃xff1a; \[ ({let} \; a \; 6 \; M) \] 一般地&＃xff0c;定义let表达式为如下形式&＃xff1a; \[ ({let} \; X \; N \; M) \] 这是一个单变量的let表达式。

还是掷骰子的例子。 避免魔术数字还有一种方法是定义一个函数&＃xff0c;函数的参数是骰子的面数\(a\)&＃xff0c;函数体是程序主体\(M\)&＃xff1a; \[ \lambda a.M \] 然后以参数6调用这个函数&＃xff1a; \[ (\lambda a.M \; 6) \] 将上面这个表达式与let表达式对比&＃xff0c;可以看到let表达式不过是函数调用的语法糖&＃xff1a; \[ ({let} \; X \; N \; M) &＃61; (\lambda X.M \; N) \] 基于尽量简单的原则&＃xff0c;我不打算将let表达式加入到解释器的语法中&＃xff0c; 而是让let表达式以宏的形式加入语言。 所以另外写了一个函数translate来展开let表达式。

解释器先调用translate做转换&＃xff0c;再调用value-of求值。

布尔类型

加入布尔类型可以像加入整数一样&＃xff0c;定义布尔类型为基本类型&＃xff0c;然后定义几个和布尔类型相关的表达式。 不过基于“以玩的心态写代码”的原则&＃xff0c;我打算折腾一下&＃xff0c;用编码的方式引入布尔类型。

可以说&＃xff0c;布尔类型唯一的用途就是用于选择&＃xff08;二选一&＃xff09;。可以将真&＃xff08;true&＃xff09;理解为一个“两个中选择第一个”的函数&＃xff0c;将假&＃xff08;false&＃xff09;理解为一个“两个中选择第二个”的函数。如下定义布尔类型&＃xff1a; \begin{eqnarray*}   {true} &&＃61;& \lambda x.\lambda y.x \\   {false} &&＃61;& \lambda x.\lambda y.y \end{eqnarray*}

为了将整数类型和布尔类型联系起来&＃xff0c;需要添加一个判断一个整数是否为零的基本函数iszero。 \begin{eqnarray*}   M, N, L &&＃61;& ... \\           &|& ({iszero} \; b) \end{eqnarray*} iszero的求值过程&＃xff1a; \begin{eqnarray*}   eval(({iszero} \; 0)) &&＃61;& {true} \\   eval(({iszero} \; b)) &&＃61;& {false}, 其中b \neq 0 \end{eqnarray*} 代码&＃xff1a;

if表达式

if表达式定义为&＃xff1a; \[ ({if} \; L \; M \; N) &＃61; ((L \; M) \; N) \]

上面if表达式的定义在call-by-value的调用方式会有问题。 在call-by-value的调用方式下&＃xff0c;不论\(L\)的值是真是假&＃xff0c;\(M\)和\(N\)都会被求值。 这不仅造成了多余的计算&＃xff0c;在一些情况下会很悲剧&＃xff1a; 如果\(M\)或者\(N\)有副作用&＃xff08;后面会加入一些有副作用的表达式&＃xff09;&＃xff0c;很可能会导致结果不正确&＃xff1b; 如果这个if表达式在一个递归函数的函数体里&＃xff0c;那么调用这个递归函数会无限循环。

为了避免\(M\)和\(N\)被提前求值&＃xff0c;这里用一个技巧来延后\(M\)和\(N\)的求值。 将if表达式的定义改为&＃xff1a; \begin{eqnarray*} ({if} \; L \; M \; N) &&＃61;& (((L \; \lambda X.M) \; \lambda X.N) \; 0) \\ &&其中X \notin FV(M) \cup FV(N) \end{eqnarray*} 将\(M\)和\(N\)封装成\(\lambda X.M\)和\(\lambda X.N\)&＃xff0c;避免了\(M\)和\(N\)被求值。 等到\(L\)的真假值被求出并选择了\(\lambda X.M\)或\(\lambda X.N\)中的一个后&＃xff0c; 将其应用到参数0上&＃xff08;0是随便选的&＃xff0c;反正\(X\)这个参数在函数体\(M\)和\(N\)里也用不着&＃xff09;。 这个技巧在很多call-by-value的语言中用来模拟惰性求值。

和let表达式一样&＃xff0c;if表达式以宏的形式加入到语言中。 Call-by-name的解释器&＃xff1a;

Call-by-value的解释器&＃xff1a;