3.2 The environment Model of Evaluation - CloneableX/SICP-learning GitHub Wiki

在第一章讲解复合程式时，我们使用替换模型解释程式调用后的运作过程，也就是被调用程式会将接收参数值按形参名称将程式体中的同名形参替换。

不过现在程式中已经加入了赋值操作，替换模型便不再适用。特别是在上一节的内容中谈到，当赋值操作被引入后，变量已经不再单纯是一个数值的名称，而是存储变量值的地址。在新的计算模型中，这个场所由 环境（environments） 结构维护。

一个环境由一系列框架构成，每一个框架是一个维系变量名与变量值关联关系的绑定表。这个关系表可能是空的，并且一个框架对于任何变量最多只能维护一个绑定关系。每个框架都指向它的闭包环境，因为框架的目标是作用于全局。变量的值是指在一个环境中第一个存在此变量关系的框架存储的绑定关系的对应变量值。如果所有的框架都不存在相应的变量关系，则称此变量在环境中没有被绑定。

下图展示了一个由三个框架组成的环境，分别标记为 I、II 和 III。在图例中，A、B、C、D 都是指向环境的指针，其中 C 和 D 指向同一环境。变量 z 和 x 绑定在框架 II 中，而 y 和 x 绑定在框架 I 中。在环境 D 中 x 的值是 3，在环境 B 中 x 的值也是 3。它的判断规则是这样，首先需要检验整个框架序列中的首个框架（也就是框架 III），查看其中是否存在 x 的绑定关系，如果没有就继续沿着闭包环境 D 查找框架 I 中是否存在 x 的绑定关系。从另一方面说，环境 A 的 x 值是 7，是由于框架序列中的首个框架（也就是框架 II）包含了 x 与 7 的关联关系。对于出现在环境 A 中框架 II 的 x 与 7 的绑定关系被称为框架 I 中 x 与 3 绑定关系的影子。

环境是计算过程的关键所在，因为它决定了一个表达式发生计算的上下文。虽然可以认为编程语言中的表达式不存在任何意义，但它可以在发生计算的环境中产生意义。即使 (+ 1 1) 这种比较浅显的表达式也可以理解为在加法符号 + 的环境中运行。所以，接下来讨论计算模型时会不断提及某个表达式运行于某个环境中。为了描述解释器的运作，先假设处于一个全局环境中，它只有一个框架（没有闭包环境），框架中只包含符号标识与基础程式的关联关系。例如，+ 可以被认为是在全局环境中与加法程式绑定的标识。

解释器的运算复合表达式的规则表述如下：

• 首先计算复合表达式的子表达式
• 然后将子表达式操作符的值向子表达式操作数的值应用

在环境模型中，程式总是以一些代码和一个环境指针的形式成对出现，而程式只能通过运算 λ 表达式创建。于是程式的代码便来自 λ 表达式的文本，环境来自 λ 表达式运算产生程式的环境。例如，在全局环境的背景下思考下列程式：

(define (square x)
  (* x x))

定义程式的语法只是一种对于底层 λ 表达式实现的语法糖。它实际上是下面的样式：

(define square
  (lambda (x) (* x x)))

这一切都发生在全局环境中，它先运算 (lambda (x) (* x x)) 再将其结果与 square 绑定。

下图展示了 define 表达式的运算结果。程式对象是由拥有名为 x 形参的程式代码，及程式体 (* x x) 组成的序对。程式的环境部分由指向全局环境的指针组成，这个环境也就是 λ 表达式产生此程式的环境。最后将程式对象与 square 标识绑定，并加入全局框架中。概括起来，define 会创建定义并将绑定关系添加至框架中。

通过以上例子，我们初步了解了程式的创建过程，接着需要了解程式的应用过程。环境模型这样解释，当把程式向参数应用时，会创建一个包含参数与参数值绑定关系框架的环境。此框架所属的闭包环境受程式约束，接着在新环境中发生程式体的计算。

按上述规则，下图阐述了在全局环境中计算 (square 5) 时产生的环境结构。在新环境中应用程式结果，也就是图中的 E1 部分。这是一个存储 x 与 5 绑定关系的框架，并且根据它的指针可以看出它的闭包环境是全局环境。全局环境作为此框架闭包环境的原因是由于 square 程式对象指向的环境正是全局环境。在 E1 中，运算程式体 (* x x)，由于在 E1 中 x 的值是 5，所以运算变成 (* 5 5) ，结果为 25。

关于程式应用的环境模型可以总结为下列两条规则：

• 向一组参数应用程式对象就是在构建一个框架，框架中存储了程式形参与应用参数的绑定关系，接着在被创建的新环境中运算程式体，并且新创建的框架作为程式对象环境部分的闭包环境被应用。
• 由 λ 表达式计算产生的程式与指定环境关联。其中程式对象的结果由 λ 表达式文本和指向程式被创建时环境的指针组成。

我们也可以通过 define 在当前环境框架中定义一个标识并给这个标识绑定对应的值。最后，还需要对导致必须引入环境模型的根因 set! 操作进行解析。在某个环境中计算 (set! <variable> <value>) 就是定位此环境中指定变量的绑定关系，然后将它对应的值修改为新的值。也就是说它会查找环境中存在相应绑定关系的第一个框架，然后修改此框架。如果在环境中变量未曾被绑定，set! 将产生错误。

环境模型的运算规则虽然比替换模型更加复杂，但还算简明。并且环境模型通过合理的抽象为我们提供了一个解释器运作方式的描述。在下一章，环境模型会作为实现解释器的蓝图为我们提供帮助。下一节将通过分析一些程序说明环境模型的细节。

在以前的章节我们使用替换模型解析过 (f 5) 表达式，具体定义如下：

(define (square x)
  (* x x))
(define (sum-of-squares x y)
  (+ (square x) (square y)))
(define (f a)
  (sum-of-squares (+ a 1) (* a 2)))

现在要用环境模型对同样的表达式进行分析。下图展示了 f、square 和 sum-of-suqares 定义时在环境中产生的程式对象。

下图展示了计算 (f 5) 所产生的环境结构。在调用 f 时产生了新环境 E1，首个框架是维护形参 a 与 5 绑定关系的框架。在 E1 中，计算 f 的程式体 (sum-of-squares (+ a 1) (* a 2))。

计算复合表达式时会首先计算其中的子表达式。第一个子表达式 sum-of-squares 的值是一个程式对象，我们的关注点要放在程式对象值的查找上。首先会在第一个框架 E1 中查找，但其中没有包含 sum-of-squares 的绑定，接着进入闭包环境，也就是全局环境中查找。另外两个子表达式分别是基础程式 + 和 * 的计算，(+ a 1) 和 (* a 2) 的计算结果分别是 6 和 10。

此时将参数 6 和 10 应用于程式对象 sum-of-squares，于是产生环境 E2，并在其中维护形参 x 和 y 与参数值的关系。在 E2 中将运算 (+ (square x) (square y))，首先要计算 (square x)，其中 square 存在于全局环境中，并且 x 为 6。同样的原理，这将产生新环境 E3，在此环境中 x 与 6 绑定，并在此基础上运算 square 的程式体 (* x x)。要顺利运算 sum-of-squares 就必须先计算子表达式 (square y)，其中 y 的值是 10。在调用 square 过程中将产生另一个新环境 E4，此环境中 square 的形参 x 与 10 绑定，接着在 E4 中计算 (* x x)。

上述使用环境模型解析运算过程的重点在于，每次调用 square 时都会产生新的环境，并在新环境中为形参 x 绑定相应的参数值。从这里可以看出，不同的框架隔离同名的不同局部变量方式。并且每一个由于 square 调用而被创建的框架都指向全局环境，也就是 square 程式对象所指向的环境。

在子表达式运算完成后将计算结果返回，它是由 sum-of-squares 将两次 square 调用结果相加，最后由 f 返回的计算数值。本节我们关注的主要是环境结构，暂时没有仔细观察程式调用的返回值过程，但它也是计算过程的重要组成部分，我们会在第 5 章详细讨论。

接下来我们要实现最初的期望，使用环境模型解析程式和赋值表示携带本地状态的对象的过程。还是以取款业务为例。

(define (make-withdraw balance)
  (lambda (amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds")))

然后定义 W1 并解析 (W1 50)。

(define W1 (make-withdraw 100))

下图展示了在全局环境中定义 make-withdraw 程式的结果，产生的结果为一个含有指向全局环境指针的程式对象。除了 λ 表达式的程式体之外，这与之前的示例没有任何区别。

不过当我们将 make-withdraw 应用于参数（也就是表达式 (define W1 (make-withdraw 100))) 时出现了有趣的现象。第一步是创建一个环境 E1，在 E1 中将形参 balance 与参数值 100 绑定。在 E1 中将计算 make-withdraw 的程式体，也就是 λ 表达式。于是 λ 表达式又构建了一个程式对象，它的代码就是 lambda 部分，它所处环境为 E1，也就是产生程式的 lambda 所处的环境。这就是调用 make-withdraw 返回的程式对象结果，并在全局环境中通过 define 将其与 W1 绑定。下图展示了计算结果的环境结构。

接下来将分析将 W1 应用于参数时的运算过程。第一步创建了一个框架，用于维护 W1 的形参 amount 与参数 50 的绑定关系。此时的重点在于此框架的闭包环境并不是全局环境而是环境 E1，因为 E1 是 W1 的程式对象指向的环境。在新环境中，运算下列程式体：

(if (>= balance amount)
    (begin (set! balance (- balance amount))
           balance)
    "Insufficient funds")

在下图中展示了运算结果的环境结构。整个表达式将应用于 amount 和 balance 的值，amount 的绑定关系维护于环境的第一个框架中，balance 的绑定关系存在当前环境的闭包环境 E1 中。

当 set! 被执行时，被绑定在 E1 中的 balance 值将发生变化。当 W1 的调用结束时，balance 的结果是 50，并且 balance 所处的框架依然是 W1 的程式对象指向的框架。amount 绑定的框架将不再作用（当运行完改变 balance 的代码后），因为产生此框架的程式调用完成后框架也将终止，并且环境中没有任何一个指针指向它。在下一次 W1 被调用时，将创建一个闭包环境是 E1 的新框架，并在其中维护新的 amount 绑定关系。在这个示例中，E1 就是为程式对象 W1 维护局部状态变量的场所。下图展示了调用 W1 后的情形。

如果再次调用 make-withdraw 创建另一个对象时过程又是如何呢？

(define W2 (make-withdraw 100))

此时将产生如下图的环境结构，其中 W2 是一个程式对象，由一些代码和指向某个环境的指针构成。W2 的环境 E2 在调用 make-withdraw 时被创建，它包含维护 balance 绑定关系的框架。另一方面，W1 和 W2 中的代码相同，都是由 make-withdraw 程式体的 λ 表达式产生。从这里我们能够知道为何 W1 和 W2 的对象是隔离的，因为 W1 的状态变量 balance 存储于 E1 中，而 W2 的状态变量 balance 存储于 E2 中。所以当修改其中一个对象的本地状态时并不会影响另一个对象的本地状态。

之前的章节介绍过内部程式的概念，就像下列程式中的代码块结构。

(define (sqrt x)
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess)
    (if (good-enough? guess)
        guess
        (squrt-iter (improve guess))))
  (sqrt-iter 1.0))

接下来我们将用环境模型分析内部程式的运算过程。下图展示了 (sqrt 2) 第一次运算过程中，当 guess 等于 1 时的情况。

观察上图中的环境结构。sqrt 这个符号在全局环境中绑定了一个程式对象。当 sqrt 被调用时产生了新环境 E1，它归属于全局环境，并在环境 E1 中维护着 x 与 2 的绑定关系，然后 sqrt 程式体将在 E1 中发生运算，在 sqrt 中定义的第一个程式如下：

(define (good-enough? guess)
  (< (abs (- (square guess) x)) 0.001))

也就是说 good-enough? 定义的程式的绑定关系维护在 E1 中。以此类推，improve 和 sqrt-iter 定义的程式绑定关系也在 E1 中。

在内部程式定义完成后，(sqrt-iter 1.0) 将在环境 E1 中进行运算。所以需要把参数 1 应用于绑定在 E1 中的 sqrt-iter 的程式对象，于是创建环境 E2，其中维护了 sqrt-iter 形参 guess 与参数值 1 的绑定关系。接着 sqrt-iter 以 E2 中的 guess 为参数调用 good-enough?，然后创建了环境 E3，其中维护了 good-enough? 的形参 guess 与参数值 1 的绑定关系。尽管此处 sqrt-iter 和 good-enough? 的参数名都为 guess，但它们却是不同框架中的局部变量。其中 E2 和 E3 的闭包环境都是 E1，这是因为 sqrt-iter 和 good-enough? 程式对象指向的环境都是 E1。造成的结果是，在 good-enough? 程式体中出现的符号 x 就是绑定在 E1 中的 x，也就是最初应用 sqrt 程式时传入的参数 x。

因此环境模型也就解释了内部程式定义作为程序模块化技术的两个关键属性：

• 内部程式的名称并不会干扰闭包程式外部的名字，因为内部程式名称是绑定在运行时程式创建的框架中，而不是全局环境中。

• 内部程式可以像使用自由变量一样使用闭包程式的参数，这是由于内部程式的程式体运算发生于闭包程式运算环境的子环境中。