4.1.3 Evaluator Data Structures

In addition to defining the external syntax of expressions, the evaluator

implementation must also define the data structures that the evaluator

manipulates internally, as part of the execution of a program, such as the

representation of procedures and environments and the representation of true

and false.

Subheading: Testing of predicates

除了定义表达式的外部语法，求值器的实现还必须定义求值器在程序执行过程中内部操纵的数据结构，例如过程与环境的表示形式，以及真值与假值的表示形式。

Subheading: Testing of predicates

For conditionals, we accept anything to be true that is not the explicit

false object.

对于条件判断，我们将所有不是显式假对象 (false object) 的值都视为真。

Subheading: Representing procedures

To handle primitives, we assume that we have available the following

procedures:

为了处理基本过程，我们假设已有如下过程可供使用：

(apply-primitive-procedure ⟨proc⟩ ⟨args⟩)

applies the given primitive procedure to the argument values in the list

⟨args⟩ and returns the result of the application.

将给定的基本过程作用于表 ⟨args⟩ 中的各个实参值，并返回应用的结果。

(primitive-procedure? ⟨proc⟩)

tests whether ⟨proc⟩ is a primitive procedure.

These mechanisms for handling primitives are further described in

4.1.4.

检验 ⟨proc⟩ 是否为基本过程。这些处理基本过程的机制将在 4.1.4 节中进一步说明。

Compound procedures are constructed from parameters, procedure bodies, and

environments using the constructor make-procedure:

复合过程由参数、过程体和环境共同构成，使用构造函数 make-procedure 来创建：

Subheading: Operations on Environments

The evaluator needs operations for manipulating environments. As explained in

3.2, an environment is a sequence of frames, where each frame is

a table of bindings that associate variables with their corresponding values.

We use the following operations for manipulating environments:

求值器需要对环境进行操作的各种运算。如 3.2 节所述，环境是一个框架的序列，每个框架是一张将变量与对应值相关联的绑定表。我们使用以下运算来操作环境：

(lookup-variable-value ⟨var⟩ ⟨env⟩)

returns the value that is bound to the symbol ⟨var⟩ in the environment

⟨env⟩, or signals an error if the variable is unbound.

返回符号 ⟨var⟩ 在环境 ⟨env⟩ 中所绑定的值；若该变量未被绑定，则报告错误。

(extend-environment ⟨variables⟩ ⟨values⟩ ⟨base-env⟩)

returns a new environment, consisting of a new frame in which the symbols in

the list ⟨variables⟩ are bound to the corresponding elements in the list

⟨values⟩, where the enclosing environment is the environment

⟨base-env⟩.

返回一个新环境，该环境由一个新框架构成——在此框架中，表 ⟨variables⟩ 中的各符号被绑定到表 ⟨values⟩ 中对应的元素——其外围环境为 ⟨base-env⟩。

(define-variable! ⟨var⟩ ⟨value⟩ ⟨env⟩)

adds to the first frame in the environment ⟨env⟩ a new binding that

associates the variable ⟨var⟩ with the value ⟨value⟩.

在环境 ⟨env⟩ 的第一个框架中添加一个新绑定，将变量 ⟨var⟩ 与值 ⟨value⟩ 相关联。

(set-variable-value! ⟨var⟩ ⟨value⟩ ⟨env⟩)

changes the binding of the variable ⟨var⟩ in the environment ⟨env⟩

so that the variable is now bound to the value ⟨value⟩, or signals an

error if the variable is unbound.

修改变量 ⟨var⟩ 在环境 ⟨env⟩ 中的绑定，使该变量现在绑定到值 ⟨value⟩；若该变量未被绑定，则报告错误。

To implement these operations we represent an environment as a list of frames.

The enclosing environment of an environment is the cdr of the list. The

empty environment is simply the empty list.

为了实现这些运算，我们将环境表示为一个框架的表。环境的外围环境就是该表的 cdr，空环境就是空表。

Each frame of an environment is represented as a pair of lists: a list of the

variables bound in that frame and a list of the associated

values.

环境中的每个框架表示为一个由两个表构成的序对：一个是该框架中所有被绑定变量的表，另一个是对应值的表。

To extend an environment by a new frame that associates variables with values,

we make a frame consisting of the list of variables and the list of values, and

we adjoin this to the environment. We signal an error if the number of

variables does not match the number of values.

为了用一个将变量与值相关联的新框架来扩展环境，我们构造一个由变量表和值表组成的框架，并将其附加到环境上。若变量的数目与值的数目不符，则报告错误。

To look up a variable in an environment, we scan the list of variables in the

first frame. If we find the desired variable, we return the corresponding

element in the list of values. If we do not find the variable in the current

frame, we search the enclosing environment, and so on. If we reach the empty

environment, we signal an “unbound variable” error.

在环境中查找某个变量时，我们扫描第一个框架中的变量表。若找到所求变量，就返回值表中对应的元素。若在当前框架中未找到该变量，则搜索外围环境，依此类推。若到达空环境，则报告"变量未绑定 (unbound variable)"错误。

To set a variable to a new value in a specified environment, we scan for the

variable, just as in lookup-variable-value, and change the corresponding

value when we find it.

在指定环境中将某个变量设置为新值时，我们像 lookup-variable-value 那样扫描该变量，找到后修改对应的值。

To define a variable, we search the first frame for a binding for the variable,

and change the binding if it exists (just as in set-variable-value!).

If no such binding exists, we adjoin one to the first frame.

定义一个变量时，我们在第一个框架中查找是否已有该变量的绑定，若存在则修改该绑定（与 set-variable-value! 的做法相同）；若不存在，则在第一个框架中添加一个新绑定。

The method described here is only one of many plausible ways to represent

environments. Since we used data abstraction to isolate the rest of the

evaluator from the detailed choice of representation, we could change the

environment representation if we wanted to. (See Exercise 4.11.) In a

production-quality Lisp system, the speed of the evaluator’s environment

operations—especially that of variable lookup—has a major impact on the

performance of the system. The representation described here, although

conceptually simple, is not efficient and would not ordinarily be used in a

production system.

这里描述的方法只是表示环境的众多合理方式之一。由于我们使用数据抽象将求值器的其余部分与表示方式的具体选择相隔离，因此可以根据需要更改环境的表示形式（见练习 4.11）。在生产质量的 Lisp 系统中，求值器中环境操作的速度——尤其是变量查找的速度——对系统性能有着重大影响。这里描述的表示方式虽然在概念上简单，但效率不高，通常不会用于生产系统。