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.
 

Related Whitepaper:

Bulletproof Java Code: A Practical Strategy for Developing Functional, Reliable, and Secure Java Code

Use Java? If you do, you know that Java software can be used to drive application logic of Web services or Web applications. Perhaps you use it for desktop applications? Or, embedded devices? Whatever your use of Java code, functional errors are the enemy!

To combat this enemy, your team might already perform functional testing. Even so, you're taking significant risks if you have not yet implemented a comprehensive team-wide quality management strategy. Such a strategy alleviates reliability, security, and performance problems to ensure that your code is free of functionality errors.Read this article to learn about this simple four-step strategy that is proven to make Java code more reliable, more secure, and easier to maintain.

Get it Now!  

Leave a Reply


5 × = thirty



Java Code Geeks and all content copyright © 2010-2014, Exelixis Media Ltd | Terms of Use
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.

Sign up for our Newsletter

15,153 insiders are already enjoying weekly updates and complimentary whitepapers! Join them now to gain exclusive access to the latest news in the Java world, as well as insights about Android, Scala, Groovy and other related technologies.

As an extra bonus, by joining you will get our brand new e-books, published by Java Code Geeks and their JCG partners for your reading pleasure! Enter your info and stay on top of things,

  • Fresh trends
  • Cases and examples
  • Research and insights
  • Two complimentary e-books