We will often define a machine to include primitive

operations that are
actually very complex. For example, in sections 5.4 and
**Cound not find label for sec:compilation** we will treat JavaScript's environment
manipulations as primitive. Such abstraction is valuable because it
allows us to ignore the details of parts of a machine so that we can
concentrate on other aspects of the design. The fact that we have
swept a lot of complexity under the rug, however, does not mean that a
machine design is unrealistic. We can always replace the complex
primitives

by simpler primitive operations.

Consider the GCD machine. The machine has an instruction that computes
the remainder of the contents of registers `a` and `b` and
assigns the result to register `t`. If we want to construct the
GCD machine without using a primitive remainder operation,
we must specify how to compute remainders in terms of simpler
operations, such as subtraction. Indeed, we can write a
JavaScript function
that finds remainders in this way:

function remainder(n, d) { return n < d ? n : remainder(n - d, d); }

We can thus replace the remainder operation in the GCD machine's data paths with a subtraction operation and a comparison test. Figure 5.5 shows the data paths and controller for the elaborated machine. The instruction

assign("t", list(op("rem"), reg("a"), reg("b")))

function sqrt(x) { function good_enough(guess, x) { return abs(square(guess) - x) < 0.001; } function improve(guess, x) { return average(guess, x / guess); } function sqrt_iter(guess, x) { return good_enough(guess, x) ? guess : sqrt_iter(improve(guess, x), x); } return sqrt_iter(1.0); }

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

5.1.2
Abstraction in Machine Design