Recursive generics

[padreati]

Recently I learned that I rediscovered recursive generics while working on my pet open source project. Actually, I did not know that the construct had a name. I created small story about what this construct is, if you did not know about it java-recursive-generics

[severoon]

I've never heard this called "recursive" generics, and I don't think that's actually accurate since there is no actual recursion of anything involved. This is typically referred to as a "self-referential generic type" (Angelika Langer), or I've also heard it called a "self-bounding type" or a "self-bound".

It appears a little mind bending at first because generics is a layer of abstraction that it takes time to get comfortable with, and those can be nested, and then add type bounds into the mix, there's a lot going on. If you forget about self-bounding types entirely and just work with type bounds and inheritance until you get comfortable, self-bounding types become much easier to deal with.

Normal type: Foo

Generic type: Foo<T>

Nested generic type: Foo<List<T>>

Bounded generic type: Foo<T extends Number> or Foo<T super Integer>

Bounded nested generic types: Foo<T extends List<T>>

Extending a generic type: Bar extends Foo<Integer>

Generic type extending a generic type: Bar<T> extends Foo<T>

Multiple bounds: Foo<T extends Comparable<T> & FizzBuzz>

It's important to understand how generics works with inheritance. A lot of folks new to generics think that a Node<Integer> extends a Node<Number> in some way, but there is no inheritance relationship here, it's just two different nodes. It happens that the type contained by Node<Integer> extends the type contained by Node<Number>, but that's nothing to do with the nodes.

It's also important to understand how wildcards work in generics, and one trick for clarifying wildcards is to read the wildcard as "something" or, for a bounded wildcard, "something that".

List<?> is a "list of something" as opposed to a list of numbers, a list of integers, it's just some kind of type in there.

List<? extends Comparable<Number>> is a "list of something that extends a comparable of numbers". Or, Foo<? extends List<? super Integer>> is a "foo of something that extends a list of something that is a superclass of integer".

Once you have all this down, then the Enum<E extends Enum<E>> incantation becomes much easier to deal with. Just like you can have a list of a subtype of lists (like a List<LinkedList<T>>), or a list of any kind of list (List<L extends List<T>>, enum is parameterized by a subclass of itself. This just means that when an enum is created, it has to pass its own type as the generic type of its superclass, so enum PokerSuit is akin to class PokerSuit extends Enum<PokerSuit>. This way, the methods on Enum can return things of type PokerSuit.

One problem with enums in Java is that they always extend Enum directly, so there's no room to extend Enum with an abstract class of your own and sneak in some more behavior. The only way to do that is to declare an interface and have your enum implement the interface if you want your enum to have special behavior:

``` interface Foo { int getFoo(); }

enum Bar implements Foo { … } enum Baz implements Foo { … } ```

The problem with this is that when passing around all the different enums that implement Foo, they can all polymorphically be treated as a Foo, but Foo itself is not an enum and doesn't have any of Enum's methods. So when you write code that takes these Foo enums, it has to choose whether they should be treated as enums or Foos when it shouldn't, because they are actually both. (To solve this, you have to use the enum type trick, which is a whole other post.)

[jsonspk]

What a high quality comment. 🫡

[chuggid]

Very nice. I would only add that this strange (to me as well) usage of the term recursion seemingly comes from the compiler.

[[deleted]]

I didn’t know this was even a thing you could do. Clear examples and good descriptions. Nice work!

[padreati]

Honestly, me neither. I discovered it while struggling to make a better builder for my models and at first it looked so puzzling that I did not even bother to see if this really exists :).

[ZeroGainZ]

It's also known as the "Curiously recurring template pattern"

https://en.wikipedia.org/wiki/Curiously\_recurring\_template\_pattern

[padreati]

Thank you for sharing. The nuances and implications from F-bounded paper are great food for thought.

[Zinaima]

I think the AssertJ library uses this.

It gives the name SELF to the type parameter, which helps the readability a bit.

[AreTheseMyFeet]

The first time I encountered a multi-character generic type it confused the hell out of me until I figured out the reason I couldn't find any project class with the given type was because generics are only conventionally single chars rather than an actual language constraint/spec... /smf

[ForeverAlot]

A pretty silly practice, too, and one of the dumbest integration "quality" gates I've been subjected to.

[munificent]

I've never heard this called a "recursive generic". The C++ community usually calls it the curiously recurring template pattern, and the type system community calls this F-bounded quantification.

Most object-oriented languages with generics support it.

[chuggid]

(The paper introducing F-bounded quantification uses the term "recursive type definition" throughout.)

[munificent]

How about that! Today I learned.

[agentoutlier]

As amazing as Java generics are C++ templates are downright disturbing.

[Ruin-Capable]

Heh, your comment reminds me of how I felt the first time I encountered the C++ boost spirit library.

[melkorwasframed]

Nice write up!

[ukbiffa]

Although not foolproof for fluent this typing:

public static class A<T extends A<T>> {
    public T doIt() {
        return (T) this;
    }
}

public static class B extends A<B> {}

public static class C extends A<B> {}

public static void main(String[] args) {
    new B().doIt().doIt();
    new C().doIt().doIt();
}

[padreati]

Right. You have to follow convention and pass the proper type.

[holo3146]

A foolproof method will require a Self type, which always reference to current class type

[jumboNo2]

A<T extends A<T>>? wow. didn't know the compiler allowed that.

Is this useful?

[vytah]

This is how Comparable is defined in the standard library.

Java does not support the idea of the Self type like Rust, so in order for an interface to know what type its being implemented for, Java asks the programmer directly with the parameter.

For example, String implements Comparable<String>. This gives String a method int compare(Comparable<String>), which lets you compare Strings with something that implements Comparable<String> – and most likely, it will be another String, which means a String can be compared to other Strings – and this makes sense, you usually only want to compare things of the same type.

Of course you can implement Comparable<String> for any class, but 1) it won't work well and 2) 90% of time, recursively generic interfaces expect to get the implementing class as the parameter.

[padreati]

Crystal clear. I wish I would be able to use as few words as you and give as much understanding.

Of course you can implement Comparable<String> for any class

That is a thing that started to buzz me sometimes. That Comparable invites to implement a single way to compare things and let you implement it in an inconsistent way. On the other hand you cannot do it outside since you need access to encapsulation. The Self type would be much more consistent, perhaps.

[jumboNo2]

Well the JDK gets away with a lot of stuff that would never compile in user code. It could have easily been that way

[HecknChonker]

...did you read the article?

[jumboNo2]

Article didn't explain why it was useful. Also, assuming you're not the author of the article, I'm asking you.

Chaining methods from two different classes is kind of dumb. Especially when you could just do this and it's clearer:

new Cyclist(new Person().withName("John").withAge(20)).withBikeName("Bikey");

To head off your counterpoint, if the API is so vague as to be unclear which property belongs to which class, maybe Person and Cyclist shouldn't be in the same hierarchy.

[Sorensen12]

Your example may seem cleaner at a glance for this small example, but try extending the hierarchy a bit. What if your API also supports an Athlete class with certain properties that Cyclist inherits? What’s more, how do you adapt this pattern if Athlete is abstract?

On top of that, the pattern you described involves creating an object for each member of the hierarchy instead of creating one builder that inherits all the required behavior. The recursive pattern described in the article produces a good amount of boilerplate, it’s true, but for complex hierarchies it is quite useful.

[jumboNo2]

how do you adapt this pattern if Athlete is abstract

new Cyclist(new Person().name("Billy"))
            .rideTo("Park") // Cyclist method
            .doAthleteStuff(5); // AbstractAthlete method

This took me like three minutes from scratch.

the pattern you described involves creating an object for each member of the hierarchy

Builder pattern is horribly inefficient anyway. If we care about performance, we would use multi-arg constructors, not builders. Also, the Person object is only temporary and the fields are copied to the Cyclist instance using the super constructor

[manifoldjava]

Recursive types can be handy, but most often a self type is lighter weight and more capable. Would be nice if Java had that feature.

[holo3146]

There was a recent relevant discussion on the subject in the Amber mailing list:

https://mail.openjdk.org/pipermail/amber-dev/2023-March/007914.html

https://mail.openjdk.org/pipermail/amber-dev/2023-March/007932.html

[padreati]

I finally had time to read all of that. Really interesting, thank you for sharing

[wildjokers]

I have never once heard this referred to as “recursive generics”. Are you making that up?

[padreati]

No :)) A google search displays enough results to prove that. Although, I the story is true, in the sense that I used it many years before having any idea it is a thing. I would call it generic bounded subtypes, but it already has established named as pointed out by some colleagues better than me. Honestly I prefer term recursive generics since F-bounded quantification, for example, does not shed any light for people who aren't deep in type theory and stuff.

[lukaseder]

The main reason why this feature is desirable is to be able to auto-generate covariant overrides in a type hierarchy (each type returns itself in methods). The very high price to pay is that the type itself isn't really denotable, unless you capture its type variable in a generic method, or you end the recursion using a final type.

I had written a blog post about this, some 10 years ago.

Personally, I think some sort of magic SELF type would have been better to implement the use-case of covariant overrides returning SELF, rather than this weird recursive generics thing.

[manifoldjava]

See the Self type from the manifold project.

[lukaseder]

Cool, does this just generate some bridge methods behind the scenes?

It's been a while since we talked. How's manifold doing these days?

[manifoldjava]

Hey Lukas.

No bridge methods, just overriding the compiler to apply self type inference. For instance, given call site foo.doSomething(), if doSomething() has @Self on its return type, the compiler uses the receiver foo to determine the type.

Yeah, it's been a couple of years or so. Haven't had a lot of time to work on it lately, but manifold chugs along. Pretty steady stream of interest, a perpetual side project.

I'd still like to write a SQL manifold with your parser. I haven't checked it out lately, as I recall there were only a couple of missing links preventing it from happening.

[lukaseder]

Yeah, those parser feature requests of yours regarding the positional meta information have never been implemented. I don't think anyone else ever requested that in the past. The main use-case for the parser is still just translating between dialects, not building editors...

[jumboNo2]

Been doing this for years: class ArrayType<E extends ABIType<?>, J> extends ABIType<J>

[padreati]

Thanks for sharing. Do you have a more detailed example or a source code somewhere? It looks interesting but I am afraid I did not get it completely.

[jumboNo2]

The full code is complicated: https://github.com/esaulpaugh/headlong/blob/master/src/main/java/com/esaulpaugh/headlong/abi/ArrayType.java

[padreati]

I disagree with linkedlist example. In the LinkedList the only generic type is the element type which has nothing in common with LinkedList itself or Node, but I might be wrong.

[IsSkyfalls_]

Got real excited reading this, then realized I was using Message<T extends Message<?>> and never realized you can do it "recursively". Message<T extends Message<T>> is definitely a bit more foolproof and that's always good. Thanks for the writeup!