Mixing self conscious parametrized types with inheritance

[Robert Klemme]

Hi,

inspired by our recent discussions of generics I set out to get a clear
picture of how to properly use Comparable<T> - especially when
inheritance comes into play.

1. Only classes whose methods that use the type parameter may not be
overridden with type specific functionality (either because all methods
or the class is final, or the type need not change when sub classes
override those) can do away with the type parameter.

2. All others need to repeat the type parameter (in case of self
reference with a bound).

class BaseC<SC extends BaseC<?>> implements Comparable<SC> {
@Override
public int compareTo(SC o) {
return getKey() - o.getKey();
}
}

class SubC<SC extends SubC<?>> extends BaseC<SC> {
@Override
public int compareTo(SC o) {
final int cmp = getK() % 3 - o.getK() % 3;
return cmp == 0 ? getK() - o.getK() : cmp;
}
}

final class FinalC extends SubC<FinalC> {
@Override
public int compareTo(FinalC o) {
final int cmp = getX() % 2 - o.getX() % 2;
return cmp == 0 ? getPos() - o.getPos() : cmp;
}
}

Full code is here https://gist.github.com/868085

Kind regards

robert

 

[Lew]

inspired by our recent discussions of generics I set out to get a clear
picture of how to properly use Comparable<T> - especially when inheritance
comes into play.

1. Only classes whose methods that use the type parameter may not be
overridden with type specific functionality (either because all methods or the
class is final, or the type need not change when sub classes override those)
can do away with the type parameter.

Would you please describe this a bit more fully, perhaps with an example? I'm
not quite getting it.

2. All others need to repeat the type parameter (in case of self reference
with a bound).

class BaseC<SC extends BaseC<?>> implements Comparable<SC> {

The convention is to use single-letter type parameters.

I totally don't get what you're asserting here.

Why do you want 'Base' to implement 'Comparable' on a subtype instead of on
itself?

Why the wildcard rather than 'class BaseC <S extends Base <S>>'?

The usual approach is 'class Foo implements Comparable <Foo>', not of some
subtype of 'Foo'.

I'd like to say:

class Base <S extends Base <S>> implements Comparable <Base <S>>

Mind you, I don't think generics work with multiply-nested type parameters
beyond a certain point, or maybe I just can't mentally encompass the type
assertions they make.

Just like I haven't mentally encompassed the type assertions you're trying to
make. The difficulties don't seem to involve 'Comparable' so much as what
you're actually attempting to aver.

 

[Robert Klemme]

Would you please describe this a bit more fully, perhaps with an
example? I'm not quite getting it.

What's missing from the code at Github? Do you think I should provide
another example? FinalC does not need a type parameter because it
cannot get more specific than this class which is final. Of course we
could think of other examples as well, e.g. a class hierarchy where
parts decide to fix the type parameter:

class Base<C extends CharSequence> {
public void process(List<C> lc) ...
}

class Derived1<C extends CharSequence> extends Base<C> {
@Override
public void process(List<C> lc) ...
}

class Derived2 extends Base<String> {
@Override
public final void process(List<String> ls) ...
}

Derived2 does not need a type parameter because someone decided to
settle with String for the type and disallow overriding of this method
in sub classes. Derived2 on the other hand does not use final nor does
it specify the type.

The convention is to use single-letter type parameters.

Well, yes. From time to time I take the liberty to allow for more
uppercase letters if I have the feeling this helps remember the purpose
of the type.

I totally don't get what you're asserting here.

Why do you want 'Base' to implement 'Comparable' on a subtype instead of
on itself?

Because Base is intended for inheritance. If you settle with
Comparable<Base> compareTo() has an argument of type Base. In that case
your sub classes which might want to implement compareTo() differently
do not have access to their own members (other than through explicit
casting which generics are trying to avoid in the first place). And you
cannot make sub classes inherit Comparable<SubC> and implement
compareTo(Subc o) because then type erasure creates a conflict because
both methods have the same erased signature. You can see this when
trying to compile FailedApproach from the Gist
https://gist.github.com/868085 .

Why the wildcard rather than 'class BaseC <S extends Base <S>>'?

That does not work because it is a recursive type definition - at least
that's what I believe to be the reason. Anyway, I my experiments this
breaks when trying to instantiate the class. At least I could not find
a way to do it. I'd be glad to see how it can be done if it can.

The usual approach is 'class Foo implements Comparable <Foo>', not of
some subtype of 'Foo'.

You can only use this approach if you either do not intend to inherit
that class OR want sub classes be sorted according to only base class
state. In that case it's probably also a good idea to make compareTo()
final.

I'd like to say:

class Base <S extends Base <S>> implements Comparable <Base <S>>

Mind you, I don't think generics work with multiply-nested type
parameters beyond a certain point, or maybe I just can't mentally
encompass the type assertions they make.

It usually takes me a bit of experimenting and reasoning, too. Generics
can be tricky at times.

Just like I haven't mentally encompassed the type assertions you're
trying to make. The difficulties don't seem to involve 'Comparable' so
much as what you're actually attempting to aver.

The example classes compose an inheritance hierarchy of classes which
all should be comparable but according to class specific criteria (i.e.
they must have compareTo(MyOwnClass o) instead of just compareTo(Base o)).

I have also added a second version which does not compile. This version
makes all class implement Comparable<OwnType> but that fails with

The interface Comparable cannot be implemented more than once with
different arguments: Comparable<BaseC> and Comparable<SubC>

If you want to give all classes in the hierarchy the freedom to have
their own default ordering (likely based on class specific state) there
is no other way than to carry a type parameter through the hierarchy.

Kind regards

robert

 

[Lew]

What's missing from the code at Github? Do you think I should provide another

The explanation of what you meant and how the example demonstrates it.

example? FinalC does not need a type parameter because it cannot get more
specific than this class which is final. Of course we could think of other

I think the business about methods being final is a red herring. You don't
have to express a type parameter when you've completely resolved it. That
isn't about the finality of the subtype or its methods but about the
completeness of type-parameter resolution.

examples as well, e.g. a class hierarchy where parts decide to fix the type
parameter:

class Base<C extends CharSequence> {
public void process(List<C> lc) ...
}

class Derived1<C extends CharSequence> extends Base<C> {
@Override
public void process(List<C> lc) ...
}

class Derived2 extends Base<String> {
@Override
public final void process(List<String> ls) ...
}

Derived2 does not need a type parameter because someone decided to settle with
String for the type and disallow overriding of this method in sub classes.

Again, this is not about whether the method is final.

Thanks for your answers. I need to take some time to digest them and to do my
own experiments. I think I see what you're trying to accomplish now.

 

[Lew]

inspired by our recent discussions of generics I set out to get a clear
picture of how to properly use Comparable<T> - especially when inheritance
comes into play.

People will have to review the thread if they want the part I elided.

I think the problem is that the base class is 'implements Comparable <S>'.
That really isn't the type assertion for 'Comparable'. The
self-referentiality is tangling the type assertions, for sure, but the real
problem is that you want the subclass to implement its own 'compareTo()'
separate from the superclass's. The wildcard dodge weakens the type
assertions to the point where you get away with it.

Normally a comparable class 'Foo' uses 'implements Comparable<Foo>'. You
didn't do that. If you had, you'd wind up with:

class BaseC<SC extends BaseC<?>> implements Comparable<BaseC<SC>> {
@Override
public int compareTo( BaseC<SC> o) {
return getKey() - o.getKey();
}
}

You cheated by having 'BaseC#compareTo()' take a different type argument from
what it's supposed to take. Yes, you did subvert the generics system by doing
that, but only by changing the semantics of what you're asserting.

Then you'd have

class SubC<SC extends SubC<?>> extends BaseC<SC> {
@Override
public int compareTo( SubC<SC> o) {
final int cmp = getK() % 3 - o.getK() % 3;
return cmp == 0 ? getK() - o.getK() : cmp;
}
}

which yields the correct compiler error that you had subverted, with or
without a clause 'implements Comparable<SubC<SC>>'.

I also wonder about the 'extends BaseC<SC>' part. Generics aren't covariant
through the type parameter without some 'extends' magic, so I think this part
tangles the type assertions also. I haven't thought it through yet.

Anyway, you have found a corner where the generics assertions cannot handle
what you wanted to do. That part is true. It is also true that formally you
want to make different type assertions from those to properly implement
'Comparable'. When you make the correct type assertions, the compiler chokes
on the erasure demon.

You might be able to get away with the kind of self-referentiality you want
better with interfaces at the root than with classes. That's a good followup
line of inquiry.

 

[Robert Klemme]

People will have to review the thread if they want the part I elided.
Definitively.

I think the problem is that the base class is 'implements Comparable <S>'..
That really isn't the type assertion for 'Comparable'.  The
self-referentiality is tangling the type assertions, for sure, but the real
problem is that you want the subclass to implement its own 'compareTo()'
separate from the superclass's.  The wildcard dodge weakens the type
assertions to the point where you get away with it.

That's an unfriendly way to state it. I rather like to think of
having found the proper generics solution for a given problem.

Normally a comparable class 'Foo' uses 'implements Comparable<Foo>'.  You
didn't do that.  If you had, you'd wind up with:

  class BaseC<SC extends BaseC<?>> implements Comparable<BaseC<SC>> {
   @Override
   public int compareTo( BaseC<SC> o) {
     return getKey() - o.getKey();
   }
  }

You cheated by having 'BaseC#compareTo()' take a different type argument from
what it's supposed to take.  Yes, you did subvert the generics system by doing
that, but only by changing the semantics of what you're asserting.

I can't detect the cheating. I simply deferred specification of
Comparable's type parameter to the point in time when the type is
known. Since we cannot specify Comparable's type parameter in the
base class (because sub classes need different types here) we must
keep it undefined (i.e. need a type variable for it). That's
basically the general generics approach. It may be obfuscated a bit
through the fact that the type we want to use is always the class we
are actually writing but it's nevertheless the generics mantra of "if
you don't know the type yet, use a type parameter".

Then you'd have

Not "would" but "do": https://gist.github.com/868085#file_self_consciousness_test.java

  class SubC<SC extends SubC<?>> extends BaseC<SC> {
   @Override
   public int compareTo( SubC<SC> o) {
     final int cmp = getK() % 3 - o.getK() % 3;
     return cmp == 0 ? getK() - o.getK() : cmp;
   }
  }

which yields the correct compiler error that you had subverted, with or
without a clause 'implements Comparable<SubC<SC>>'.

I also wonder about the 'extends BaseC<SC>' part.  Generics aren't covariant
through the type parameter without some 'extends' magic, so I think this part
tangles the type assertions also.  I haven't thought it through yet.

Anyway, you have found a corner where the generics assertions cannot handle
what you wanted to do.  That part is true.

No, I haven't found a corner case generics cannot handle. The code at
https://gist.github.com/868085#file_self_consciousness_test.java
exactly shows how to handle the situation. The other example was to
demonstrate that the approach with class BaseC implements

 It is also true that formally you
want to make different type assertions from those to properly implement
'Comparable'.  When you make the correct type assertions, the compiler chokes
on the erasure demon.

You might be able to get away with the kind of self-referentiality you want
better with interfaces at the root than with classes.  That's a good followup
line of inquiry.

Actually the working example is exactly what should be done here. We
want a class hierarchy where every class has its own default
ordering. It follows we want Comparable and it also follows that we
cannot use Comparable with a specific type but we need to propagate
the type parameter from the most specific type upwards. That requires
a type parameter at the base class and all sub classes which can have
sub classes that need a different type propagated.

Kind regards

robert

 

[Lew]

That's an unfriendly way to state it. I rather like to think of
having found the proper generics solution for a given problem.

"Unfriendly"?

It's weaker to say "some subtype of Object" than "type Foo". It's not as
strong an assertion.

It's no unfriendlier than to say that 100 newtons is a weaker force than 1000.

It's also not a proper solution because of your dodge on the declaration of
'Comparable' implementation.

I can't detect the cheating. I simply deferred specification of

The cheating is that you implement 'Comparable<SC>' ionstead of
'Comparable<Base<SC>>'. The non-cheating way is to implement 'Comparable' of
the class you want to compare, not the type parameter. Do you see that you

Comparable's type parameter to the point in time when the type is
known. Since we cannot specify Comparable's type parameter in the
base class (because sub classes need different types here) we must
keep it undefined (i.e. need a type variable for it). That's
basically the general generics approach. It may be obfuscated a bit
through the fact that the type we want to use is always the class we
are actually writing but it's nevertheless the generics mantra of "if
you don't know the type yet, use a type parameter".


Not "would" but "do": https://gist.github.com/868085#file_self_consciousness_test.java

Sorry, but that is just untrue. In there you have

class BaseC<SC extends BaseC<?>> implements Comparable<SC> {

I just now copied-and-pasted that line into this post, so I'm telling the truth.

No, I haven't found a corner case generics cannot handle. The code at
https://gist.github.com/868085#file_self_consciousness_test.java
exactly shows how to handle the situation. The other example was to

It shows how to handle it incorrectly because of the 'Comparable' dodge.

demonstrate that the approach with class BaseC implements
Comparable<BaseC> does NOT work: https://gist.github.com/868085#file_failed_approach.java

Right, because it bumps up against the erasure issue.

Actually the working example is exactly what should be done here. We

Except for implementing 'Comparable' on the type parameter instead of the
class, which is not "exactly what should be done", it's "exactly what should
not be done" because it makes for convoluted, hard-to-understand and
not-exactly-what-you-want type assertions.

The problem is that you aren't declaring 'class Foo implements

want a class hierarchy where every class has its own default
ordering. It follows we want Comparable and it also follows that we
cannot use Comparable with a specific type but we need to propagate

You have found a workaround for the erasure issue. The problem is that you
created a generics structure that doesn't declare exactly what you mean and is
difficult to reason about. OTOH, the difficulty with the "normal" approach is
that you cannot get Java generics to do what you want that way.

the type parameter from the most specific type upwards. That requires
a type parameter at the base class and all sub classes which can have
sub classes that need a different type propagated.

Well, it requires that you cheat, in the sense that you have to warp the
declaration of 'implements Comparable'.

Notice I'm not saying one shouldn't do what you suggest, only that it requires
some dodgy type assertions to get around erasure and playing loose with the
semantics of 'implements Comparable'.

 

[Lew]

Sorry, but that is just untrue. In there you have

class BaseC<SC extends BaseC<?>> implements Comparable<SC> {

Oops. Wrong line.

I just now copied-and-pasted that line into this post, so I'm telling the truth.

I quoted the wrong line, instead of copying and pasting

public int compareTo(SC o) {

from your link.

 

[Robert Klemme]

"Unfriendly"?

It's weaker to say "some subtype of Object" than "type Foo".  It's not as
strong an assertion.

It's no unfriendlier than to say that 100 newtons is a weaker force than 1000.

It's also not a proper solution because of your dodge on the declaration of
'Comparable' implementation.

The "dodge" and "get away" bits are the "unfriendly" ones. You
call what I would call a "proper solution" to a given problem "a
workaround". Why do you insist that only Comparable<ConcreteType> is
valid and not Comparable<TypyParameter>? This is general practice,
e.g.

public class Processor<T> {
private final List<T> processed = new ArrayList<T>();

public void process(T it) {
processed.add(it);
}
}

Here List<T> is also unspecified and will only be fixed when I

The cheating is that you implement 'Comparable<SC>' ionstead of
'Comparable<Base<SC>>'.  The non-cheating way is to implement 'Comparable' of
the class you want to compare, not the type parameter.  Do you see thatyou
did not implement 'Comparable<Base<SC>>' but instead 'Comparable<SC>'?  If you
see that, then you've detected the cheating.

I see it but I fail to recognize the cheating (see above). Also,
please note that SC is bound (SC extends BaseC<?>). This also means
that

public int compareTo(SC o) {

can work with the fact (i.e. access specific members) that SC is

Sorry, but that is just untrue.  In there you have

    class BaseC<SC extends BaseC<?>> implements Comparable<SC> {

I just now copied-and-pasted that line into this post, so I'm telling thetruth.





It shows how to handle it incorrectly because of the 'Comparable' dodge.


Right, because it bumps up against the erasure issue.



Except for implementing 'Comparable' on the type parameter instead of the
class, which is not "exactly what should be done", it's "exactly what should
not be done" because it makes for convoluted, hard-to-understand and
not-exactly-what-you-want type assertions.

The problem is that you aren't declaring 'class Foo implements


You have found a workaround for the erasure issue.  The problem is thatyou
created a generics structure that doesn't declare exactly what you mean and is
difficult to reason about.  OTOH, the difficulty with the "normal" approach is
that you cannot get Java generics to do what you want that way.


Well, it requires that you cheat, in the sense that you have to warp the
declaration of 'implements Comparable'.

I don't see why I "warp" the declaration.

Notice I'm not saying one shouldn't do what you suggest, only that it requires
some dodgy type assertions to get around erasure and playing loose with the
semantics of 'implements Comparable'.

I cannot find anything in http://download.oracle.com/javase/6/docs/api/java/lang/Comparable.html
that would explain the dodgyness of my solution and render it a
workaround instead of a proper solution. What am I missing?

Kind regards

robert