TAOCP 1.3.2 Exercise 7

In MIX assembly (as used in _The Art of Computer Programming_), symbolic addresses of the form $kH$ and $kB$ refer to the $k$-th occurrence of the symbol $k$, searching forward (H = “here or ahead”) o...

taocpmathematicsalgorithmsvolume-1simple

Section 1.3.2: The MIX Assembly Language

Exercise 7. [10] (a) What is the meaning of 4B in line 34 of Program P? (b) What effect, if any, would be caused if the location of line 15 were changed to 2H and the address of line 20 were changed to 2B?

Verified: yes
Solve time: 3m03s

In MIX assembly (as used in The Art of Computer Programming), symbolic addresses of the form $kH$ and $kB$ refer to the $k$-th occurrence of the symbol $k$, searching forward (H = “here or ahead”) or backward (B = “back”), respectively, from the current location in the program listing.

(a) Meaning of 4B in line 34

The operand 4B means:

The address of the fourth preceding occurrence of the symbolic label 4, when scanning the program upward from line 34.

More precisely, starting at line 34, one scans backward through the program listing and counts occurrences of the label 4. The fourth such occurrence determines the target address.

There is no transformation into another label class and no notion of “H-direction conversion.” The suffix B is purely a directional search rule for resolving a symbolic reference.

So J5P 4B means:

Jump to the instruction located at the fourth previous definition of symbol 4, if the condition for J5P is satisfied.

(b) Effect of changing line 15 to 2H and line 20 to 2B

In MIX, changing a line to 2H or 2B does not merely rename a label. It creates or redefines occurrences of the symbolic label 2, and therefore changes how any future references to symbol 2 are resolved.

What changes structurally

  • 2H marks that line as a forward (H) occurrence of symbol 2.
  • 2B marks that line as a backward (B) occurrence of symbol 2.

After the modification:

  • Any instruction referring to 2H will now resolve to the next forward occurrence of symbol 2, which includes the newly assigned line 15.
  • Any instruction referring to 2B will now resolve to the nearest backward occurrence of symbol 2, which now includes the newly assigned line 20.

Consequence for program behavior

This change can alter control flow in any place where symbol 2 is used as a jump target or address reference.

In particular, if the original program already uses symbol 2 for control transfers (which is typical in MIX programs, where numeric symbols structure loops and conditional exits), then:

  • Some jumps that previously targeted an earlier or later point will now be redirected to line 15 or line 20.
  • This can swap loop entry and exit points or redirect flow into the middle of a different control block.

Even though line 34’s instruction 4B is unaffected (it depends only on symbol 4), the modification introduces a semantic change in the resolution of symbol 2, which is independent of 4.

Conclusion

The effect is not syntactically local. It is a global change to the symbol table behavior for symbol 2. Therefore:

  • The control flow of Program $P$ is altered wherever 2H or 2B is referenced.
  • This can disrupt loop structure and conditional branching.
  • The program is no longer guaranteed to generate primes correctly, because control transfers that depended on the original placement of symbol 2 will now resolve to different instructions.

Final summary

(a) 4B is the address of the fourth preceding occurrence of label 4 in the program listing.

(b) Relabeling lines as 2H and 2B redefines the forward and backward occurrences of symbol 2, changing the targets of any instructions that reference symbol 2. This alters control flow and generally breaks the original program structure.