The Dangers of Correlating Subtype Polymorphism with Generic Polymorphism


Java 5 has introduced generic polymorphism to the Java ecosystem. This has been a great addition to the Java language, even if we’re all aware of the numerous caveats due to generic type erasure and the consequences thereof. Generic polymorphism (also known as parametric polymorphism) is usually maintained orthogonally to possibly pre-existing subtype polymorphism. A simple example for this is the collections API

List<? extends Number> c = new ArrayList<Integer>();

In the above example, the subtype ArrayList is assigned to a variable of the super type List. At the same time ArrayList is parameterised with the type Integer, which can be assigned to the compatible parameter supertype ? extends Number. This usage of subtype polymorphism in the context of generic polymorphism is also called covariance, although covariance can also be achieved in non-generic contexts, of course.

Covariance with Generic Polymorphism

Covariance is important with generics. It allows for creating complex type systems. Easy examples involve using covariance with generic methods:

<E extends Serializable> void serialize(
    Collection<E> collection) {}

The above example accepts any Collection type, which can be subtyped at the call-site with types such as List, ArrayList, Set, and many more. At the same time, the generic type argument at the call site is only required to be a subtype of Serializable. I.e. it could be a List<Integer> or an ArrayList<String>, etc.

Correlating Subtype Polymorphism with Generic Polymorphism

People are then often lured into correlating the two orthogonal types of polymorphism. A simple example of such a correlation would be to specialise an IntegerList or StringSet as such:

class IntegerList extends ArrayList<Integer> {}
class StringSet extends HashSet<String> {}

It is easy to see that the number of explicit types will explode, if you start to span the cartesian product of the subtype and generic type hierarchies, wanting to specialise more precisely by creating things like IntegerArrayList, IntegerAbstractList, IntegerLinkedList etc.

Making the Correlation Generic

As seen above, such correlations will often remove the genericity from the type hierarchy, although they are not required to do so. This can be seen in the following, more general example:

// AnyContainer can contain AnyObject
class AnyContainer<E extends AnyObject> {}
class AnyObject {}

// PhysicalContainer contains only PhysicalObjects
class PhysicalContainer<E extends PhysicalObject>
  extends AnyContainer<E> {}
class PhysicalObject extends AnyObject {}

// FruitContainer contains only Fruit,
// which in turn are PhysicalObjects
class FruitContainer<E extends Fruit>
  extends PhysicalContainer<E> {}
class Fruit extends PhysicalObject {}

The above example is a typical one, where the API designer was lured into correlating subtype polymorphism (Fruit extends PhysicalObject extends AnyObject) with generic polymorphism (<E>), while keeping it generic, allowing to add further subtypes below FruitContainer. This gets more interesting when AnyObject should know its own subtype, generically. This can be achieved with a recursive generic parameter. Let’s fix the previous example

// AnyContainer can contain AnyObject
class AnyContainer<E extends AnyObject<E>> {}
class AnyObject<O extends AnyObject<O>> {}

// PhysicalContainer contains only PhysicalObjects
class PhysicalContainer<E extends PhysicalObject<E>>
  extends AnyContainer<E> {}
class PhysicalObject<O extends PhysicalObject<O>>
  extends AnyObject<O> {}

// FruitContainer contains only Fruit,
// which in turn are PhysicalObjects
class FruitContainer<E extends Fruit<E>>
  extends PhysicalContainer<E> {}
class Fruit<O extends Fruit<O>>
  extends PhysicalObject<O> {}

The interesting part here are no longer the containers, but the AnyObject type hierarchy, which correlates subtype polymorphism with generic polymorphism on its own type! This is also done with java.lang.Enum:

public class Enum<E extends Enum<E>>
implements Comparable<E> {
  public final int compareTo(E other) { ... }
  public final Class<E> getDeclaringClass() { ... }
}

enum MyEnum {}

// Which is syntactic sugar for:
final class MyEnum extends Enum<MyEnum> {}

Where Lies the Danger?

The subtle difference between enums and our custom AnyObject hierarchy is the fact that MyEnum terminates recursive self-correlation of the two orthogonal typing techniques by being final! AnyObject subtypes, on the other hand should not be allowed to remove the generic type parameter, unless they are made final as well. An example:

// "Dangerous"
class Apple extends Fruit<Apple> {}

// "Safe"
final class Apple extends Fruit<Apple> {}

Why is final so important, or in other words, why must AnyObject subtypes be careful when terminating recursive self-correlation, such as Apple did, before? It’s simple. Let’s assume the following addition:

class AnyObject<O extends AnyObject<O>>
  implements Comparable<O> {

  @Override
  public int compareTo(O other) { ... }
  public AnyContainer<O> container() { ... }
}

The above contract on AnyObject.compareTo() implies that any subtype of AnyObject can only ever be compared to the the same subtype. The following is not possible:

Fruit<?> fruit = // ...
Vegetable<?> vegetable = // ...

// Compilation error!
fruit.compareTo(vegetable);

The only currently comparable type in the hierarchy is Apple:

Apple a1 = new Apple();
Apple a2 = new Apple();

a1.compareTo(a2);

But what if we wanted to add GoldenDelicious and Gala apples?

class GoldenDelicious extends Apple {}
class Gala extends Apple {}

We can now compare them!

GoldenDelicious g1 = new GoldenDelicious();
Gala g2 = new Gala();

g1.compareTo(g2);

This was not the intention of the author of AnyObject!

The same applies to the container() method. Subtypes are allowed to covariantly specialise the AnyContainer type, which is fine:

class Fruit<O extends Fruit<O>>
  extends PhysicalObject<O> {

  @Override
  public FruitContainer<O> container() { ... }
}

But what happens to the container() method in GoldenDelicious and Gala?

GoldenDelicious g = new GoldenDelicious();
FruitContainer<Apple> c = g.container();

Yes, it will return an Apple container, not a GoldenDelicious container as intended by the AnyObject designer.

Conclusion

Subtype polymorphism and generic polymorphism span orthogonal type axes. Making them correlate can be a design smell in your type system. Making them correlate on the same type is dangerous, as it is hard to get right. Users will try to terminate the recursive generic type definition on a subtype of your base type. The reason for this termination is the fact that base types with recursive self-bounds are hard to use. But the termination often goes wrong, as it should only be done on final classes, not regular classes or interfaces.

In other words, if you think you need a recursive generic type definition on a common base type, think again very carefully, if you really need it and if your type users can correctly terminate the recursive generic type definition in a final class.

Tags: , , , , , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,745 other followers

%d bloggers like this: