Skip to content

Unit 21: Variance

Learning Objectives

Students should

  • understand the definition of the variance of types: covariant, contravariant, and invariant.
  • be aware that the Java array is covariant and how it could lead to run-time errors that cannot be caught during compile time.

Motivation

Both the methods findLargest and contains takes in an array of reference types as parameters:

findLargest v0.5
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
GetAreable findLargest(GetAreable[] array) {
  double maxArea = 0;
  GetAreable maxObj = null;
  for (GetAreable curr : array) {
    double area = curr.getArea();
    if (area > maxArea) {
      maxArea = area;
      maxObj = curr;
    }
  }
  return maxObj;
}
contains v0.1
1
2
3
4
5
6
7
8
boolean contains(Object[] array, Object obj) {
  for (Object curr : array) {
    if (curr.equals(obj)) {
      return true;
    }
  }
  return false;
}

What are some possible arrays that we can pass into these methods? Let's try this: 

1
2
3
4
5
Object[] objArray = new Object[] { Integer.valueOf(1), Integer.valueOf(2) };
Integer[] intArray = new Integer[] { Integer.valueOf(1), Integer.valueOf(2) };

contains(objArray, Integer.valueOf(1)); // ok
contains(intArray, Integer.valueOf(1)); // ok

Line 4 is not surprising since the type for objArray matches that of parameter array. Line 5, however, shows that it is possible to assign an instance with run-time type Integer[] to a variable with compile-time type Object[].

Why Is It Possible?

We have explained the reason for this before and that is because for every reference type that is declared, Java automatically create an array type for that reference type such that follows the subtyping relationship of the reference type. In this case, since Integer <: Number <: Object, Java automatically create the corresponding array types [LInteger; <: [LNumber; <: [LObject;.

For simplicity, from this point onwards, if we have a reference type T, we will be using T[] to indicate the automatically generated array type for T. Now, note that we only create the array type for reference type. This means that for primitive type, the developer of Java language have to add special types corresponding to the array of primitive type.

Variance of Types

So far, we have established the subtype relationship between classes and interfaces based on inheritance and implementation. The subtype relationship between complex types such as arrays, however, is not so trivial. Let's look at some definitions.

The variance of types refers to how the subtype relationship between complex types relates to the subtype relationship between components.

Let \(C(S)\) corresponds to some complex type based on type \(S\). An array of type \(S\) is an example of a complex type.

We say a complex type is:

  • covariant if \(S <: T\) implies \(C(S) <: C(T)\)
  • contravariant if \(S <: T\) implies \(C(T) <: C(S)\)
  • invariant if it is neither covariant nor contravariant.

How to Memorize

Think of variant as an arrow (i.e., it has direction). Then, the word "contra" should evoke the feeling of "counter". In other words, the direction should be in the counter (i.e., opposite) direction. That's why for contravariant, we have \(S <: T\) implies \(C(S) :> C(T)\). Of course, it is actually written as \(C(T) <: C(S)\).

The word "co" should evoke the same direction (like co-payment, co-operation, etc). So, the direction should be in the same direction. That's why for covariant, we have \(S <: T\) implies \(C(S) <: C(T)\).

Lastly, invariant is simply neither.

Java Array is Covariant

Arrays of reference types are covariant in Java1. This means that, if \(S <: T\), then \(S[] <: T[]\).

For example, because Integer <: Object, we have Integer[] <: Object[] and we can do the following:

1
2
3
Integer[] intArray;
Object[] objArray;
objArray = intArray; // ok

1
2
3
Integer[] intArray;  // intArray::Integer[]
Object[] objArray;   // objArray::Object[]
objArray = intArray; // objArray::Object[]  <- intArray::Integer[] (ok because Integer[] <: Object[])

By making array covariant, however, Java opens up the possibility of run-time errors, even without typecasting!

Consider the following code:

Problematic Code
1
2
3
4
5
6
Integer[] intArray = new Integer[2] {
  Integer.valueOf(10), Integer.valueOf(20)
};
Object[] objArray;
objArray = intArray;
objArray[0] = "Hello!"; // <- compiles!
Problematic Code
1
2
3
4
5
6
Integer[] intArray = new Integer[2] {
  Integer.valueOf(10), Integer.valueOf(20)
};                      // intArray::Integer[]
Object[] objArray;      // objArray::Object[]
objArray = intArray;    // objArray::Object[]  <- intArray::Integer[]
objArray[0] = "Hello!"; // objArray[0]::Object <- "Hello!"::String (ok, because String <: Object)

On Line 5 above, we set objArray (with a compile-time type of Object[]) to refer to an object with a run-time type of Integer[]. This is allowed since the array is covariant.

On Line 6, we try to put a String object into the Object array. Since String <: Object, the compiler allows this. The compiler does not realize that at run-time, the Object array will refer to an array of Integer.

So we now have a perfectly compilable code, that will crash on us when it executes Line 6 -- only then would Java realize that we are trying to stuff a string into an array of integers!

This is an example of a type system rule that is unsafe. Since the array type is an essential part of the Java language, this rule cannot be changed without ruining existing code. We will see later how Java avoids this pitfall for other complex types (such as a list).

Detailed Explanation

The "Problematic Code" has no compile-time error but has run-time error.

  1. From line 1 to 4, we know the compile-time type of two variables: intArray is Integer[] and objArray is Object[].
  2. Assignment at line 5 has no compile-time error because we are assigning intArray of compile-time type Integer[] into objArray of compile-time type Object[] and Integer[] <: Object[].
  3. At line 6, the compile-time type of objArray[0] is Object because it is an element of objArray that has the type of Object[].
  4. Assignment at line 5 has no compile-time error because we are assigning a String into an Object and String <: Object.
  5. Hence, the code compiles without error.
  6. However, the run-time type of objArray is Integer[], so the run-time type of objArray[0] is Integer.
  7. Hence, assignment at line 5 is assigning a String into an Integer and this causes an error because String </: Integer.
  8. (5) shows that there is no compile-time error while (7) shows that there is a run-time error.

Producer/Consumer

Variance is closely related to the concept of producer/consumer. We will encounter this concept again later. For now, we can simply introduce the following obvious definition.

Producer

Producer produces value.

Consumer

Consumer consumes value.

We will show two different of producer/consumer.

Kind as Producer as Consumer
Array X x = arr[n]; arr[n] = value;
Function X x = f(arg); (i.e., return value is produced) f(value); (i.e., argument is consumed)

Type Problems

There are some type problems related to producer/consumer and variance of types. We have seen one such example above. Due to covariance of Java array, there are some run-time errors that cannot be detected by our compiler. Notice that this happens when we treat the array as a consumer. We can actually state this more generally,

There will be some run-time errors that cannot be detected by compiler when having producer consumer covariant.

A more general example is as follows but we will illustrate using array. Consider A1 <: B and A2 <: B. By covariance, A[] <: B[]. Then the following code will not produce compilation error but will produce run-time error.

1
2
3
4
A1[] aArr = new A1[] { new A1(), new A1() };
B[] bArr = aArr;    // assume covariant: A1[] <: B[]
bArr[0] = new A2(); // compiles because A2 <: B
                    // but this is a run-time error

In this case, we see that bArr is used as a consumer (i.e., it consumes the value of new A2()).

We can also state the opposite problem.

There will be some run-time errors that cannot be detected by compiler when having consumer producer contravariant.

We will use the same subtyping relationship as above. However, note that the following code is simply hypotheticals because Java array is not contravariant.

1
2
3
4
B[] bArr = new B[] { new A1(), new A2() };
A1[] aArr = bArr;   // assume contravariant: B[] <: A1[]
A1 a1 = aArr[2];    // compiles because A1 <: A1
                    // but this is a run-time error

In this case, we see that aArr is used as a producer (i.e., it produces the value in aArr[2]).

  1. Arrays of primitive types are invariant. ↩