# SICP Solutions

### Chapter 5, Computing with Register Machines

#### (a)

Let’s first look at some results:

From the data above($\, n \ge 2 \,$ ), clearly we have:

$$\, \text{total-pushes} = 6n + 1 \,$$

and,

$$\, \text{maximum-depth} = 3n - 1 \,$$

Lets compare them:

total-pushes maximum-depth
special-purpose $\, 2(n-1) \,$ $\, 2(n-1) \,$
interpreter $\, 32n-16 \,$ $\, 5n+3 \,$
compiler $\, 6n+1 \,$ $\, 3n-1 \,$
compiler vs interpreter $\, \frac 6 {32} = \frac 3 {16} \,$ $\, \frac 3 5 \,$
special vs interpreter $\, \frac 2 {32} = \frac 1 {16} \,$ $\, \frac 2 5 \,$
special vs compiler $\, \frac 2 6 = \frac 1 3 \,$ $\, \frac 2 3 \,$

#### (b)

Looking at the intructions generated, one big difference is handling of operations -, = and *.

For each of these operations compiled code do extra saves and restores and specially in the case like =, where no registers(except flag but which is internal so doesnt count) gets modified!

Well, what if we can use primitive operations as suggested in ex-5.38!

With that change, here are the stats:

Thus we get:

$$\, \text{total-pushes} = 2n + 3 \,$$

and,

$$\, \text{maximum-depth} = 2n - 2 \,$$

And these are of the same order as the compiled version!

Are such optimizations always possible? I dont think so. Consider the cases when we have non primitive operations(compound procedures) similar to =, or * which does modify only a few registers.

I think it is quite difficult to deduce that which registers a compound procedure modifies and thus avoiding there save and restores.

Also, there are things that we just can not do inside a compiler. For eg:

• A compiler either does a left to right evaluation or a right to left evaluation but not both at the same time. In some cases, one order might be better then other as it will require fewer number of saves and restores. We can always take advantage of this in special purpose machine.

Things have finally all came into a complete story!

I was wondering whether my solutions related to open code changes(ex-5.38) and compile time environment will work correctly. Turns out they did!

There are a few things to do to make those changes work:

(All the changes are in same file ch5-eceval-compiler.scm)

• Add following lines under eceval-operations in the mentioned file:
• Also, add the following new registers(change is marked with ;;;) for open code arguments:
• Add following change in file ch5-compiler.scm in procedure compile-and-go:

Other changes and their locations I have mentioned in ex-5.45