Exercise 5.38 · 习题

Exercise 5.38: Our compiler is clever about
avoiding unnecessary stack operations, but it is not clever at all when it
comes to compiling calls to the primitive procedures of the language in terms
of the primitive operations supplied by the machine. For example, consider how
much code is compiled to compute (+ a 1): The code sets up an argument
list in argl, puts the primitive addition procedure (which it finds by
looking up the symbol + in the environment) into proc, and tests
whether the procedure is primitive or compound. The compiler always generates
code to perform the test, as well as code for primitive and compound branches
(only one of which will be executed). We have not shown the part of the
controller that implements primitives, but we presume that these instructions
make use of primitive arithmetic operations in the machine’s data paths.
Consider how much less code would be generated if the compiler could

open-code primitives—that is, if it could generate code to directly
use these primitive machine operations. The expression (+ a 1) might be
compiled into something as simple as

(assign val (op lookup-variable-value)
(const a)
(reg env))
(assign val (op +)
(reg val)
(const 1))

In this exercise we will extend our compiler to support open coding of selected
primitives. Special-purpose code will be generated for calls to these
primitive procedures instead of the general procedure-application code. In
order to support this, we will augment our machine with special argument
registers arg1 and arg2. The primitive arithmetic operations of
the machine will take their inputs from arg1 and arg2. The
results may be put into val, arg1, or arg2.

The compiler must be able to recognize the application of an open-coded
primitive in the source program. We will augment the dispatch in the
compile procedure to recognize the names of these primitives in addition
to the reserved words (the special forms) it currently
recognizes. For each special
form our compiler has a code generator. In this exercise we will construct a
family of code generators for the open-coded primitives.

The open-coded primitives, unlike the special forms, all need their operands
evaluated. Write a code generator spread-arguments for use by all the
open-coding code generators. Spread-arguments should take an operand
list and compile the given operands targeted to successive argument registers.
Note that an operand may contain a call to an open-coded primitive, so argument
registers will have to be preserved during operand evaluation.

For each of the primitive procedures =, *, -, and
+, write a code generator that takes a combination with that operator,
together with a target and a linkage descriptor, and produces code to spread
the arguments into the registers and then perform the operation targeted to the
given target with the given linkage. You need only handle expressions with two
operands. Make compile dispatch to these code generators.

Try your new compiler on the factorial example. Compare the resulting
code with the result produced without open coding.

Extend your code generators for + and * so that they can handle

expressions with arbitrary numbers of operands. An expression with more than

two operands will have to be compiled into a sequence of operations, each with

only two inputs.

练习 5.38：我们的编译器在避免多余栈操作方面相当聪明，但在将语言基本过程的调用编译为机器所提供的基本操作方面却毫无技巧可言。例如，考虑编译 (+ a 1) 时会生成多少代码：代码要在 argl 中构造实参表，把基本加法过程（通过在环境中查找符号 + 得到）放入 proc，并测试该过程是基本过程还是复合过程。编译器始终生成执行测试的代码，以及基本分支和复合分支各自的代码（两者只有一个会被执行）。我们没有展示控制器中实现基本过程的部分，但可以假定这些指令会利用机器数据通路中的基本算术操作。试想，如果编译器能够

对基本过程进行开放式编码 (open-code)——即直接生成使用这些基本机器操作的代码——将会少生成多少代码。表达式 (+ a 1) 可能被编译成如下简单形式：

(assign val (op lookup-variable-value)
(const a)
(reg env))
(assign val (op +)
(reg val)
(const 1))

在本练习中，我们将扩展编译器以支持对选定基本过程的开放式编码。对这些基本过程的调用将生成专用代码，而非通用的过程应用代码。为此，我们将为机器增加专用实参寄存器 arg1 和 arg2。机器的基本算术操作从 arg1 和 arg2 读取输入，结果可写入 val、arg1 或 arg2。

编译器必须能够识别源程序中对开放式编码基本过程的应用。我们将扩展 compile 过程中的分派机制，使其除当前已识别的保留字（即各种特殊形式）外，还能识别这些基本过程的名称。对于每种特殊形式，编译器都有一个代码生成器。在本练习中，我们将为开放式编码基本过程构造一族代码生成器。

开放式编码基本过程与特殊形式不同，它们的运算对象都需要求值。请编写供所有开放式编码代码生成器使用的代码生成器 spread-arguments。spread-arguments 应接受一个运算对象表，并将各运算对象编译后依次以连续的实参寄存器为目标。注意，运算对象本身可能包含对开放式编码基本过程的调用，因此在对运算对象求值期间可能需要保护实参寄存器。

对基本过程 =、*、- 和 + 各编写一个代码生成器，接受以该运算符为首的组合式、一个目标和一个链接描述符，生成将实参展开到寄存器后执行该操作的代码，结果以给定目标和给定链接输出。只需处理含两个运算对象的表达式。令 compile 将这些代码生成器加入分派。

在阶乘示例上试验新编译器，将所得代码与未开放式编码时的结果加以比较。

将 + 和 * 的代码生成器扩展，使其能处理任意数量运算对象的表达式。超过两个运算对象的表达式须编译为一系列操作，每次只取两个输入。