Last week, I found out about a non-obvious pitfall of the Java language caused by the interaction of sub-classing and arrays. In short, Java arrays are covariant, so what I thought was illegal code compiles, and causes an exception at runtime. In this post, I give a quick intro to type variance, and describe the particular issue I encountered recently.
To start off, type variance is a way of describing what you can do with a type: whether you can use a more general (a superclass), or more specific (a subclass) type in place of it. Variance comes in three flavours: covariant, contravariant, and invariant.
A type is covariant if a more general type can be used in its place. For instance, function returns are covariant; so, if a function returns a Cat
, you can use it as an Animal
. More generally, if you have a particular object, you can use it whenever a superclass of it is required.
A type is contravariant if a more specific type can be used in its place. For instance, function arguments are contravariant; so, if a function is expecting an Animal
argument, you can give it a Cat
instead.
Finally, a type is invariant if nothing else can be used in its place.
Now, back to Java: arrays types are covariant, so the following will compile just fine:
public class Variance {
static class Animal { }
static class Dog extends Animal { }
static class Cat extends Animal { }
public static void main(String args[]) {
Animal[] zoo = new Dog[10];
zoo[0] = new Cat();
}
}
Note that we’re casting a value of a specific type, Dog[]
, to a more general type, Animal[]
. In other words, we’re using a more general type in place of a specific type, so the type is covariant.
Unfortunately, that means we’ve created a hidden requirement that elements of the zoo
array must be of type Dog
or a subclass of Dog
. So, the final line fails at runtime with an ArrayStoreException
. Ultimately, the problem is that every individual line in the above program makes sense from a typing standpoint, but when taken together, they no longer make sense.
Other languages such as C#, and C++, also have this issue.
As far as I can tell, the best solution right now is to use templates in C++, and generics in Java. Both of these make the types invariant, and a program equivalent to the above would cause a compile-time exception.
More modern languages have taken a more flexible approach to the issue: Scala takes a page out of OCaml’s book, and has variance annotations; these are a way of relaxing the invariance in certain cases where we know it won’t cause problems. C# 4.0 also seems to have taken this route (but I don’t know enough about the language to judge).