6 从替换模型到环境模型
尽管我们已经实现了函数，你可能对其不太满意。处理标识符时，直观上应该是“找到它绑定的值”。但是我们不仅没这样做，还在遇到标识符时直接抛出错误！这么做也没错，但感觉怪怪的。更重要的是，编写解释器是为了让其理解并解释我们的语言，而该解释器现在看来并没有达成我们的意愿。
使用替换模型的另一个问题是，它需要遍历源程序的次数。理想的做法是，只访问程序中被实际求值的部分，并且，仅当必要时才这么做。替换模型必须遍历程序的所有部分——比如说，条件分支中不执行的分支——而且还需要遍历程序两遍，一遍替换，一遍解释。
练习
替换模型会影响程序运行的时间复杂性吗？
替换模型还有个问题，它的结构受限于源代码的存储。当然，我们的解释器需要源代码，对其解释。但是其他实现方式——比如说编译器——并不需要存贮源代码。【注释】采取更一般的策略，不依赖于具体实现方式显然更为合理。
编译器可能也需要存储某些源代码信息，以实现其他功能。比如说，报告运行时错误时，或者进行即时编译（JIT）。
6.1 介绍环境模型
直觉告诉我们，解决第一个问题的方法是，解释器可以在某种形式的字典里面“寻找”标识符；解决第二个问题的方法是，延迟替换。幸运的是，这两点结合起来还能解决第三个问题。字典里面记录的是将要进行的替换，而并不对原始程序进行修改。因为记录下了将要进行的替换，而并非直接替换，我们可以延迟进行替换步骤。记录替换内容的数据结构被称为环境（environment）。使用环境模型避免了源代码级别的重写，并且和底层的计算机表示法很好地对应。环境中的结合关系被称为绑定（binding）。
注意，这里我们要修改的是编程语言的实现策略，而不是修改语言本身。因此用于表示程序的数据结构，还有解释器执行的结果都不应发生改变。所以，我们可以将之前那个解释器当作我们这次要写的解释器的“参考实现”，两者的结果应该一致。实际上，我们应该创建一个测试生成器，让它生成很多测给两个解释器来执行，并确保它们返回的结果都相同。理想情况下，我们应该证明两个解释器行为一致，事实上它是很好的高阶课题。
这里的“一致”到底是什么意思呢？特别地，当程序运行报错时呢？
首先，我们来定义环境的数据结构。环境是将名字与什么的绑定的表？
思考题
这里定义数据结构时，很自然的问题就是，环境中将名字映射成了什么东西。但是我们可以问更好更基本的问题，我们如何得出这个很自然问题的答案？
记住我们这里引入环境是为了推迟替换过程。因此，答案在替换中。我们在上一章最后一节中讨论过，我们希望直接将名字替换为计算结果，即对应于函数的及早求值策略。因此同样的，环境中应该将名字映射为求值结果。
(define-type Binding
[bind (name : symbol) (val : number)])
(define-type-alias Env (listof Binding))
(define mt-env empty)
(define extend-env cons)
6.2 环境模型解释器
现在可以实现解释器了。除最简单的分支情况外，其它代码均需要重新考虑：
<*> ::=
(define (interp [expr : ExprC] [env : Env] [fds : (listof FunDefC)]) : number
(type-case ExprC expr
[numC (n) n]
<idC-case> ;标识符子句
<appC-case> ;调用子句
<plusC/multC-case>)) ;加法乘法子句
算术操作是最好写的。回忆一下，递归中未涉及到新的替换，因此无需特别处理，环境不会发生改变：
<plusC/multC-case> ::= ;加法乘法子句
[plusC (l r) (+ (interp l env fds) (interp r env fds))]
[multC (l r) (* (interp l env fds) (interp r env fds))]
接下来我们处理标识符。显然，现在遇到标识符不应该直接报错了。我们应该在当前环境中查找对应的值：
<idC-case> ::= ;标识符子句
[idC (n) (lookup n env)]
思考题
实现lookup函数。
最后，处理函数调用。注意到在替换模型的解释器中，唯一创建新替换的部分就是函数调用。因此这个地方会是需要创建绑定的地方。第一步，跟之前一样，提取函数定义：
<appC-case> ::= ;调用子句
[appC (f a) (let ([fd (get-fundef f fds)])
<appC-interp>)] ;调用的解释
之前，我们是先进行替换，然后解释。现在剔除掉替换这个步骤，我们首先记录下要替换的东西，然后直接进入解释步骤：
<appC-interp> ::= ;调用的解释
(interp (fdC-body fd)
<appC-interp-bind-in-env> ;调用的解释，环境绑定
fds)
也就是说，函数定义部分保持不变；我们照旧解释函数的主体部分；不过解释过程要被放在新的环境中，该环境包含了函数形式参数的绑定。接下来定义绑定过程：
<appC-interp-bind-in-env-take-1> ::= ;调用的解释，环境绑定，第一次尝试
(extend-env (bind (fdC-arg fd)
(interp a env fds))
env)
要绑定的是形参（之前被替换的也是形参）。绑定的值是函数参数解释求值的结果（因为我们采取及早求值语义）。这就需要扩充我们的环境。类型检查确保我们得到的代码是正确的。
最后加上lookup函数的实现，一切就都完成了：
(define (lookup [for : symbol] [env : Env]) : number
(cond
[(empty? env) (error 'lookup "name not found")] ;找不到名称
[else (cond
[(symbol=? for (bind-name (first env)))
(bind-val (first env))]
[else (lookup for (rest env))])]))
请注意，查找自由标识符时依旧会报错，但是这一步从解释器中被剥离出来——解释器并无法判断某个标识符是否被绑定——由lookup函数根据当前环境来决定。
完成解释器后，当然需要测试以确保其正确性。下面这几个测试都通过了：
(test (interp (plusC (numC 10) (appC 'const5 (numC 10)))
mt-env
(list (fdC 'const5 '_ (numC 5))))
15)
(test (interp (plusC (numC 10) (appC 'double (plusC (numC 1) (numC 2))))
mt-env
(list (fdC 'double 'x (plusC (idC 'x) (idC 'x)))))
16)
(test (interp (plusC (numC 10) (appC 'quadruple (plusC (numC 1) (numC 2))))
mt-env
(list (fdC 'quadruple 'x (appC 'double (appC 'double (idC 'x))))
(fdC 'double 'x (plusC (idC 'x) (idC 'x)))))
22)
所以，我们是已经完成任务了，对吧？
思考题
找找看bug在哪。
6.3 正确的进行延迟求值
考虑下面这个测试：
(interp (appC 'f1 (numC 3))
mt-env
(list (fdC 'f1 'x (appC 'f2 (numC 4)))
(fdC 'f2 'y (plusC (idC 'x) (idC 'y)))))
在我们的解释器中，它的结果为7。这正确吗？
将这个测试转换成Racket代码，两个定义加一个表达式：
(define (f1 x) (f2 4))
(define (f2 y) (+ x y))
(f1 3)
考虑其求值过程。(f1 3)将函数f1的函数体中x替换为3，于是下一步处理(f2 4)。但是注意到在函数f2中， 标识符x未绑定！当然Racket报错了。
事实上，我们的替换模型解释器也会报错！
为什么我们的替换模型会报错呢？这是因为，我们仅会在f1的函数体内将标识符x替换为数3的表示。【注释】（这是显而易见的事：x是f1的参数；如果其它函数的参数名碰巧也叫x，那也是个不同的x）。当我们计算f2时，其中x没有被替换过，因此报错了。
“数3的表示”听上去是不是很罗嗦？以后这类情况我就直接说“3”了，不过请你理解这其中的区别。
那么我们环境模型的问题到底出在哪呢？请仔细观察，这一点很微妙。只有函数调用过程会改变环境，我们重点观察这一步。将形参替换成实参是通过扩展当前环境实现的。在我们的例子中，在处理f2函数体时，我们不仅要求它对f2的参数进行替换，还要它对当前所有环境中的参数（也就是调用f2的f1的参数）都进行替换。如果还有上一层，它的参数也会被替换。换一种说法，添加到环境中的绑定只增不减。
由于前面说过，环境模型是替换模型的替代实现策略——我们的语言意义不应该发生改变——唯一合理的做法是修改解释器。具体来说，我们不应该让解释过程携带所有历史绑定，而应为每个函数创建干净的环境，类似替换模型的做法。很容易实现：
<appC-interp-bind-in-env> ::= ;调用的解释，环境绑定
(extend-env (bind (fdC-arg fd)
(interp a env fds))
mt-env)
到此，我们重现了替换模型解释器的行为。
对于需要报错的情况，测试该怎么写呢？请查阅test/exn的文档。
6.4 作用域
上面那个错误的环境模型解释器，所实现的语义被称为动态作用域（dynamic scope）。它意味着随着程序的执行，环境中的绑定不断增加。于是，某个标识符是否被绑定取决于程序的执行历史。这应该被视作程序语言设计的缺陷。它增加了所有相关工具的复杂度，如编译器、IDE，也使得其代码难于阅读维护。
与之对应的，替换模型，以及上面正确实现的环境模型，给我们带来的是词法作用域（lexical scope） 或称静态作用域（static scope）。这里“词法（lexical）”指的是 “通过源码即可确定”；“静态（static）”指的是“不需运行程序即可确定”，在这里，这两者指代的意义相同。当遇到标识符时，我们希望知道两件事：
- 它是否被绑定了？
- 如果被绑定，在何处被绑定的？
这里“何处被绑定”指的是当程序中某个名字在多处被绑定，当前这个名字对应于哪个绑定。换一种说法，那个绑定负责当前标识符的绑定？一般来说，在动态作用域的语言中，这种问题没有静态的答案；于是你的IDE没法提示你某个变量是在哪个地方被定义的（DrRacket可以通过画箭头的方式提示此类信息）。【注释】因此，随着命名空间变得更为复杂（比如引入对象、线程等概念），我们仍需努力维护静态作用域原则。
思考这个问题的另一种方法是，在动态作用域的语言中，所有变量的绑定位置都没法静态确定，它总是取决于动态的环境。换一种说法，这种信息毫无价值。
6.4.1 动态作用域到底有多糟糕
可能看到上述的例子，你会觉得这是小题大作。但是，请考虑这两件事：
- 要真正理解动态作用域的程序，你必需阅读整个程序。不管你怎么将程序进行解耦成易于理解的小的部分，如果程序中有个自由变量呢。
- 要理解绑定关系，其复杂度不仅涉及到程序的体积，还牵扯到控制流的复杂度。考虑使用了很多回调的交互式程序，你需要追踪整个调用过程来确定某个标识符的值的来源。
还不够有说服力？让我们把示例程序中的表达式替换为：
(if (moon-visible?)
(f1 10)
(f2 10))
假设moon-visible?函数在新月的夜晚其值为假，其他情况下为真。于是我们的程序应当在新月夜晚报错，未绑定变量，而在其他情况下返回某个值。
练习
在多云的夜晚呢？
6.4.2 全局作用域
当我们深入思考很多语言中全局的定义时，事情会变得更加复杂。例如，一些版本的Scheme（典型的词法作用域语言）允许你写出这样的程序：
(define y 1)
(define (f x) (+ x y))
看上去好像函数f中的y来源很清晰，不过：
(define y 1)
(define (f x) (+ x y))
(define y 2)
这是合法的，且计算(f 10)时它返回12。你可能会想，那么取最后一个定义就对了！。但是：
(define y 1)
(define f (let ((z y)) (lambda (x) (+ x y z))))
(define y 2)
这时候，z绑定的是第一个y的值，lambda函数内部的y被绑定为第二个y的值。【注释】事实上可以通过词法作用域解释这种行为，但是它让情况变得异常复杂，可能避免这样的重定义是一种比较好的选择。Racket正是这样做的（在Racket中这么操作会导致报错），它能提供用户全局定义，同时又避免这类麻烦事。
很多“脚本”语言都有类似的问题。所以网上你会看到很多人搞不清楚某种语言到底是静态还是动态作用域的。其实很多情况下人们只是在比较函数内的行为（通常是静态作用域）还是全局的行为（通常是动态作用域）。请注意这一点。
6.5 暴露环境
如果是实现供别人使用的解释器，明智的选择是将环境隐藏起来，给用户提供的接口只接收一个表达式，外加一系列函数定义，然后我们在程序内部从空白的环境开始调用interp。这样即不用将实现细节暴露给用户，也不会由于用户提供错误的环境导致问题。然而，有些情况下，暴露环境参数也是有用的。比如如果语言希望默认绑定一系列值:比如说，将pi绑定到3.2（Indiana）。