Wednesday, February 25, 2009

SICP Section 5.1 Designing Register Machines

Exercise 5.2. (and 5.1) Use the register-machine language to describe the iterative factorial machine of exercise 5.1.


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

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.

Answer: I am skipping the data-path diagrams for the three different versions of sqrt. Controller definitions of the three versions in the register-machine language follow. All three versions assume that abs, square and average are available as primitive operations along with - and /.

Version 1.

Version 2. In this version good-enough? is expanded using arithmetic operations.

Version 3. Improve is also expanded using arithmetic operations.

Exercise 5.4. Specify register machines that implement each of the following procedures. For each machine, write a controller instruction sequence and draw a diagram showing the data paths.

a. Recursive exponentiation:

b. Iterative exponentiation:

a. Recursive exponentiation.

b. Iterative exponentiation.

Exercise 5.5. Hand-simulate the factorial and Fibonacci machines, using some nontrivial input (requiring execution of at least one recursive call). Show the contents of the stack at each significant point in the execution.

Answer: (factorial 3)
continue = fact-done; n = 3;

Iteration round 1.
Test (= n 1) fails.
Stack: continue => fact-done; n=> 3.
n = 2; continue = after-fact.

Iteration round 2.
Test (= n 1) fails.
Stack: continue => after-fact, fact-done; n=> 2, 3.
n = 1; continue = after-fact.

Iteration round 3.
Test (= n 1) succeeds. Proceed to base-case
val = 1; proceed to after-fact

After-fact round 1.
n <= 2. continue <= after-fact.
Stack: continue => fact-done; n=> 3.
val = 2 * 1 = 2

After-fact round 2.
n <= 3. continue <= fact-done.
Stack: empty
val = 3 * 2 = 6
Proceed to fact-done

Exercise 5.6. Ben Bitdiddle observes that the Fibonacci machine's controller sequence has an extra save and an extra restore, which can be removed to make a faster machine. Where are these instructions?

Answer: The redundant save and restore statements occur in the set of instructions labeled afterfib-n-1. The (restore continue) and (save continue) statements that occur at the top can be removed as the value of continue will never change between restore and save calls. The machine can be now re-written as follows:

No comments: