Monday, August 9, 2010

How I Understand Generics.

I have come to realize that my understanding of generics is likely more limiting than I'd care to admit. No better way to address this concern than to try and lay it out.

To start, I must fall back to what I understand of types in Java. Before generics, to define a new type was to define a new class. So, if you had a class:



public class List {
public Object get(int index) {...}
public void add(Object o) {...}
}


Then you have declared a type that is very understandable (helped by virtue of being familiar). Now, generics often start by showing casting happening at the use site of this class. However, I feel it is more revealing to think of another type that is similar to the above definition. Consider:



public class StringList {
public String get(int index) {...}
public void add(String o) {...}
}


Now, this is a new type. Further, it is completely unrelated to the previous type, except for the fact that it looks an awful lot like it.

Now, most people will start with the other types that happen to be named in these and try to build a relationship from that. Such that because people see that String extends Object, so StringList must extend ObjectList. But remember, we aren't talking about the types String and Object, we are looking at StringList and plain List. As defined here, this can not happen. Were one to try this, you would find that, were you to drop the set method, suddenly you could make these types related. As such:


public class List {
public Object get(int index) {...}
}

public class StringList extends List {
public String get(int index) {...}
}


Similarly, were one to drop the get methods, the relationship could actually be written the other way, such that List would actually extend StringList:



public class StringList {
public void add(String o) {...}
}

public class List extends StringList {
public void add(Object o) {...}
}


(It occurred to me this morning that I should say that Java doesn't support contravariant method parameters. So... The above compiles, but only because List is defining a new add method. :) )

Using this code, you would see that nothing that is invalid to the type system would have happened, as you simply added a String to a List. Which, since List has an add method that takes an Object, and a String is an Object, we are all clear.


StringList foo = new List()
foo.add("hello");




But, what all does this have to do with generics in Java? Well, as I said at the beginning, until generics, one had to write a new class file to define a new type. With generics, one can simply describe types. Specifically, you can now define all types that share a common description. For us, this description is simply:



public class List<O> {
public void add(O o) {...}
public O get(int index) {...}
}



So, why did I go through the trouble of exploring relationships of these possible types. Well, remember in Java when you describe all possible types that share a common description, you are describing completely unrelated types (in the typically inheritance based view of relationships). This is what is referred to when it is said that generics are invariant. List<String> describes a type akin to StringList, and List<Object> describes plain old List. And, just as StringList is not a related type to List, nor is List<String> related to List<Object>.

But what if we wanted that relationship ability? That is where wildcard captures come into play. Specifically, the first relationship type can be described with the following snippet. Notice the lines that don't compile are the ones that we could not have been able to code were we writing the class file ourselves:


List<? extends Object> foo = new List<String>();
foo = new List<Integer>();
foo = new List<Double>();
Object o = foo.get(0);
foo.add(new Object()); //Fails.


Similarly, the second relationship could be encoded with the wildcard below:



List<? super String> foo = new List<String>();
foo = new List<CharSequence>();
foo = new List<Object>();
foo.add("hello");
String o = foo.get(0); //Fails



That is all well and good, but what if we wanted to describe not just all similarly described types, but also all of their subtypes as well? Since we can identify in the code what restrictions are required to say that StringList extends String (and, conversely List extends StringList), could we not write a class such that we declared the generic to account for this and have the compiler let us know if we write a method that would be incompatible with what we declared as our intention?

Unfortunately, this is not possible in Java. And it is a direct consequence of the final point on generics that one will hear about in java, that it has use site variance declarations. You can not write a class that describes all possible subtypes of the types it describes, but one can write a variable that defines an inheritance chain. And, in so doing, the compiler will remove methods that would not be possible in the inheritance chain that you declared.

No comments: