Implementation of Array Types
Implementing arrays requires considerably more compile-time effort than does implementing primitive types. The code to allow accessing of array elements
must be generated at compile time. At run time, this code must be executed to produce element addresses. There is no way to precompute the address to be accessed by a reference such as
A single-dimensioned array is implemented as a list of adjacent memory cells. Suppose the array list is defined to have a subscript range lower bound of 0. The access function for list is often of the form
address(list[k]) = address(list) k * element_size
where the first operand of the addition is the constant part of the access function, and the second is the variable part.
If the element type is statically bound and the array is statically bound to storage, then the value of the constant part can be computed before run time. However, the addition and multiplication operations must be done at run time. The generalization of this access function for an arbitrary lower bound is
address(list[k]) = address(list[lower_bound]) ((k - lower_bound) * element_size)
The compile-time descriptor for single-dimensioned arrays can have the form shown in Figure 6.4. The descriptor includes information required to construct the access function. If run-time checking of index ranges is not done and the attributes are all static, then only the access function is required during execution; no descriptor is needed. If run-time checking of index ranges is done, then those index ranges may need to be stored in a run-time descriptor. If the subscript ranges of a particular array type are static, then the ranges may be
incorporated into the code that does the checking, thus eliminating the need for the run-time descriptor. If any of the descriptor entries are dynamically bound, then those parts of the descriptor must be maintained at run time. True multidimensional arrays, that is, those that are not arrays of arrays, are more complex to implement than single-dimensioned arrays, although the extension to more dimensions is straightforward. Hardware memory is linear— it is usually a simple sequence of bytes. So values of data types that have two or more dimensions must be mapped onto the single-dimensioned memory.
There are two ways in which multidimensional arrays can be mapped to one dimension: row major order and column major order.
In row major order, the elements of the array that have as their first subscript the lower bound value of that subscript are stored first, followed by the elements of the second value of the first subscript, and so forth. If the array is a matrix, it is stored by rows. For example, if the matrix had the values
it would be stored in row major order as
3, 4, 7, 6, 2, 5, 1, 3, 8
In column major order, the elements of an array that have as their last subscript the lower bound value of that subscript are stored first, followed by the elements of the second value of the last subscript, and so forth. If the array is a matrix, it is stored by columns. If the example matrix were stored in column major order, it would have the following order in memory:
3, 6, 1, 4, 2, 3, 7, 5, 8
Column major order is used in Fortran, but other languages that have true multidimensional arrays use row major order.