About Lukas Eder

Lukas is a Java and SQL enthusiast developer. He created the Data Geekery GmbH. He is the creator of jOOQ, a comprehensive SQL library for Java, and he is blogging mostly about these three topics: Java, SQL and jOOQ.

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.

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.
 

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you two of our best selling eBooks for FREE!

JPA Mini Book

Learn how to leverage the power of JPA in order to create robust and flexible Java applications. With this Mini Book, you will get introduced to JPA and smoothly transition to more advanced concepts.

JVM Troubleshooting Guide

The Java virtual machine is really the foundation of any Java EE platform. Learn how to master it with this advanced guide!

Given email address is already subscribed, thank you!
Oops. Something went wrong. Please try again later.
Please provide a valid email address.
Thank you, your sign-up request was successful! Please check your e-mail inbox.
Please complete the CAPTCHA.
Please fill in the required fields.

Leave a Reply


5 − five =



Java Code Geeks and all content copyright © 2010-2014, Exelixis Media Ltd | Terms of Use | Privacy Policy | Contact
All trademarks and registered trademarks appearing on Java Code Geeks are the property of their respective owners.
Java is a trademark or registered trademark of Oracle Corporation in the United States and other countries.
Java Code Geeks is not connected to Oracle Corporation and is not sponsored by Oracle Corporation.
Do you want to know how to develop your skillset and become a ...
Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you two of our best selling eBooks for FREE!

Get ready to Rock!
You can download the complementary eBooks using the links below:
Close