求值的环境模型

介绍替代替换模型的环境模型：环境、框架、绑定以及各类表达式和过程的求值规则。

上一课我们了解到，一旦使用赋值，就不能再用替换求值模型了。从今往后，我们将使用一种新模型，它叫做环境模型（environment model）。

让我们通过一个例子来看看这个新模型怎么工作。我们先定义一个简单的 square 过程，并用它计算 7 的平方：

> (define (square x) (* x x))
square
> (square 7)
49

这中间发生了什么？替换模型的说法是：

  1. 用实际参数的值替换过程体中对应的形式参数。
  2. 对替换后的表达式求值。

在这个例子里，把 7 替换 (* x x) 中的 x，得到 (* 7 7)。第二步求值这个表达式，得到结果 49。

现在，把替换模型放一边，来看更完整、更全面的环境模型：

  1. 创建一个框架（frame），把形式参数绑定到实际参数的值上。
  2. 用这个框架扩展已有的词法环境。
  3. 在得到的环境中求值过程体。

框架是名字—值关联（即绑定，binding）的集合。在我们的例子中，框架里只有一个绑定，把 x 绑到 7。

先跳过第二步，想想第三步。我们要求值的表达式是 (* x x)，这里我们是在深化对「求值一个表达式」的理解。表达式不再在真空里求值；相反，每次求值都必须相对于某个环境进行。

环境可以描述成名字与值之间一批绑定的集合。求值 (* x x) 时看到符号 x，我们希望能在这一批绑定里查到 x，找到值 7。这种「查符号绑定的值」的事我们以前就做过——处理全局变量时就是这样。新意在于：我们不再只有中央集中的一批绑定，而是可能有局部环境。符号 x 并不总是 7，那只在这一次 square 调用中成立。所以第三步的意思是：像我们一贯理解的那样求值表达式，但查名字要去特定的地方找。

那第二步又是干什么？要点在于：我们不能在一个只有 x 到 7 绑定的环境里求值 (* x x)，因为还要查符号 * 的值（也就是乘法函数）。所以第一步创建新框架后，它本身还不构成一个环境，要用它去扩展一个已经存在的环境。

扩展哪个旧环境？在 square 例子里只有一个候选——全局环境（global environment）。但在更复杂的情况中，可能有多个环境可选。

环境模型的规则

下面我们分情况过一遍环境模型的规则。开始之前，请记住：

  1. 每个表达式要么是原子（atom），要么是列表。
  2. 任何时刻都有一个当前框架，初始时是全局框架。

原子的求值

先看看原子值怎么求值：

  1. 数字、字符串、#t、#f 自求值。
  2. 如果表达式是符号，找第一个可用的绑定。（也就是说：先查当前框架；查不到，就查当前框架「后面」的框架；如此继续，直到全局框架。）

过程调用

过程又怎么处理？求值机制怎样应对调用过程的表达式？

  1. 求值所有子表达式（用同一套规则）。
  2. 把过程（第一个子表达式的值）应用到各个参数（其余子表达式的值）上。
    • 如果过程是复合的（用户定义的）：
      1. 创建一个框架，把过程的形式参数绑定到实际参数的值上。
      2. 用这个新框架扩展过程的定义环境。
      3. 以求值过程体，以新框架作为当前框架。
    • 如果过程是基本的（primitive）：
      1. 用魔法应用它。只有复合过程调用会创建新框架。

一个例子

(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 5) 创建的环境。

特殊形式

  1. lambda 以「双气泡」的形式创建一个过程。左边的圆指向 lambda 表达式的文本；右边的圆指向定义环境（即看到 lambda 时的当前环境）。只有 lambda 会创建过程。
  2. define 向当前框架添加新绑定。
  3. set! 改变第一个可用的绑定。
  4. let 等于一个 lambda 加上一次调用。
  5. (define (...) …) = lambda + define
  6. 其他特殊形式遵循各自的规则（cond、if）。

一个例子

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

在全局环境中定义 make-withdraw 的结果。

求值 (define W1 (make-withdraw 100)) 的结果。

要点回顾

本课我们学习了如何用环境模型求值过程。

接下来

进入下一课，学习如何绘制环境图！