Java Reference
In-Depth Information
of an array or allowing a pointer to progress one position past the end of an
array.
We can support array bounds checking by including a ”size” parameter
with every array passed as a parameter and every pointer that steps through
an array. This size value serves as an upper bound, indicating the extent of
access allowed. Nevertheless, it is clear that bounds checking is a di
cult
issue in languages where the di
ff
erence between pointers and array addresses
is blurred.
Array parameters often require information beyond a pointer to the ar-
ray's data values. This includes information on the array's size (to implement
assignment) and information on the array's bounds (to allow subscript check-
ing). An array descriptor (sometimes called a
dope vector
), containing this
information, can be passed for array parameters instead of just a data pointer.
Non-Zero Lower Bounds
In C, C
and Java, arrays always have a lower bound of zero. This simplifies
array indexing. Still, a single fixed lower bound can lead to clumsy code
sequences. Consider an array indexed by years. Having learned in 1999 not
to represent years as just two digits, we may prefer to use a full four-digit year
as an index. Assuming we really want to only use years of the twentieth and
early twenty-first centuries, an array starting at 0 is very clumsy. But so is
explicitly subtracting 1900 from each index before using it.
A few languages, like Pascal and Ada, have already solved this problem.
An array of the form A[low..high] may be declared, where all indices in the
range low
++
high are allowed. With this array form, we can easily declare an
array indexed by four digit years: data[1900..2020].
With a non-zero lower bound, our formula for the size of an array must
be generalized a bit:
,...,
size
(
array
)
=
(
UpperBound
−
LowerBound
+
1)
∗
size
(
Element
)
How much does this generalization complicate array indexing? Actually,
surprisingly little. If we take the Java approach, we just include the lower
bound as part of the array object we allocate. If we compute an element
address in the code we generate, the address formula introduced above needs
to be changed a little:
address
(
A
[
i
])
=
address
(
A
)
+
(
i
−
low
)
∗
size
(
Element
)
We subtract the array's lower bound (
low
) before we multiply by the element
size. Now it is clear why a lower bound of zero simplifies indexing—a sub-
traction of zero from the array index can be skipped. But the above formula
