5.5.6 Lexical Addressing

One of the most common optimizations performed by compilers is the optimization

of variable lookup. Our compiler, as we have implemented it so far, generates

code that uses the lookup-variable-value operation of the evaluator

machine. This searches for a variable by comparing it with each variable that

is currently bound, working frame by frame outward through the run-time

environment. This search can be expensive if the frames are deeply nested or

if there are many variables. For example, consider the problem of looking up

the value of x while evaluating the expression (* x y z) in an

application of the procedure that is returned by

编译器所做的最常见优化之一是对变量查找的优化。就目前实现的编译器而言，它生成的代码使用求值器机器中的 `lookup-variable-value` 操作来查找变量：该操作通过将变量与当前已绑定的每个变量逐一比较，逐框架向外遍历运行时环境来完成查找。如果框架嵌套较深或变量数目众多，这种查找可能代价高昂。例如，考虑在对以下过程所返回的过程应用中对表达式 `(* x y z)` 求值时查找 x 的值这一问题：

Since a let expression is just syntactic sugar for a lambda

combination, this expression is equivalent to

由于 let 表达式不过是 lambda 组合式的语法糖，这个表达式等价于

Each time lookup-variable-value searches for x, it must determine

that the symbol x is not eq? to y or z (in the

first frame), nor to a, b, c, d, or e (in

the second frame). We will assume, for the moment, that our programs do not

use define—that variables are bound only with lambda. Because

our language is lexically scoped, the run-time environment for any expression

will have a structure that parallels the lexical structure of the program in

which the expression appears. Thus, the

compiler can know, when it analyzes the above expression, that each time the

procedure is applied the variable x in (* x y z) will be found

two frames out from the current frame and will be the first variable in that

frame.

每次 `lookup-variable-value` 查找 x 时，必须先判断符号 x 是否与 y 或 z `eq?`（在第一个框架中），再判断是否与 a、b、c、d 或 e `eq?`（在第二个框架中）。我们暂时假定程序中不使用 define——变量仅通过 lambda 绑定。由于我们的语言是词法作用域的，任意表达式的运行时环境结构都与该表达式所在程序的词法结构相互对应。因此，编译器在分析上述表达式时就能知道：每次应用该过程时，`(* x y z)` 中的变量 x 将位于当前框架往外两个框架处，且是该框架中的第一个变量。

We can exploit this fact by inventing a new kind of variable-lookup operation,

lexical-address-lookup, that takes as arguments an environment and a

我们可以利用这一事实，引入一种新的变量查找操作 `lexical-address-lookup`，它以一个环境和一个

lexical address that consists of two numbers: a

frame number,

which specifies how many frames to pass over, and a

词法地址 (lexical address) 作为参数，该地址由两个数组成：帧号 (frame number)，指定需要越过多少个框架；以及

displacement number, which specifies how many variables to pass over

in that frame. Lexical-address-lookup will produce the value of the

variable stored at that lexical address relative to the current environment.

If we add the lexical-address-lookup operation to our machine, we can

make the compiler generate code that references variables using this operation,

rather than lookup-variable-value. Similarly, our compiled code can use

a new lexical-address-set! operation instead of

set-variable-value!.

偏移量 (displacement number)，指定在该框架中需要越过多少个变量。`lexical-address-lookup` 将产生相对于当前环境存放在该词法地址处的变量的值。如果我们将 `lexical-address-lookup` 操作加入机器，就可以让编译器生成使用该操作而非 `lookup-variable-value` 来引用变量的代码。类似地，已编译代码可以使用新的 `lexical-address-set!` 操作来替代 `set-variable-value!`。

In order to generate such code, the compiler must be able to determine the

lexical address of a variable it is about to compile a reference to. The

lexical address of a variable in a program depends on where one is in the code.

For example, in the following program, the address of x in expression

⟨e1⟩ is (2, 0)—two frames back and the first variable in the frame. At

that point y is at address (0, 0) and c is at address (1, 2). In

expression ⟨e2⟩, x is at (1, 0), y is at (1, 1), and c

is at (0, 2).

为了生成这样的代码，编译器必须能够确定它即将编译引用的变量的词法地址。程序中某个变量的词法地址取决于在代码中所处的位置。例如，在下面的程序中，表达式 ⟨e1⟩ 中 x 的地址是 (2, 0)——往外两个框架、该框架中的第一个变量。在该位置，y 的地址是 (0, 0)，c 的地址是 (1, 2)。在表达式 ⟨e2⟩ 中，x 在 (1, 0)，y 在 (1, 1)，c 在 (0, 2)。

One way for the compiler to produce code that uses lexical addressing is to

maintain a data structure called a

compile-time environment. This

keeps track of which variables will be at which positions in which frames in

the run-time environment when a particular variable-access operation is

executed. The compile-time environment is a list of frames, each containing a

list of variables. (There will of course be no values bound to the variables,

since values are not computed at compile time.) The compile-time environment

becomes an additional argument to compile and is passed along to each

code generator. The top-level call to compile uses an empty

compile-time environment. When a lambda body is compiled,

compile-lambda-body extends the compile-time environment by a frame

containing the procedure’s parameters, so that the sequence making up the body

is compiled with that extended environment. At each point in the compilation,

compile-variable and compile-assignment use the compile-time

environment in order to generate the appropriate lexical addresses.

编译器生成使用词法寻址的代码的一种方式，是维护一种称为编译时环境 (compile-time environment) 的数据结构。它跟踪在执行某个特定变量访问操作时，各变量将位于运行时环境中哪个框架的哪个位置。编译时环境是一个框架的表，每个框架包含一个变量的表。（当然，其中不会有绑定到变量的值，因为值在编译时尚未计算。）编译时环境作为附加参数传给 compile，并沿途传递给各代码生成器。对 compile 的顶层调用使用空的编译时环境。在编译 lambda 体时，`compile-lambda-body` 用一个包含过程参数的框架来扩展编译时环境，从而使构成过程体的序列以该扩展后的环境进行编译。在编译过程的每个节点，`compile-variable` 和 `compile-assignment` 使用编译时环境来生成适当的词法地址。

Exercise 5.39 through Exercise 5.43 describe how to complete this

sketch of the lexical-addressing strategy in order to incorporate lexical

lookup into the compiler. Exercise 5.44 describes another use for the

compile-time environment.

练习 5.39 到练习 5.43 描述了如何补全这一词法寻址策略的草图，以便将词法查找融入编译器。练习 5.44 描述了编译时环境的另一种用途。