next up previous contents
Next: Subroutines Up: Designing Register Machines Previous: A Language for Describing

Abstraction in Machine Design

We will often define a machine to include ``primitive'' operations that are actually very complex. For example, in sections [*] and [*] we will treat Scheme'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 that finds remainders in this way:

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


  \begin{figure}\par\figcaption {Data paths and controller for the elaborated GCD machine.}\par\end{figure}

(assign t (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 [*].


 \begin{figure}% latex2html id marker 26054
<pre>
(controller
test-b
(test (op ...
...n sequence for the GCD machine in
figure~\ref{fig:gcd-machine-rem}.}\end{figure}

Exercise. Design a machine to compute square roots using Newton's method, as described in section [*]:

(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))
Begin by assuming that 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.


next up previous contents
Next: Subroutines Up: Designing Register Machines Previous: A Language for Describing
Ryan Bender
2000-04-17