Java Recursive Generics

From time to time I like to take a look at Java JDK source code to learn more about how the contributors think about various topics. While I was looking into how enum is implemented, I noticed something very familiar in the declaration of Enum class, the class which is responsible with enum implementation in Java language.

public abstract class Enum<E extends Enum<E>>
        implements Constable, Comparable<E>, Serializable {
...
}

At the first glance one might notice nothing unusual. At a second look one can see that E is a generic parameter which extends Enum<E>, and feels like mind bending or insane. However I used it in the past, in my personal projects, without knowing it has a name: recursive generics. In this story I will present you what this construct is.

A standard example

We will illustrate a situation very similar with the enum construct. Suppose that we have a base class for numbers and we want to have positive integers and real numbers specializations. Additionally, we want to compare positive integers only with positive integers, and real numbers only with real numbers. A standard way to write those classes is the following:

abstract class Number implements Comparable<Number> {
}
class PositiveInteger extends Number {
    private final int value;
    public PositiveInteger(int value) {
        if (value < 0) {
            throw new IllegalArgumentException();
        }
        this.value = value;
    }
    int getValue() {
        return value;
    }
    @Override
    public int compareTo(Number o) {
        if (o instanceof PositiveInteger pos) {
            return Integer.compare(value, pos.value);
        }
        throw new IllegalArgumentException();
    }
}
class Real extends Number {
    private final double value;
    public Real(double value) {
        this.value = value;
    }
    public double getValue() {
        return value;
    }
    @Override
    public int compareTo(Number o) {
        if (o instanceof Real r) {
            return Double.compare(value, r.value);
        }
        throw new IllegalArgumentException();
    }
}

Then calls like this will succed

var n1 = new PositiveInteger(1);
var n2 = new PositiveInteger(2);
System.out.println(n1.compareTo(n2));

And comparison between two different specialized classes will fail with exception at runtime.

var n1 = new PositiveInteger(1);
var n2 = new Real(2);
System.out.println(n1.compareTo(n2));

When we declared in the abstract class the requirement to implement the comparator, the base class has no way to tell that we want a specialization comparison. Thus we have to treat the situation with instanceof and throw exceptions if needed.

The question is if it could be done in a better way. Of course, the recursive generics is the answer, otherwise I would not write this story. We go abruptly into the new code.

abstract class Number<N extends Number<N>> implements Comparable<N> {
}
class PositiveInteger extends Number<PositiveInteger> {
    private final int value;
    public PositiveInteger(int value) {
        if (value < 0) {
            throw new IllegalArgumentException();
        }
        this.value = value;
    }
    int getValue() {
        return value;
    }
    @Override
    public int compareTo(PositiveInteger o) {
        return Integer.compare(value, o.value);
    }
}
class Real extends Number<Real> {
    private final double value;
    public Real(double value) {
        this.value = value;
    }
    public double getValue() {
        return value;
    }
    @Override
    public int compareTo(Real o) {
        return Double.compare(value, o.value);
    }
}

What happens? In the declaration of Number we introduced a new generic type N and we use this new type to give additional directive to Comparator contract.

Who is N? Well, N is a generic type which inherits from Number, but because Number has a generic type, we have to add to it a generic type parameter. Why the same type N? Simply because N is the generic type which inherits from Number. It looks like a circular argument, but it works.

What we achieved? We have told to the class Number that the inheritors will have to implement a Comparable interface with their own derived types (to not use the base type). In other words, in the base class we described a behavior that the inheritors will have to have, and we described that behavior in terms of their own types.

Now the implementation is simplified. But we achieve more with that. We also allow the compiler to help us and to not allow other implementations. A code like the one below will not even compile.

var n1 = new PositiveInteger(1);
var n2 = new Real(2);
System.out.println(n1.compareTo(n2)); // <- this will not compile

Back to Java enum implementation

I prepared that artificial example for illustration purposes. The main reason was to explain what happens with enum implementation in Java. Behind the keyword enum is that class which also uses recursive generics. The reasoning should be clear now. They used this type of description to allow each enumeration class to perform comparisons only between elements of the same concrete enumeration class. It makes sense to be like that, in the end it is completely illogical to allow comparisons between elements of different types.

When you create an enum basically, under the hood, you inherit this class. The recursive generics are used here only to limit the behavior of comparator (and not only). We can think of this usage as a bound on allowed types.

Fluent API

Another usage of recursive generics is fluent API. This is often seen in builder patterns, but it is not restricted to it. A fluent API is a way to chain methods which returns a pointer to this. Let’s look at some form of builder.

class Person {
    
    private String name;
    private int age;
    
    public Person withName(String name) {
        this.name = name;
        return this;
    }
    
    public Person withAge(int age) {
        this.age = age;
        return this;
    }
}

This allows initialization code like:

new Person().withName("John").withAge(20);

What happens if we have an inheritance chain?

class Cyclist extends Person {
    private String bikeName;
    
    public Cyclist withBikeName(String bikeName) {
        this.bikeName = bikeName;
        return this;
    }
}

This becomes problematic. Chaining methods from both classes is not possible. Once you call a method from Person you will not see methods from Cyclist. Even if one can manage to chain all calls using a proper ordering of method calls, the resulting object must be cast back to derived class.

Again, recursive patterns helps here.

class Person<T extends Person<T>> {
    private String name;
    private int age;
    public T withName(String name) {
        this.name = name;
        return (T) this;
    }
    public T withAge(int age) {
        this.age = age;
        return (T) this;
    }
}
class Cyclist extends Person<Cyclist> {
    private String bikeName;
    public Cyclist withBikeName(String bikeName) {
        this.bikeName = bikeName;
        return this;
    }
}

You can notice the cast to generic parameter. This is safe since we know that this pointer is a derived class by construction.

An example from my pet project

Perhaps there are different use cases for generic types I am not aware of. In fact I was not aware that this construct had a name before reading about enum implementation, but I recognized the pattern immediately because I have used it before. I will give here two examples from my pet statistics and machine learning library I contribute to when I want to learn more about various data related topics rapaio.

public abstract class ParamSet<T extends ParamSet<T>> implements Serializable {
...
}
public abstract class ClassifierModel<M extends ClassifierModel<M, R, H>, R extends ClassifierResult, H extends RunInfo<M>>
        extends ParamSet<M> implements Printable, Serializable {
...
}
public class NaiveBayes extends ClassifierModel<NaiveBayes, ClassifierResult, RunInfo<NaiveBayes>> implements Printable {
...
}

The sample code above describes the class declaration for some ML model classifier and the abstract class every classifier model should implement. It might look ugly at first sight, but it does have a straightforward semantic.

Every classifier model is configured by a custom set of parameters specific for each type. The parameter management is implemented in a base class called ParamSet, which you can see it uses the recursive generic construct in order to allow fluent API. The classifier model abstract class provides some general parameters for all classifiers and also some generic behaviors. Those are further propagated through recursive generics to it’s final implementations, in this case the NaiveBayes class.

The classifier model abstract class has also additional generic types. Those types are the class which contains results of the classification prediction and a class which provides information for each iteration (if the classifier is iterative). Those two components reuses also the recursive generic types to allow full access to implementation methods.

In contrast with the complexity of the type declarations, the usage becomes elegant and simple.

Frame train = null;
Frame test = null;
CForest cf = CForest.newModel()
        .runs.set(10) // parameter for all classifiers
        .baggingMode.set(BaggingMode.SOFT_VOTE) // parameter specific to CForest
        .rowSampler.set(RowSampler.bootstrap(0.8)); // parameter for all classifiers
var result = cf.fit(train, "y").predict(test);
result.printSummary();

Final thoughts

I think that every one who is serious about its work has his own share of rediscoveries. It would be great if from time to time those would be real discoveries, but even if not, there are some great things about re-inventing the wheel. It is a great feeling that you do something which resonates with the work of other minds, most of the time greater minds than yours. This is reassuring in the sense that it gives you a confidence boost.

Additionally, rediscovering things allows one to have a deeper understanding compared to the direct contact through learning from external sources. This is because when you learn from somebody, you also take with you some perspectives which helps on short term, but can limit yourself because those perspective are too tightly connected with what you learn and often times it remains the only perspectives available to you.


Posted

in

by

Tags:

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *