5.1.1 A Language for Describing Register Machines

Data-path and controller diagrams are adequate for representing simple machines

such as GCD, but they are unwieldy for describing large machines such

as a Lisp interpreter. To make it possible to deal with complex machines, we

will create a language that presents, in textual form, all the information

given by the data-path and controller diagrams. We will start with a notation

that directly mirrors the diagrams.

数据通路图和控制器图足以表示简单的机器（如 GCD 机器），但用来描述大型机器（如 Lisp 解释器）时则显得笨拙。为了能够处理复杂的机器，我们将创建一种语言，以文本形式呈现数据通路图和控制器图所给出的全部信息。我们从一种直接映射这两种图的记号开始。

We define the data paths of a machine by describing the registers and the

operations. To describe a register, we give it a name and specify the buttons

that control assignment to it. We give each of these buttons a name and

specify the source of the data that enters the register under the button’s

control. (The source is a register, a constant, or an operation.) To describe

an operation, we give it a name and specify its inputs (registers or

constants).

我们通过描述寄存器和操作来定义机器的数据通路。要描述一个寄存器，需给它命名并指定控制其赋值的按钮。对每个按钮给定名称，并指定在该按钮控制下进入寄存器的数据来源（来源可以是寄存器、常量或某个操作的结果）。要描述一个操作，需给它命名并指定其输入（寄存器或常量）。

We define the controller of a machine as a sequence of

instructions

together with

labels that identify

entry points in the

sequence. An instruction is one of the following:

我们将机器的控制器定义为一个指令序列，以及用于标识序列中各入口点的标号。指令是以下几种之一：

The name of a data-path button to push to assign a value to a register. (This

corresponds to a box in the controller diagram.)

数据通路按钮的名称，按下该按钮可将某个值赋给一个寄存器。（对应控制器图中的一个方框。）

A test instruction, that performs a specified test.

一条检测指令 (test instruction)，用于执行指定的检测。

A conditional branch (branch instruction) to a location indicated by a

controller label, based on the result of the previous test. (The test and

branch together correspond to a diamond in the controller diagram.) If the

test is false, the controller should continue with the next instruction in the

sequence. Otherwise, the controller should continue with the instruction after

the label.

一条条件分支指令（branch instruction），根据前一次检测的结果，转向由控制器标号指示的位置。（检测与分支合在一起对应控制器图中的一个菱形。）若检测结果为假，控制器应继续执行序列中的下一条指令；否则，控制器应从该标号之后的指令继续执行。

An unconditional branch (goto instruction) naming a controller label at

which to continue execution.

一条无条件分支指令（goto instruction），指定一个控制器标号，从该处继续执行。

The machine starts at the beginning of the controller instruction sequence and

stops when execution reaches the end of the sequence. Except when a branch

changes the flow of control, instructions are executed in the order in which

they are listed.

机器从控制器指令序列的开头开始执行，当执行到达序列末尾时停止。除非某条分支指令改变了控制流，否则指令按照列出的顺序依次执行。

Figure 5.3 shows the GCD machine described in this way. This

example only hints at the generality of these descriptions, since the

GCD machine is a very simple case: Each register has only one button,

and each button and test is used only once in the controller.

Figure 5.3: ↓ A specification of the GCD

machine.

图 5.3 展示了以这种方式描述的 GCD 机器。这个例子只是初步展示了这些描述的一般性，因为 GCD 机器是非常简单的情形：每个寄存器只有一个按钮，每个按钮和检测在控制器中也只使用一次。图 5.3：↓ GCD 机器的规格描述。

Unfortunately, it is difficult to read such a description. In order to

understand the controller instructions we must constantly refer back to the

definitions of the button names and the operation names, and to understand what

the buttons do we may have to refer to the definitions of the operation names.

We will thus transform our notation to combine the information from the

data-path and controller descriptions so that we see it all together.

遗憾的是，这样的描述很难阅读。为了理解控制器指令，我们必须不断回头查看按钮名称和操作名称的定义；而为了理解按钮的作用，还可能需要参阅操作名称的定义。因此，我们将对记号进行改造，把数据通路描述和控制器描述中的信息合并在一起，使其可以一览无余。

To obtain this form of description, we will replace the arbitrary button and

operation names by the definitions of their behavior. That is, instead of

saying (in the controller) “Push button t” and separately saying

(in the data paths) “Button t assigns the value of the rem

operation to register t” and “The rem operation’s inputs are

the contents of registers a and b,” we will say (in the

controller) “Push the button that assigns to register t the value of

the rem operation on the contents of registers a and b.”

Similarly, instead of saying (in the controller) “Perform the = test”

and separately saying (in the data paths) “The = test operates on the

contents of register b and the constant 0,” we will say “Perform the

= test on the contents of register b and the constant 0.” We

will omit the data-path description, leaving only the controller sequence.

Thus, the GCD machine is described as follows:

为了得到这种形式的描述，我们将用各按钮和操作的行为定义来替换它们的任意名称。也就是说，不再（在控制器中）说"按下按钮 t"，并单独（在数据通路中）说"按钮 t 将 rem 操作的值赋给寄存器 t"以及"rem 操作的输入是寄存器 a 和 b 的内容"，而是（在控制器中）直接说"按下按钮，将寄存器 a 和 b 内容的 rem 操作的值赋给寄存器 t"。类似地，不再（在控制器中）说"执行 = 检测"，并单独（在数据通路中）说"= 检测作用于寄存器 b 的内容和常量 0"，而是说"对寄存器 b 的内容和常量 0 执行 = 检测"。我们将省略数据通路描述，只保留控制器序列。这样，GCD 机器的描述如下：

This form of description is easier to read than the kind illustrated in

Figure 5.3, but it also has disadvantages:

这种描述形式比图 5.3 所示的形式更易阅读，但也存在一些缺点：

It is more verbose for large machines, because complete descriptions of the

data-path elements are repeated whenever the elements are mentioned in the

controller instruction sequence. (This is not a problem in the GCD

example, because each operation and button is used only once.) Moreover,

repeating the data-path descriptions obscures the actual data-path structure of

the machine; it is not obvious for a large machine how many registers,

operations, and buttons there are and how they are interconnected.

对于大型机器而言，这种形式过于冗长，因为每当控制器指令序列中出现某个数据通路元素时，都要重复写出对该元素的完整描述。（在 GCD 的例子中这不成问题，因为每个操作和按钮都只使用了一次。）此外，重复书写数据通路描述掩盖了机器实际的数据通路结构；对于大型机器，寄存器、操作和按钮的数量以及它们之间的互连方式都不易一目了然。

Because the controller instructions in a machine definition look like Lisp

expressions, it is easy to forget that they are not arbitrary Lisp expressions.

They can notate only legal machine operations. For example, operations can

operate directly only on constants and the contents of registers, not on the

results of other operations.

由于机器定义中的控制器指令看起来像 Lisp 表达式，人们很容易忘记它们并不是任意的 Lisp 表达式。它们只能标记合法的机器操作。例如，操作只能直接作用于常量和寄存器的内容，而不能作用于其他操作的结果。

In spite of these disadvantages, we will use this register-machine language

throughout this chapter, because we will be more concerned with understanding

controllers than with understanding the elements and connections in data paths.

We should keep in mind, however, that data-path design is crucial in designing

real machines.

尽管存在这些缺点，我们在本章中仍将使用这种寄存器机器语言，因为我们更关注对控制器的理解，而不是对数据通路中各元素及其连接的理解。不过，我们应当铭记：在设计真实机器时，数据通路的设计至关重要。