Section 2.1. Subtyping and the Substitution Principle

2.1. Subtyping and the Substitution Principle

Subtyping is a key feature of object-oriented languages such as Java. In Java, one type is a subtype of another if they are related by an extends or implements clause. Here are some examples:

Integer	is a subtype of	Number
Double	is a subtype of	Number
ArrayList<E>	is a subtype of	List<E>
List<E>	is a subtype of	Collection<E>
Collection<E>	is a subtype of	Iterable<E>

Subtyping is transitive, meaning that if one type is a subtype of a second, and the second is a subtype of a third, then the first is a subtype of the third. So, from the last two lines in the preceding list, it follows that List<E> is a subtype of Iterable<E>. If one type is a subtype of another, we also say that the second is a supertype of the first. Every reference type is a subtype of Object, and Object is a supertype of every reference type. We also say, trivially, that every type is a subtype of itself.

The Substitution Principle tells us that wherever a value of one type is expected, one may provide a value of any subtype of that type:

Substitution Principle: a variable of a given type may be assigned a value of any subtype of that type, and a method with a parameter of a given type may be invoked with an argument of any subtype of that type.

Consider the interface Collection<E>. One of its methods is add, which takes a parameter of type E:

 interface Collections<E> {   public boolean add(E elt);   ... } 

According to the Substitution Principle, if we have a collection of numbers, we may add an integer or a double to it, because Integer and Double are subtypes of Number.

 List<Number> nums = new ArrayList<Number>(); nums.add(2); nums.add(3.14); assert nums.toString().equals("[2, 3.14]"); 

Here, subtyping is used in two ways for each method call. The first call is permitted because nums has type List<Number>, which is a subtype of Collection<Number>, and 2 has type Integer (thanks to boxing), which is a subtype of Number. The second call is similarly permitted. In both calls, the E in List<E> is taken to be Number.

It may seem reasonable to expect that since Integer is a subtype of Number, it follows that List<Integer> is a subtype of List<Number>. But this is not the case, because the Substitution Principle would rapidly get us into trouble. It is not always safe to assign a value of type List<Integer> to a variable of type List<Number>. Consider the following code fragment:

 List<Integer> ints = Arrays.asList(1,2); List<Number> nums = ints;  // compile-time error nums.add(3.14); assert ints.toString().equals("[1, 2, 3.14]");  // uh oh! 

This code assigns variable ints to point at a list of integers, and then assigns nums to point at the same list of integers; hence the call in the third line adds a double to this list, as shown in the fourth line. This must not be allowed! The problem is prevented by observing that here the Substitution Principle does not apply: the assignment on the second line is not allowed because List<Integer> is not a subtype of List<Number>, and the compiler reports that the second line is in error.

What about the reverse? Can we take List<Number> to be a subtype of List<Integer>? No, that doesn't work either, as shown by the following code:

 List<Number> nums = Arrays.<Number>asList(2.78, 3.14); List<Integer> ints = nums;  // compile-time error assert ints.toString().equals("[2.78, 3.14]");  // uh oh! 

The problem is prevented by observing that here the Substitution Principle does not apply: the assignment on the second line is not allowed because List<Integer> is not a subtype of List<Number>, and the compiler reports that the second line is in error.

So List<Integer> is not a subtype of List<Number>, nor is List<Number> a subtype of List<Integer>; all we have is the trivial case, where List<Integer> is a subtype of itself, and we also have that List<Integer> is a subtype of Collection<Integer>.

Arrays behave quite differently; with them, Integer[] is a subtype of Number[]. We will compare the treatment of lists and arrays later (see Section 2.5).

Sometimes we would like lists to behave more like arrays, in that we want to accept not only a list with elements of a given type, but also a list with elements of any subtype of a given type. For this purpose, we use wildcards.