The first machines I knew used no data or code addresses except those explicitly stored in the instruction stream. Most instructions had a fixed portion that held an address, probably of data, but sometimes of code that the CPU might switch its attention to. The ‘effective address’ (modern jargon) was exactly that found in memory; there were no index registers or general registers. On the IBM 701 (1954) here is a typical loop (one machine instruction per line) to sum the numbers in locations 100 thru 199:
There was another register, the MQ, but it was useless for this job. Each of these instructions required two sequential memory cycles (12 μsec each) except tz and t which required one. 22*12 = 264 μs / iteration. The instructions were 18 bits each. See this for more detail on instructions. The address was 12 bits long. Words, not bytes, were addressed. The 704 arrived in 1956 with index registers. The above loop was reduced to:
Index registers values were subtracted from the address in the instruction. The instructions were 36 bits and an address occupied 15 bits within the instruction and an index register. The control block had not been invented and a physics problem with a 1000 points and 10 variables per point would use 10 arrays of 1000 numbers. An index register would hold a small integer identifying the current point. You can probably guess the sort of code required on the 701. Fortran assumed this pattern and included no features suitable to a control block.
The first Fortrans had arrays but not structures. Early operating systems, which were written in assembler, would assign an index to a new job and Job 9’s file system root would be found in FSR of the array of roots FSR. Many different arrays would each be indexed by job number. These arrays were typically fixed in size and their origins would be scattered in the instruction stream. The different arrays would have several different element sizes so that shifting or even multiplying would be required to apply a job index to the array.
See some history of segmented addressing architectures.
The IBM 360 could not store large addresses directly in the code stream and I was not yet convinced that control blocks could entirely supplant arrays. When Fortran compiled array oriented code for the 360 it had to spend extra instructions loading array origins in order to compute the address of the array element. It seemed to do conceptual damage to a program to transform it from arrays to structures. One reason is that in physics element i is related to element i+1 and this is naturally expressed with arrays. In short the array index, as integer, has topological meaning. It can be naturally done with arrays of structures but arrays of structures still cause compilers problems with remembering array origins. A future side benefit of control blocks was that they were more cache efficient; but they arose before caches.
This is the earliest application that I am aware of, of polymorphism. The FCB included (rather than shared) the v-table. The compilers could compile polymorphic call sites that were cognizant of the layout of the FCB. Alas that compiler logic was restricted to the particular logic of IBM’s file systems.
In the beginning the only concept of multiple data in a computer was that of array. (Well before the beginning there were machines without sufficient memory to contemplate even a small array. Babbage’s proposed engine would hold only a few variables.) The first Fortran provided arrays whose size was fixed at compile time. There were no pointers or structures. For complex applications that would use structures and pointers today, several arrays would be declared of the same length and in place of a pointer to a structure an index into these arrays would be used. The program failed it the common array size was exhausted. Early operating systems used this plan for their internal state.
Digitek pioneered a scheme for growable arrays. It adopted the convention that each reference to the array consults a fixed place that describes the current size and location of that array. When the array needs to grow it and other arrays may be moved in necessary. There is only one place where the location of an array is kept. I can remember being impressed with this scheme. Using this technique Digitek produced a series of moderately fast Fortran compilers. These compilers cost about $50,000 each and drove other compiler technologies out of the market except for a few compilers known for their excellent optimizations.