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 section 1.2.5, Euclid's Algorithm can be carried out by an iterative process, as specified by the following procedure: function:
| Original | JavaScript |
| (define (gcd a b) (if (= b 0) a (gcd b (remainder a b)))) | function gcd(a, b) { return b === 0 ? a : gcd(b, a % b); } |
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.)
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 Xa button—drawn as $\otimes$— behind the
head, pointing from the source of data to the register.
We can think of the X as a button that, when pushed,When pushed, the button 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<-b 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<-b assignment), an operation result (as in
the t<-r assignment), or a constant
(a built-in value that cannot be changed, represented in a data-path
diagram by a triangle containing the constant).
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$\otimes$ buttons as switches, the data-path diagram
is very like the wiring diagram for a machine that could be constructed
from electrical components.
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.
| Original | JavaScript |
| (define (factorial n) (define (iter product counter) (if (> counter n) product (iter (* counter product) (+ counter 1)))) (iter 1 1)) | function factorial(n) { function iter(product, counter) { return counter > n ? product : iter(counter * product, counter + 1); } return iter(1, 1); } |
