Generics: The Importance of Wildcards

or "Why type erasure is not such a bad thing" or "Why generics in C# are not that good"

Last Friday, I read an article that has been on my to do list way too long: Adding Wildcards to the Java Programming Language. I've seen wildcards in Java; I've used wildcards in Java; and I've even read the Java Language Specification on wildcards, but did yet not get the essence of wildcards.

This paper makes the need for wildcards very clear and explains why the work on wildcards and parameterized types is novel. Unfortunately, generics are often ridiculed by functional programmers. They claim that their type systems have been more expressive for decades. Fortunately, this paper clearly explains the issues of introducing generics in an object oriented setting.

The problem with basic parameterized types is subtyping. For example, although Integer is a subclass of Number, a List<Integer> is not a subtype of a List<Number>. Hence, if a method requires a List<Number> as an argument, then you cannot pass a list of List<Integer> to it.

Why is a List<Integer> not a subclass of List<Number>? Well, this is related to covariance and contravariance. A type declaration is covariant if it allowed to be more specific. For example, return types are covariant. A method that is declared to return a Number can be overridden to be more specific and return an Integer. On the other hand, parameter types are contravariant: a method that is declared to accept a Integer argument can be implemented in a more general way by allowing all Numbers.

The problem with type parameters is that they are used in method parameters as well as return types. Hence, they are restricted to the intersection of covariance and contravariance: invariance. Thus, type parameters are invariant and a List<Integer> is not a subclass of List<Number>.

If Java would be restricted to basic parameterized types and methods, then it is quite difficult to come up with a good signature for a method that works on a List that contains any Number. In fact, you cannot even declare the type of lists with abitrary numbers! Allowing arbitrary numbers a generic method with a dummy type parameter for the 'real' Number, i.e.

      <T> void doSomething(List<T extends Number>) { ... }

This works, but it gets quite mind-boggling if the types get more complex ("The more interesting your types get, the less fun it is to write them down!" -- Benjamin C. Pierce). These types are not only hard to write down: it does not even work in all cases. For example, you cannot declare a field that contains arbitrary Numbers, since you cannot introduce a dummy type variable for a field.

Wildcards are a language feature that make it a bit more fun to write down these types. Actually, it is a language feature that is necessary to write down these types, since the dummy type variable is just a workaround and uses the type of the method to declare the type of the argument. The field example shows that you cannot write down the type itself. Wildcards are based on the notion of use-site variance. Using wildcards, you can declare that your list is covariant: List<? extends Number> or contravariant: List<? super Number>. For more details, read the paper!

Unfortunately, C# will not support wildcards or a similar mechanism. The implementation strategy does not allow the introduction of wildcards (generics are implemented in the runtime instead of by type erasure). This is a bit surprising, since the implementation strategy is often claimed to be superior. What disappoints me is that the designers of C# are not willing to admit that subtyping is an issue and that wildcards are a solution. See the weblog of Eric Gunnerson: Puzzling through Erasure II and the section on wildcards in JavaOne: Day One.