Arrays

An array is an indexed sequence $s_0, s_1, s_2, ..., s_n$, $n>=0$ of data values of fixed length. In contrast to more general representations for sequences an array object cannot grow or shrink. It has a specific length $n>=0$ when it is created and retains this length during its entire lifetime. Java arrays are almost identical to Scheme vectors; the only difference is that every array in Java has a declared type T[] asserting that all elements of the array have type T. All of the primitive operations on arrays in Java preserve the declared types attached to arrays. Given an array a of type T[], the expresssion a[i] extracts the ith element of the array, which must be a value of type T. Array indexing begins with the integer value 0 as in Scheme, C, and C++. Hence, an array of length $n$ has valid indices of $0, 1, ..., n-1$.

The assignment operator = is used to update array elements. Given an array a of type T[], the statement

a[i] = e;

updates the value of the ith element to the value of the expression e. The values of all other elements of a remain unchanged.

In Java, arrays of every type are built into the language. If you define a class or interface C, then the array type C[] is automatically supported by Java. Every array type is a subtype of type Object, but array types cannot be extended. In essence, Java arrays are identical Scheme vectors augmented by an enforced type constraint. If a Java variable has type T[] for some primitive or object type T then it can only be bound to arrays containing elements of type T. Every Java array has a int field length that contains the length of the array.

Since Java arrays are objects, a Java array value is actually a reference to an array. Hence, a variable of type T[] in Java can have the value null. A variable of type T[] can appear on the left-hand side of an assignment

a = e

where e is any expression of type T.

Since array values are references to arrays, two variables can be bound to exactly the same array. If array variables a and b are bound to the same array object, then updating an array of a

a[i] = e;

changes the value of b[i]. Scheme variables bound to vectors have precisely the same property.

Arrays are allocated in Java using the new statement just like other objects. The array form is

new T[length]

where T is any type and length is an expression that evaluates to a non-negative int. Arrays can have length 0. Each element of the array is set to the `zero'' value of the declared type T. If T is an object type, the initial value of each element is null. Hence, the expression

new String[1000]

allocates an array of 1000 String elements all bound to null.

Java has alternate form for constructing an array called an anonymous array. The expression

new T[] { $v_0, ... v_{n-1}$}

allocates an array of length n of type T containing the specified sequence of elements.

Java uses two mechanisms to enforce the declared type T[] of an array object. First, when an array T[] is allocated, all of the initial element values must be of type T. Second, when an array object a of type T][] is updated by an assignment

a[i] = e

Java confirms that the the new value e for the ith element belongs to the type T. During program execution, the Java virtual machine confirms the the value e belongs to type T each time that the assignment is executed.

The array-assignment check must be performed at run-time because an array object of type S[] can be stored in a local variable or field of type T[] where S is a subtype of T. Hence, in the preceding array assignment, the declared (static) type T of e could match the declared type T[] of the array variable a, yet the assignment could fail at run-time because the value of a is an array of type S where S is a proper subtype of T.

The Java type system permits an array variable of type T[] to be bound to an array A of type S[] provided $S \subseteq T$. This property of the Java type system is called covariant subtyping. Note that covariant subtyping implies that the array type Object[] is a supertype for all object array types, which permits arrays to be treated polymorhically in many situations.