When we examined how a compiler can represent arrays in memory and compute a d-dimensional array reference in O(d) time, we assumed that the basic RAM model includes the ability to perform indirect addressing. That is, for a fixed integer x, not only are there machine instructions to read or write to memory location. x, but in O(1) time we can also read or write to the memory location y, where y is the value stored in memory location x. Indirect addressing corresponds exactly to the notion of a one dimensional array. For example, an assignment statement like x := A[i] does not place the contents of the memory location i into x; rather, it copies the contents of a memory location that is determined by the value of i. Assume that computer programs are encoded in binary and placed in one portion of memory, and another portion of memory is used for the data that is manipulated by the program.
A. Suppose that programs do not have indirect addressing but are allowed to modify memory locations in the area where the program is stored. Show how such programs can effectively perform indirect addressing in 0(1) time by modifying arguments to their own instructions.
B. Suppose that programs do have indirect addressing but are not allowed to modify memory locations in the area where the program is stored. Describe how the actions of a program that can modify itself can be simulated in O( 1) time per instruction.
C. Discuss the practical merits of the models of Parts A and B, and whether it is useful to have the features of both.