To design a register machine, we must design its
data paths
(registers and operations) and the
controller that sequences these
operations. To illustrate the design of a simple register machine, let us
examine Euclid’s Algorithm, which is used to compute the greatest common
divisor (GCD) of two integers. As we saw in 1.2.5,
Euclid’s Algorithm can be carried out by an iterative process, as specified by
the following procedure:
要设计一台寄存器机器，我们必须设计其数据通路（寄存器和操作）以及对这些操作进行排序的控制器。为了说明简单寄存器机器的设计过程，我们来考察欧几里得算法——它用于计算两个整数的最大公约数（GCD）。正如我们在 1.2.5 中所见，欧几里得算法可以通过迭代型计算过程来执行，如下列过程所示：
A machine to carry out this algorithm must keep track of two numbers, a and
b, so let us assume that these numbers are stored in two registers with
those names. The basic operations required are testing whether the contents of
register b is zero and computing the remainder of the contents of
register a divided by the contents of register b. The remainder
operation is a complex process, but assume for the moment that we have a
primitive device that computes remainders. On each cycle of the GCD
algorithm, the contents of register a must be replaced by the contents
of register b, and the contents of b must be replaced by the
remainder of the old contents of a divided by the old contents of
b. It would be convenient if these replacements could be done
simultaneously, but in our model of register machines we will assume that only
one register can be assigned a new value at each step. To accomplish the
replacements, our machine will use a third “temporary” register, which we
call t. (First the remainder will be placed in t, then the
contents of b will be placed in a, and finally the remainder
stored in t will be placed in b.)
执行此算法的机器必须跟踪两个数 a 和 b，因此我们假设这两个数分别存储在以其命名的两个寄存器中。所需的基本操作是：测试寄存器 b 的内容是否为零，以及计算寄存器 a 的内容除以寄存器 b 的内容所得的余数。求余操作是一个复杂的计算过程，但暂时假设我们有一个能计算余数的基本装置。在 GCD 算法的每一轮循环中，寄存器 a 的内容必须替换为寄存器 b 的内容，而寄存器 b 的内容必须替换为旧 a 除以旧 b 所得的余数。若能同时完成这两个替换会很方便，但在我们的寄存器机器模型中，假设每步只能对一个寄存器赋新值。为了完成这些替换，我们的机器将使用第三个"临时"寄存器，称之为 t。（首先将余数存入 t，然后将 b 的内容存入 a，最后将存于 t 中的余数存入 b。）
We can illustrate the registers and operations required for this machine by
using the data-path diagram shown in Figure 5.1. In this diagram, the
registers (a, b, and t) are represented by rectangles.
Each way to assign a value to a register is indicated by an arrow with an
X behind the head, pointing from the source of data to the register. We
can think of the X as a button that, when pushed, allows the value at
the source to “flow” into the designated register. The label next to each
button is the name we will use to refer to the button. The names are
arbitrary, and can be chosen to have mnemonic value (for example, a
denotes pushing the button that assigns the contents of register b to
register a). The source of data for a register can be another register
(as in the a assignment), an operation result (as in the t
assignment), or a constant (a built-in value that cannot be changed,
represented in a data-path diagram by a triangle containing the constant).
Figure 5.1: Data paths for a GCD machine.
我们可以用图 5.1 所示的数据通路图来说明此机器所需的寄存器和操作。在该图中，寄存器（a、b 和 t）用矩形表示。向寄存器赋值的每种方式都用一个箭头表示，箭头头部后方有一个 X，从数据来源指向寄存器。可以将 X 理解为一个按钮，按下时允许来源处的值"流入"指定寄存器。每个按钮旁边的标签是我们用来指称该按钮的名字。这些名字是任意的，可以选取具有助记价值的名字（例如，a 表示按下将寄存器 b 的内容赋给寄存器 a 的按钮）。寄存器的数据来源可以是另一个寄存器（如 a 赋值中），也可以是操作结果（如 t 赋值中），或者是常量（不可更改的内置值，在数据通路图中用包含该常量的三角形表示）。图 5.1：GCD 机器的数据通路。
An operation that computes a value from constants and the contents of registers
is represented in a data-path diagram by a trapezoid containing a name for the
operation. For example, the box marked rem in Figure 5.1
represents an operation that computes the remainder of the contents of the
registers a and b to which it is attached. Arrows (without
buttons) point from the input registers and constants to the box, and arrows
connect the operation’s output value to registers. A test is represented by a
circle containing a name for the test. For example, our GCD machine
has an operation that tests whether the contents of register b is zero.
A test also has arrows from its input registers and constants, but it has no
output arrows; its value is used by the controller rather than by the data
paths. Overall, the data-path diagram shows the registers and operations that
are required for the machine and how they must be connected. If we view the
arrows as wires and the X buttons as switches, the data-path diagram is
very like the wiring diagram for a machine that could be constructed from
electrical components.
在数据通路图中，从常量和寄存器内容计算出某个值的操作用一个含有操作名称的梯形表示。例如，图 5.1 中标记为 rem 的方框表示一个操作，它计算与之相连的寄存器 a 和 b 的内容之余数。（不带按钮的）箭头从输入寄存器和常量指向方框，另有箭头将操作的输出值连接到寄存器。测试用一个含有测试名称的圆圈表示。例如，我们的 GCD 机器有一个操作，用于测试寄存器 b 的内容是否为零。测试同样有从其输入寄存器和常量出发的箭头，但没有输出箭头；其值由控制器使用，而非由数据通路使用。总体而言，数据通路图展示了机器所需的寄存器和操作，以及它们必须如何相互连接。若将箭头视为导线，将 X 按钮视为开关，则数据通路图与可由电子元器件构建的机器的接线图非常相似。
In order for the data paths to actually compute GCDs, the buttons
must be pushed in the correct sequence. We will describe this sequence in
terms of a controller diagram, as illustrated in Figure 5.2. The
elements of the controller diagram indicate how the data-path components should
be operated. The rectangular boxes in the controller diagram identify
data-path buttons to be pushed, and the arrows describe the sequencing from one
step to the next. The diamond in the diagram represents a decision. One of
the two sequencing arrows will be followed, depending on the value of the
data-path test identified in the diamond. We can interpret the controller in
terms of a physical analogy: Think of the diagram as a maze in which a marble
is rolling. When the marble rolls into a box, it pushes the data-path button
that is named by the box. When the marble rolls into a decision node (such as
the test for b = 0), it leaves the node on the path determined by the
result of the indicated test. Taken together, the data paths and the
controller completely describe a machine for computing GCDs. We
start the controller (the rolling marble) at the place marked start,
after placing numbers in registers a and b. When the controller
reaches done, we will find the value of the GCD in register
a.
Figure 5.2: Controller for a GCD machine.
为了让数据通路实际计算 GCD，必须按正确的顺序按下各按钮。我们将用控制器图来描述这一顺序，如图 5.2 所示。控制器图中的各元素说明数据通路组件应如何操作。控制器图中的矩形框标识需要按下的数据通路按钮，箭头描述从一步到下一步的顺序。图中的菱形代表一个决策点：根据菱形中标识的数据通路测试结果，将沿两条顺序箭头之一继续执行。我们可以用一个物理类比来理解控制器：将该图想象成一个弹珠在其中滚动的迷宫。弹珠滚入方框时，按下以该方框命名的数据通路按钮；弹珠滚入决策节点（如 b = 0 的测试）时，根据指定测试的结果沿相应路径离开该节点。数据通路和控制器合在一起，完整描述了一台计算 GCD 的机器。将数字放入寄存器 a 和 b 后，从标记 start 处启动控制器（滚动的弹珠）；当控制器到达 done 时，寄存器 a 中即存有 GCD 的值。图 5.2：GCD 机器的控制器。
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))