We will often define a machine to include primitive operations that are actually very complex. For example, in sections 5.4 and 5.5 we will treat Scheme's 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 Scheme procedure JavaScript function that finds remainders in this way:

Original	JavaScript
(define (remainder n d) (if (< n d) n (remainder (- n d) d)))	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.6 shows the data paths and controller for the elaborated machine. The instruction

Figure 5.6 Data paths and controller for the elaborated GCD machine.

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

in the GCD controller definition is replaced by a sequence of instructions that contains a loop, as shown in figure 5.7.

Original	JavaScript
(controller test-b (test (op =) (reg b) (const 0)) (branch (label gcd-done)) (assign t (reg a)) rem-loop (test (op <) (reg t) (reg b)) (branch (label rem-done)) (assign t (op -) (reg t) (reg b)) (goto (label rem-loop)) rem-done (assign a (reg b)) (assign b (reg t)) (goto (label test-b)) gcd-done)	controller( list( "test_b", test(list(op("="), reg("b"), constant(0))), branch(label("gcd_done")), assign("t", reg("a")), "rem_loop", test(list(op("<"), reg("t"), reg("b"))), branch(label("rem_done")), assign("t", list(op("-"), reg("t"), reg("b"))), go_to(label("rem_loop")), "rem_done", assign("a", reg("b")), assign("b", reg("t")), go_to(label("test_b")), "gcd_done"))

Figure 5.7 Controller instruction sequence for the GCD machine in figure 5.6.

Exercise 5.3 Design a machine to compute square roots using Newton's method, as described in section 1.1.7 and implemented with the following code in section 1.1.8:

Original	JavaScript
(define (sqrt x) (define (good-enough? guess) (< (abs (- (square guess) x)) 0.001)) (define (improve guess) (average guess (/ x guess))) (define (sqrt-iter guess) (if (good-enough? guess) guess (sqrt-iter (improve guess)))) (sqrt-iter 1.0))	function sqrt(x) { function is_good_enough(guess) { return math_abs(square(guess) - x) < 0.001; } function improve(guess) { return average(guess, x / guess); } function sqrt_iter(guess) { return is_good_enough(guess) ? guess : sqrt_iter(improve(guess)); } return sqrt_iter(1); }

Begin by assuming that good-enough? is_good_enough and improve operations are available as primitives. Then show how to expand these in terms of arithmetic operations. Describe each version of the sqrt machine design by drawing a data-path diagram and writing a controller definition in the register-machine language.

Add solution

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.