TAOCP 2.2.2 Exercise 5

Section 2.2.2: Sequential Allocation

Exercise 5. [35] The extension of MIX suggested in exercise 3 has an unfortunate restriction that "7:7" is not allowed in an indirectly addressed location.

a) Give an example to indicate that, without this restriction, it would probably be necessary for the MIX hardware to be capable of maintaining a long internal stack of three-bit items. (This would be prohibitively expensive hardware, even for a mythical computer like MIX.)

b) Explain why such a stack is not needed under the present restriction; in other words, design an algorithm with which the hardware of a computer could perform the desired address modifications without much additional register capacity.

c) Give a milder restriction than that of exercise 3 on the use of 7:7 that alleviates the difficulties of exercise 4(c), yet can be cheaply implemented in computer hardware.

Verified: no
Solve time: -

Setup

Exercise 3 introduces address modifications of the form I1:I2, where modification 7 means: interpret the addressed location as another address specification and continue the address-modification process from there. The restriction imposed in exercise 3 is that a location whose modification field is 7:7 may not be used as an indirectly addressed location.

Part (a) asks for an example showing that, without this restriction, address evaluation could require an arbitrarily deep stack of pending modifications.

Part (b) asks for an algorithm showing that, with the restriction in force, address evaluation can be carried out with only a small fixed amount of auxiliary storage.

Part (c) asks for a weaker restriction than forbidding all occurrences of 7:7, while still avoiding the difficulties exhibited in part (a).

Solution

(a)

Consider the instruction

LDA A,7:7

and suppose location A contains

NOP B,7:7

location B contains

NOP C,7:7

location C contains

NOP D,7:7

and so on.

To evaluate A,7:7, the machine must first perform modification 7. This requires it to examine location A, whose modification field is again 7:7. The first component of that field must be executed before the second component can be applied. Thus evaluation of the outer 7:7 is suspended while the inner 7:7 is processed.

At location B the same situation occurs. Evaluation of the 7:7 at A remains unfinished while evaluation of the 7:7 at B begins. Then evaluation of the 7:7 at C begins, and so on.

After reaching a location whose modification field is not 7:7, the machine must return to complete the suspended second modifications in reverse order. If there are $m$ successive locations having modification field 7:7, there are $m$ pending second modifications waiting to be executed.

Since $m$ can be arbitrarily large, the hardware must be able to store an arbitrarily long sequence of pending three-bit modification codes. Hence a potentially long internal stack of three-bit items is required.

This is precisely the difficulty alluded to in exercise 4(c), where repeated indirect references can generate arbitrarily deep nesting.

(b)

Assume now that no indirectly addressed location contains modification field 7:7.

Let the current address specification be (A,p:q).

The hardware maintains only the current address specification together with one temporary three-bit register.

Proceed as follows.

If neither $p$ nor $q$ equals $7$, perform modification $p$, then modification $q$, and stop.
If $p=7$, save $q$ in the temporary register.
Replace the current address specification by the address specification stored in location $A$.
Because 7:7 is forbidden in indirectly addressed locations, the newly obtained specification cannot have both modification components equal to $7$.
Evaluate this new specification completely, obtaining an address $M$.
Apply the saved modification $q$ to $M$.

The same procedure is used when $q=7$.

The crucial point is that after entering an indirectly addressed location, at most one pending modification must be remembered. A second pending modification cannot arise, because the indirect location is forbidden to contain 7:7. Therefore the amount of auxiliary information that must be saved is bounded by a fixed constant, independent of the length of the indirect chain.

No stack is required.

(c)

A weaker restriction is obtained by forbidding only indirectly reachable occurrences of 7:7.

More precisely, permit locations to contain modification field 7:7, but require that whenever modification 7 follows a reference to a location $X$, the specification stored in $X$ is not 7:7.

Then instructions explicitly written as

LDA A,7:7

remain legal. The machine needs only one pending modification while evaluating the indirect reference at A.

What is excluded is a chain

A -> B -> C -> ...

in which an indirectly reached location again contains 7:7, creating nested suspensions of pending modifications. Such nesting is exactly what produces the unbounded stack requirement of part (a).

Under this milder restriction, arbitrarily deep chains of indirect references are still allowed, but the depth of simultaneously pending modification operations is bounded by one. Hence the address computation can be implemented with only a fixed number of temporary registers.

Verification

In part (a), after traversing a chain of $m$ locations whose modification fields are all 7:7, there are $m$ unfinished second modifications. Any correct evaluation must remember all of them until the chain terminates. Therefore storage proportional to $m$ is required.

In part (b), the prohibition of 7:7 in indirectly addressed locations guarantees that once a modification 7 has been entered, no further pair of pending modifications can be generated before the current indirect reference is resolved. A single temporary register therefore suffices.

In part (c), the proposed restriction eliminates exactly the source of unbounded nesting while allowing more programs than the blanket prohibition of exercise 3. The hardware requirement remains bounded.

Notes

The essential distinction is between the length of an indirect-address chain and the depth of unresolved modification operations. Long chains can be processed iteratively. Unbounded nesting of 7:7 requires a stack. The restriction of exercise 3 eliminates such nesting completely; the restriction of part (c) eliminates only the nested cases.