Generics and Wildcards in Java

On generics and wildcards in Java (a.k.a., parametric polymorphism, type bounds, type variance)

Photo by Dimitri Houtteman on Unsplash

Note: This article is adapted from my book Functional and Concurrent Programming: Core concepts and Features, published by Addison-Wesley. See, in particular, Chapter 15 on Types (and Related Concepts).

Ever wondered what the syntax<? extends T> or <? super T> in Java was for? Why do we need it? How to use it? If so, this article is for you. It will also briefly discuss alternatives in languages that support covariant and contravariant types.

Generics

In modern typed programming languages, a type can be parametrized by another type, a feature sometimes known as parametric polymorphism. In Java, this takes the form of so-called generics, introduced in Java 5.

For instance, List can be parametrized as List<String> or List<Number>, making it possible for the compiler to check that a number is never inserted into a list of strings or a string into a list of numbers. This way, no typecasts (and potential ClassCastException) are needed in the code.

Type invariance

In Java, Integer is a subtype of Number. Do you know, however, that List<Integer> is not a subtype of List<Number>? More importantly, do you know why?

Consider the following illustration. Assume a simple type hierarchy:

A simple type hierarchy.

where Publication is defined as:

interface Publication {
  String title();
}

and Book and Magazine are two classes that implement the interface.

Since all objects of type Publication have a title method, code can be written to print all the titles of a list of publications as follows:

void printTitles(List<Publication> collection) {
  for (Publication p : collection)
    System.out.println(p.title());
}

Now assume that the contents of a library have been stored as a list of books:

List<Book> library = ...

It would seem natural to use method printTitles to print the titles of the books in the library, since books are publications.

However, the call printTitles(library) fails with the following error:

Error:(57, 22) java: incompatible types: java.util.List<Book> cannot be converted to java.util.List<Publication>

Even though Book is a subtype of Publication, List<Book> is not a subtype of List<Publication>.

Liskov Substitution Principle

The substitution principle states that if a type T is a subtype of a type U, you can substitute a value of type T wherever a value of type U is required. In other words, a subtype has to offer all the services of the supertype.

The problem here is that a value of type List<Book> does not offer all the services of a value of type List<Publication>. The call printTitles(library) may seem harmless, but consider this variant of the printing method:

void printTitlesAndAddMagazine(List<Publication> collection) {
  for (Publication p : collection)
    System.out.println(p.title());
  collection.add(new Magazine(...));
}

If the call printTitles(library) is valid, so is the call printTitlesAndAddMagazine(library), since the two methods have the same signature. But the latter would add a magazine to a list of books! Since Magazine is not a subtype of Book, this would break type safety. Adding a magazine is a service that is supported by List<Publication> but not by List<Book>.

Type bounds

Since printTitles does not care about adding magazines to the collection, its signature can be modified to enable the call printTitles(library):

void printTitles(List<? extends Publication> collection) {
  for (Publication p : collection)
    System.out.println(p.title());
}

List<? extends Publication> is the type of a list in which the elements have an unspecified type that is a subtype of Publication (or Publication itself). In particular, List<Book> is a subtype of List<? extends Publication> and the call printTitles(library) is now valid. Since an element p of the list must be of a type that is a subtype of Publication, it also has type Publication and thus a title method.

At this point, the acute reader might be thinking: What prevents me from using the same trick in printTitlesAndAddMagazine to enable a call printTitlesAndAddMagazine(library), which would break type safety?

void printTitlesAndAddMagazine(List<? extends Publication> collection) {
  for (Publication p : collection)
    System.out.println(p.title());
  collection.add(new Magazine(...)); // rejected at compile-time
}

The last line of the method cannot be compiled. The type of the list elements is an unknown subtype of Publication, and there is no guarantee that this type can contain values of type Magazine. To add a magazine to the list, we would need to know that the type of the list elements is a supertype of Magazine (or the type Magazine itself). Java has a syntax for that. A method addMagazine can be written as follows:

void addMagazine(List<? super Magazine> collection) {
  collection.add(new Magazine(...));
}

Method addMagazine can be called on a List<Magazine> or on a List<Publication>, or even on a List<Object>.

The syntax ? extends T specifies a type upper bound — the type must be a subtype of T; the syntax ? super T specifies a type lower bound — the type must be a supertype of T. Java does not allow the specification of both an upper bound and a lower bound (though some languages do, e.g., Scala). Method printTitlesAndAddMagazine must use List<Publication> exactly in its signature.

Naming types

In the examples so far, the type of the list elements has been unnamed. It could also be named, while remaining unspecified. This variant of method printTitles is possible:

<A extends Publication> void printTitles(List<A> collection) {
  for (Publication p : collection)
    System.out.println(p.title());
}

Here, the type of the list elements becomes a type argument of the method, named A (but it remains unspecified, with an upper bound).

Naming types this way has several advantages, besides readability. First, it can make the compiler’s type inference task easier. The following method cannot be compiled:

void dupFirst(List<? extends Publication> collection) {
  if (!collection.isEmpty())
    collection.add(0, collection.get(0));

The value returned by collection.get(0) has a type that is obviously compatible with the list, but the compiler loses track of this imformation and rejects the call to add. Instead, the method needs to name the type, and be written as:

<A extends Publication> void dupFirst(List<A> collection) {
  if (!collection.isEmpty())
    collection.add(0, collection.get(0));
}

Although it is not a very common case, another benefit is that a named type can have multiple bounds. For instance, a method that stores a list of publications across a network could require publications to be serializable:

<A extends Publication & Serializable>
  void storePublications(List<A> collection) {...}

The syntax <? extends T & U> is not possible. Naming also enables more complex types, as in this method, which requires publications to be ordered:

<A extends Publication & Comparable<A>>
  void printTitlesInOrder(List<A> collection) {...}

On the flip size, upper type bounds only can be named in Java, not lower type bounds. In other words, these are possible:

• <? extends U>
• <? super T>
• <T extends U>

but there is no <U super T> syntax.

The case of arrays

In Java, Book[] is a subtype of Publication[]. More generally, if T is a subtype of U, T[] is a subtype of U[]. This is an early design decision of Java that allowed writing general sorting or searching methods with an Object[] signature and call them on String[] or Book[].

Accordingly, this method:

void printTitlesAndReplaceFirst(Publication[] collection) {
  for (Publication p : collection)
    System.out.println(p.title());
  collection[0] = new Magazine(...);
}

can be called on a value of type Book[]. The last line of the method, which would need to store a magazine in an array of books, will throw an ArrayStoreException at runtime.

Covariance and contravariance

Arrays in Java are said to be covariant: if T is a subtype of U, T[] is a subtype of U[]. In Java, arrays are the only covariant types, but that is not the case in other languages. In Scala, for instance, List is covariant and List[Book] is a subtype of List[Publication] (Scala lists are immutable, and there is no danger of adding a magazine to a list of books). Other languages, like C# and Kotlin, have covariant types.

Contravariance is symmetrical: If, when T is a subtype of U, X[T] is a supertype of X[U], X is said to be contravariant. As an example, consider a type Consumer[T] that can “consume” a value of type T. Clearly, a Consumer[Publication] can consume a book (since it can consume a publication), and therefore Consumer[Publication] should be a subtype of Consumer[Book].

Basically, types that lets values out can be made covariant, while types that take values in can be made contravariant (in and out are the keywords used in C# and Kotlin to define contravariant and covariant types). Types that need both usually cannot be covariant or contravariant; they have to remain invariant (or non-variant), like the collections in Java. For instance, arrays in Scala are non-variant, and there is not relationship between Array[Book] and Array[Publication]. (Arrays are also non-variant in Kotlin, but they are covariant in C#, with a potential ArrayTypeMismatchException.) Types that are parametrized by multiple types can mix covariance and contravariance. For instance, in Scala, functions are covariant in their output type and contravariant in their input type.

Usage

When designing reusable library code, consider using type bounds for flexibility. For instance, a Java method that takes a list of tasks (specified as instances of Callable) and produces a list of results, possibly executing the tasks in parallel on a thread pool, could have the signature:

<A> List<A> execute(List<Callable<A>> tasks) {...}

However, a user with lists of book-retrieving and magazine-retrieving tasks will not be able to use this method to produce lists of publications. A more user-friendly method could use type bounds in its signature:

<A> List<A> execute(List<? extends Callable<? extends A>> tasks) {...}

This method can be used on a List<BookTask> where BookTask is a subtype of Callable<Book> and produce a List<Publication>.

If, instead of Java, you are using a language that supports covariant and contravariant types, you can leverage them instead. For instance, using Unit => A functions for tasks, a flexible execute method in Scala can be as simple as:

def execute[A](tasks: List[Unit => A]): List[A] = ...

This is as flexible as the Java method with type bounds because, in Scala, List is covariant and functions are covariant in their return type.

Conclusion

<? extends T>, <T extends U> and <? super T> are used to specify type bounds, a mechanism by which code can be parametrized by a type while keeping constraints on what this type can be. Their use is often necessary in Java because the language has no support for type variance. Other, more modern languages offer additional features, like variance annotations or combined lower/upper bounds.