circular generics : interface IFoo >

Question

This is a well-known idiom in Java. See for instance this SO discussion. So basically to define an interface whereby classes that implement it need to have a method to compare with objects of their class you would do:

public interface IComparable<T extends IComparable<T>> {
    public int compare(T item);
}

(Note: that's apparently an unnecessarily complicated way to solve the particular use case - see this post - but I am inquiring on how to interpret the recursive syntax, never mind the particular application).

In short, this is a recursive definition with no apparent end in the recursion and I don't see how the compiler / type system pull this off.

Also, trying to put in words ("an IComparable is a class whose instances can compare with objects of a class that implements the IComparable interface") yields an illogical circular definition that can't be had in Philosophy / Logic / Mathematics but apparently is doable in compiler design (!).

Further, it would seem that if the original idiom syntax is acceptable then one might also be allowed to say:

public interface IComparable<T extends IComparable<T extends IComparable<T>>> {
    public int compare(T item);
}

... but the compiler balks at that apparently allowing only one level of extend.

Can anyone shed some light to help me grok this kind of recursive generic definitions?

UPDATE

Based on the accepted answer (BartoszKP) what I think I now understand is the following:

The "recursive" definition should NOT be read as (arrows representing the "the definition depends on" relationship):

[ IComparable<T> ] -------> [ IComparable<T> ]

... which is illogical (circular), but rather as:

[ IComparable<T> ] ----------> [ list of methods (parameterized by T) ]
          \                                      ^
           \                                     |
            \-------> [ type bound on T ]-------/

... which is not illogical and thus doable in the compiler. So, in words, the definition of IComparable is given in terms of the list of methods it defines and the bound it defines on type T and the latter in turn also depends on the list of methods. So, no recursion.

Answer 1

This is a well-known idiom in Java.

No. It is not useful, and should not be used. With the exception of Enum (which is a special case because enum types are compiler-generated), this pattern is never seen anywhere in the official Java libraries, or anywhere in any official Java documentation.

The purpose of Generic bounds on a type variable is to set up a relationship so that code inside the generic class or generic method can use that guarantee to perform some operations without casts, which are potentially unsafe. Generics bounds should be as unrestrictive as possible while still preventing the casts in the code.

Therefore, the only legitimate purpose of a bound interface IComparable<T extends IComparable<T>> would be if 1) it's actually a class, not an interface (interfaces do not have code, and thus there are no casts to avoid), and 2) code in the class needs to perform the following operation: use a method to get T out of itself, and then call on that a method that requires IComparable<T>. Then, a guarantee that T extends IComparable<T> would allow this to be done without casts.

I've seen many uses of this pattern, and in 99% of the cases, they do not need to do the above-mentioned operation. Rather, 99% of the time, what people want to do is somehow express that T "is equal to" IComparable<T>, which the above pattern does not guarantee (and which is impossible to express in Java). It only guarantees that T extends IComparable<T>, but not that IComparable<T> extends T.

Most of the time when people use this pattern, they use it for a class inside of which they do (T)this. The fact that there needs to be a cast shows that this is potentially unsafe; that its type safety is not guaranteed by the bounds (there is no guarantee that this (of type IComparable<T>) extends T). It is actually unsafe; a well-known example is class Foo extends IComparable<Foo>, and then class Bar extends IComparable<Foo>, thus this (of type Bar) does not extends T (Foo).

So if you ever see that code, it is almost certainly written with some misconception about what it does, and it should almost always be changed to this:

public interface IComparable<T> {
    public int compare(T item);
}

As an exercise, I challenge you to find a snippet where interface IComparable<T extends IComparable<T>> works, and where interface IComparable<T> does not work.

Answer 2

Actually - you don't need the recursive definition in your case.

public interface IComparable<T> {
  public int compare(T item);
}

public class Foo implements IComparable<Foo> {
  @Override
  public int compare(Foo o) {
    return 0;
  }
}

Is quite sufficient to define what you are attempting.

A common place for recursive definitions is when you are working with enum. You will often see E extends Enum<E> and in this context it actually makes a lot of sense because the Enum class is defined with a generic type E that it enumerates.

As a narrative to @NPE's post on the referenced discussion:

public interface ResultItem<T extends ResultItem<T>> {
    public int getConfidence();
    public boolean equals(T item);
    public T cloneWithConfidence(int newConfidence);
}

What is happening here is that instead of defining your class in terms of a specific generic class T you are stating that T must extend ResultItem, i.e. it is any subclass of ResultItem. Of course, since ResultItem is a generic class you have to give it's generic parameter which, in this case is T itself. Thus the T extends ResultItem<T>. This is not a recursive definition, it is a subclass capture definition.

Answer 3

First, about your doubts regarding the recurrence:

It is some kind of recurrence (as X is being defined by something related to X), but even if it is, it's only one level. Imagine the compiler has a function define which defines something it doesn't already know by reading and compiling the source file, and an utility function get_list_of_methods. So in the case of the ResultItem we have:

1) define(interface ResultItem<T extends ResultItem<T>>)

For this, a definition of the inner ResultItem<T> is needed. But we don't need to know everything about ResultItem<T>, we want to know only what it means that something extends ResultItem<T>, therefore at first:

2) get_list_of_methods(ResultItem<T>)

This parses the source file getting the list of all the methods of ResultItem<T> - we don't have to compile them now.

3) create generic constraint guarding that T will have all the methods of ResultItem<T>

4) Continuation of step 1) - parse the source file getting the definitions of all the methods of ResultItem<T>. Knowing what methods are being implemented by T from step 2 we can compile the methods.

Probably in reality this is more complicated, but this helps to see that no recurrence is needed to interpret this. So it's no more recurrent than class X having a method that accepts X. It just needs more than one pass. In older languages such lookahead definitions where not possible. Even in C++ now you need forward declarations:

class X;

class Y
{
private:
  X* x;
};

class X
{
};

Next, about the usability of this. Gathering information from the comments and related topics, I'd state that this mechanism is used to express the intent about classes implementing given interface, and making the interface more useful and convenient. This topic explains it in more detail: How can I make an interface instance method accept arguments of the same class only?.

In the second case, there is no gain in convenience for classes implementing the interface:

public interface IComparable<T extends IComparable<T>> {
  public int compare(T item);
}

However, it can be interpreted as expressing the fact, that an entity which is comparable is comparable only with comparable items of the same type. It is not the best example, as noted in other answers and comments, as you could still write class X implements IComparable<Y> as long as Y is also comparable. More detail here: How can I make an interface instance method accept arguments of the same class only, really?.

More details about usage of this idiom: http://www.angelikalanger.com/GenericsFAQ/FAQSections/TypeParameters.html#FAQ106.