Cam's Cyberspace

Recent Notes

Recursive Generic Bounds and Self Types

Properties3
descriptionWhy Comparable shows up as a bound on its own type parameter, what that recursion actually promises, and the self type it can only imitate.
tagscs, languages, type-theory
aliases

7 min read

The first time you write a generic method that has to compare two things, the bound writes itself into a small circle. You need T to be comparable, so you bound it by Comparable. Then the compiler asks what Comparable is parameterized on, and the only sensible answer is T, the thing you were in the middle of declaring. The declaration turns back on itself and you get <T extends Comparable<T>>.

The idea

A recursive bound does not say “T is the class that implements this interface.” It says “T can be compared to T,” which is a claim about a relationship between two type arguments, and nothing more. Java has no way to write “the type of this,” so the recursive bound is the closest available approximation, and the distance between the approximation and the real thing is not academic. It shows up as a class that satisfies the bound while lying about which type it is, and as a JDK that could not use the textbook form of the idiom in its own library.

How the circle gets there

The Java Tutorials build the idiom from a failure. Start with a method that counts array elements greater than some element, and the obvious body does not compile, because the greater-than operator “applies only to primitive types such as short,” int, double, and the rest of the primitives. Objects have no >. The fix is a bound: “To fix the problem, use a type parameter bounded by the” Comparable<T> interface, whose entire content is one method, int compareTo(T o). The repaired signature is

public static <T extends Comparable<T>> int countGreaterThan(T[] anArray, T elem) {
    int count = 0;
    for (T e : anArray)
        if (e.compareTo(elem) > 0)
            ++count;
    return count;
}

and the tutorial is blunt about why this matters: “Bounded type parameters are key to the implementation of generic algorithms.”

The shape has a name in type theory. When a type variable appears inside its own bound, the bound is a function of the variable it constrains, and the quantification is called f-bounded. The mechanical consequence inside the method body is small and specific. T now has a compareTo that accepts a T, so e.compareTo(elem) type-checks with no cast, and the argument type lines up with the element type instead of degrading to Object. Bounded Type Parameters covers the rest of what a bound buys, including the fact that the leftmost bound is what the parameter erases to.

What the bound actually promises

Read T extends Comparable<T> as a constraint solver would. It admits any type argument X for which X is a subtype of Comparable<X>. That is the whole check. Comparable itself is declared with an unconstrained parameter, public interface Comparable<T>, so the interface places no restriction at all on what you compare against. The doc describes the intent, that the interface “imposes a total ordering on the objects of each class that implements it,” and the payoff, that “Objects that implement this interface can be used as keys in a sorted map or as elements in a sorted set” without an explicit comparator. But intent is not enforcement.

class Sneaky implements Comparable<String> compiles. So does class Backwards implements Comparable<Object>. Neither is what anyone meant, and the type system has no opinion. The gap is visible in compareTo’s own contract, which reserves a runtime exception for exactly this situation: ClassCastException - if the specified object's type prevents it from being compared to this object. A statically enforced self type would make that exception unreachable. It is in the API because the bound cannot rule the case out.

The JDK could not use the textbook form

The clean demonstration is in java.util.Collections. The naive signature for a natural-ordering sort would be <T extends Comparable<T>>. What ships is wider, and the maximum-finder is stranger still:

public static <T extends Comparable<? super T>> void sort(List<T> list)
public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)

Two deviations from the textbook form, one cause each.

The ? super T is about inheritance. Say Employee implements Comparable<Employee> and Manager extends Employee. Manager inherits compareTo(Employee), so Manager is a Comparable<Employee>, and it is emphatically not a Comparable<Manager>. Under the strict recursive bound, a List<Manager> is unsortable, which would be an absurd thing for a collections library to say. Widening to Comparable<? super T> accepts any ancestor as the comparison type and the hierarchy sorts. The leading Object & in max is doing a different job, one about erasure rather than type-checking, since it changes which bound sits leftmost; Generics and Type Erasure in Java carries the leftmost-bound rule and its citation.

Reading the bound against a two-level hierarchy

Collections.max documents what it needs at runtime: “All elements in the collection must implement the Comparable interface.” and “Furthermore, all elements in the collection must be mutually comparable”. Mutual comparability is the property the recursive bound is groping toward and never quite reaches. The static bound checks one type against one bound; mutual comparability is a property of a whole collection, which is why the method still documents ClassCastException - if the collection contains elements that are not mutually comparable (for example, strings and integers). The bound narrows the failure surface. It does not close it.

The self type it imitates

The same recursion is the standard workaround whenever a superclass method needs to return the subtype. A builder is the usual case:

abstract class Builder<T extends Builder<T>> {
    abstract T self();
    T name(String n) { this.n = n; return self(); }
}
 
class HttpBuilder extends Builder<HttpBuilder> {
    HttpBuilder self() { return this; }
}

Chaining new HttpBuilder().name("x").timeout(5) now type-checks, because name returns HttpBuilder rather than Builder. The same trick makes an abstract copy() or a fluent withX return something usable. This is the curiously recurring generic pattern, and every one of these declarations is a workaround for the same missing feature: Java has no this type, no way to write “whatever class this method was invoked on.”

Nothing binds T to the implementing class

class Impostor extends Builder<HttpBuilder> compiles. HttpBuilder satisfies HttpBuilder extends Builder<HttpBuilder>, the bound is discharged, and Impostor now inherits a name method that returns an HttpBuilder which is not this and never was. The self() implementation can return any HttpBuilder it likes. The pattern is a convention held in place by author discipline and code review, not by the compiler. Its guarantee is one step weaker than it looks in every use, and the boilerplate cost is real: every leaf class in the hierarchy has to name itself in its own extends clause, and an intermediate abstract class has to stay generic to keep the chain open.

The practical reading is to reach for the recursive bound when the alternative is casting, keep the bound as wide as the use permits, and treat any signature you publish for others as needing the ? super T relaxation the JDK learned to write. The strict form is a promise about a single class. Real hierarchies are not single classes.

Sources

Graph View

Backlinks