The Artima Developer Community
Sponsored Link

Weblogs Forum
Generics and covariant return types

17 replies on 2 pages. Most recent reply: Nov 11, 2005 11:11 AM by James Watson

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 17 replies on 2 pages [ 1 2 | » ]
Bruce Eckel

Posts: 875
Nickname: beckel
Registered: Jun, 2003

Generics and covariant return types (View in Weblogs)
Posted: Nov 8, 2005 4:52 PM
Reply to this message Reply
Summary
I came across another generic puzzle and hope that someone has some insights.
Advertisement

Suppose you have a class with a method f():


public class HasF {
  public HasF f() {
    System.out.println("HasF::f()");
    return this;
  }
}

Here's a class that uses HasF as a bound for its generic parameter T. It stores an object of type T, and since the type parameter erases to its first bound, the methods of HasF are available:


class Manipulator4<T extends HasF> {
  private T obj;
  public Manipulator4(T x) { obj = x; }
  public T manipulate() { obj.f(); }
}

The problem is that, in theory, covariant return types allow a return value to be the specified type or something derived from it. So it would seem that manipulate() would be able to return a HasF or something derived from it, which is exactly what T is bounded to be. So it would seem that the definition of manipulate() is OK, but the compiler gives an error: incompatible types, found : HasF, required: T. This is further confusing because T erases to HasF.


Brian Slesinsky

Posts: 43
Nickname: skybrian
Registered: Sep, 2003

Re: Generics and covariant return types Posted: Nov 8, 2005 5:56 PM
Reply to this message Reply
The example would be clearer if you defined f like this:


public HasF f() {
System.out.println("HasF::f()");
return new HasF();
}


The type-checker only looks at the type signature for f(), not the executable code, so the "return this" statement is a red herring.

In the manipulate() method, f() returns a HasF object, but T could be a subclass of HasF, so converting HasF to T requires a cast. For type-checking purposes, erasure doesn't matter.

Guillaume Taglang

Posts: 18
Nickname: gouyou
Registered: Jul, 2003

Re: Generics and covariant return types Posted: Nov 8, 2005 6:12 PM
Reply to this message Reply
I believe the code should be either:
class Manipulator4<T extends HasF> {
  private T obj;
  public Manipulator4(T x) { obj = x; }
  public T manipulate() { return (T) obj.f(); }
}

or:
class Manipulator4<T extends HasF> {
  private T obj;
  public Manipulator4(T x) { obj = x; }
  public HasF manipulate() { return obj.f(); }
}

or I didn't understand what you are trying to do ...

Guillaume Taglang

Posts: 18
Nickname: gouyou
Registered: Jul, 2003

Re: Generics and covariant return types Posted: Nov 8, 2005 6:14 PM
Reply to this message Reply
>
> class Manipulator4<T extends HasF> {
>   private T obj;
>   public Manipulator4(T x) { obj = x; }
>   public T manipulate() { return (T) obj.f(); }
> }
> 


The casting being really bad as you need to have insider knowledge about what the HasF class is doing ...

Bruce Eckel

Posts: 875
Nickname: beckel
Registered: Jun, 2003

Re: Generics and covariant return types Posted: Nov 8, 2005 6:35 PM
Reply to this message Reply
> The example would be clearer if you defined f like this:
>
>
> public HasF f() {
> System.out.println("HasF::f()");
> return new HasF();
> }
>

>
> The type-checker only looks at the type signature for f(),
> not the executable code, so the "return this" statement is
> a red herring.
>
> In the manipulate() method, f() returns a HasF object, but
> T could be a subclass of HasF, so converting HasF to T
> requires a cast. For type-checking purposes, erasure
> doesn't matter.


That doesn't make the example compile.

And semantically, returning a reference to the current object produces very different results than creating a new instance.

Bruce Eckel

Posts: 875
Nickname: beckel
Registered: Jun, 2003

Re: Generics and covariant return types Posted: Nov 8, 2005 6:42 PM
Reply to this message Reply
> >
> > class Manipulator4<T extends HasF> {
> >   private T obj;
> >   public Manipulator4(T x) { obj = x; }
> >   public T manipulate() { return (T) obj.f(); }
> > }
> > 

>
> The casting being really bad as you need to have
> insider knowledge about what the HasF class is
> doing ...

It would seem to be perverse in that fashion -- except that on top of this, casting to T is, because of erasure, the equivalent of casting to Object. So although this compiles, you still get a warning.

I think your first approach -- manipulate() returns HasF -- is probably better, especially because it produces no warnings, and you do know that manipulate() returns that type. But in that case, the need for generics is eliminated for that example, since you could just say:


class Manipulator5 {
private HasF obj;
public Manipulator5(HasF x) { obj = x; }
public HasF manipulate() { return obj.f(); }
}

Jay Sachs

Posts: 30
Nickname: jaysachs
Registered: Jul, 2005

Re: Generics and covariant return types Posted: Nov 8, 2005 9:24 PM
Reply to this message Reply
What you really want is something akin to a MyType construct (http://cs.williams.edu/~kim/ftp/LOOJ.pdf.gz for example), like to Eiffel's "like self". MyType is unfortunately another gap in Java's generics. It most certainly was well known and understood by the authors of Pizza, the precursor to Java's generics, but was omitted. I suspect the reason has everything to do with the erasure abmonination.

In any case, MyType would allow you to write
class HasF {
  public MyType f() { ...; return this; }
}
class Manipulator<T extends HasF> {
class Manipulator4&lt;T extends HasF&gt; {
private T obj;
public Manipulator4(T x) { obj = x; }
public T manipulate() { obj.f(); }
}}

and it would compile.

The problem with your original code snippet is that the return type of f is fixed at type HasF; the MyType would automatically be covariant.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Generics and covariant return types Posted: Nov 8, 2005 11:20 PM
Reply to this message Reply
This is an interesting generic pattern that crops up in a number of places, e.g. generic factories. The solution I use:
abstract class HasF< T extends HasF< T > > {
    abstract T fClass();
    @SuppressWarnings( "unchecked" ) T f() {
        System.out.println( "HasF.f()" );
        return (T)this;
    }
}
class HasFClass extends HasF< HasFClass > {
    HasFClass fClass() {
        System.out.println( "HasFClass.fClass()" );
        return this;
    }
}
public class Manipulate< T extends HasF< T > > {
    T obj;
    Manipulate( final T x ) { obj = x; }
    T manipulate() { return obj.f(); }
    T manipulateClass() { return obj.fClass(); }
    public static void main( final String[] notUsed ) {
        final HasFClass f = new HasFClass();
        final Manipulate< HasFClass > m = new Manipulate< HasFClass >( f );
        final HasFClass f2 = m.manipulate();
        final HasFClass f3 = m.manipulateClass();
    }
}

I expanded the example to show the two cases of a function in a base class, f, and in a derived class, fClass. The pattern uses a generic-abstract base, either an abstract class or an interface, that is recursively generic, HasF, in the above. Then a concrete, non-abstract, and non-generic class is derived, HasFClass. The class Manipulate programs to the the generic-abstract base but is parameterized with the concrete-non-generic class.

The difference between f and fClass is the cast in f. This is because of the lack of a MyType in Java as Jay Sachs has pointed out (but note it is not associated with erasure - both Pizza and Scala that have MyType use erasure). The problem is that Java takes this to be of type HasF whereas in fact it is of type extends HasF, which because of the recursive definition of T is T, and hence the cast won't fail (it is just that Java doesn't know it won't fail!).

Scala is a newish programming language from Martic Odersky, who also wrote Pizza -> GJ -> Java 5. In the paper Odersky wrote about Scala, http://scala.epfl.ch/docu/files/ScalaOverview.pdf, he gives a couple of examples of this same construct and how two type extensions in Scala generics help. The examples he gives in Scala are coded in Java as:
abstract class CBase< T extends CBase< T > > {
    protected int x = 0;
    @SuppressWarnings( "unchecked" ) T incr() { ++x; return (T)this; }
    public String toString() { return Integer.toString( x ); }
}
class C extends CBase< C > {}
class D extends CBase< D > {
    D decr() { --x; return this; }
}
public class ThisType {
    public static void main( final String[] notUsed ) {
        final D d = new D();
        d.incr().decr();
        System.out.println( d );
        final C c = new C();
        c.incr();
        System.out.println( c );
    }
}

The interesting line in this example is d.incr().decr() which is written without casts which is not possible with covarient return types alone. The second example given in the paper and coded in Java is:
abstract class Subject< S extends Subject< S, O >, O extends Observer< S, O > > {
    private final List< O > observers = new ArrayList< O >();
    void subscribe( O obs ) { observers.add( obs ); }
    void publish() {
        for ( final O obs : observers )
            obs.notify( (S)this );
    }
}
abstract class Observer< S extends Subject< S, O >, O extends Observer< S, O > > {
    abstract void notify( S sub );
}
class Sensor extends Subject< Sensor, Display > {
    double value = 0.0;
    void changeValue( final double v ) {
        value = v;
        publish();
    }
}
class Display extends Observer< Sensor, Display > {
    void notify( Sensor sub ) {
        System.out.println( sub  + " has value " + sub.value );
    }
}
public class SubjectObserver {
    public static void main( final String[] notUsed ) {
        final Display o = new Display();
        final Sensor s = new Sensor();
        s.subscribe( o );
        s.changeValue( 1 );
    }
}

This is a nice variation on the ame theme where mutually recursive generic definitions are used.

lagorio

Posts: 1
Nickname: lagorio
Registered: Feb, 2003

Re: Generics and covariant return types Posted: Nov 9, 2005 4:04 AM
Reply to this message Reply
> public class HasF {
> public HasF f() {
> System.out.println("HasF::f()");
> return this;
> }
> } ....
> class Manipulator4<T extends HasF> {
> private T obj;
> public Manipulator4(T x) { obj = x; }
> public T manipulate() { obj.f(); }
> }

If I'm not missing something here, generic class Manipulator4 can be instantiated with types "T" which are HasF or are more specific. So, if I define:
class MoreSpecific extends HasF {}
then I can instantiate Manipulator4<MoreSpecific>; in this case it easy to see that if the compiler allowed you to return an HasF in place of a T (in this case: MoreSpecific) you would get a problem at runtime.

Adam Kiezun

Posts: 4
Nickname: akiezun
Registered: Nov, 2005

Re: Generics and covariant return types Posted: Nov 9, 2005 12:32 PM
Reply to this message Reply
The compiler is perfectly reasonable here.

A class is not required to have return types covariant.
So, imagine a class that did not made the return type convariant.

<code>
class Foo extends HasF{
public HasF f() { .... }
}
</code>

Now, it's clear that manipulate() is bogus!
Imagine Manipulator4<Foo>
The manipulate() method thinks its return type is Foo but the call to obj.f() returns HasF.

Krzysztof Sobolewski

Posts: 7
Nickname: jezuch
Registered: Dec, 2003

Re: Generics and covariant return types Posted: Nov 9, 2005 3:34 PM
Reply to this message Reply
Yep, you're definitely overgenerified :)

HasF::f() returns HasF and no <T extends HasF> will change that, only explicit subclassing and changing the return type. Conpiler only sees static types so no wonder it's complaining.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Generics and covariant return types Posted: Nov 9, 2005 5:03 PM
Reply to this message Reply
@Krzysztof Sobolewski,

Consider this example of the same problem:
abstract class CBase< T extends CBase< T > > {
    int x = 0;
    T incr() { ++x; return (T)this; }
}
class C extends CBase< C > {}
class D extends CBase< D > {
    D decr() { --x; return this; }
}

Now think about:
d.incr().decr(); // d is a D

You can't write this line without generics, i.e. if:
class C {
    int x = 0;
    C incr() { ++x; return this; }
}
class D extends C {
    D decr() { --x; return this; }
}

you would need to write:
((D)(d.incr())).decr(); // i.e. add a cast

Therefore using the generics as well as covarient returns helps simplify the use of an API, but at the expense of a harder to write API.

Paul de Vrieze

Posts: 9
Nickname: pauldv
Registered: Oct, 2005

Re: Generics and covariant return types Posted: Nov 10, 2005 11:02 AM
Reply to this message Reply
The problem is very simple. Looking at erasures just makes things harder.

public class HasF {
public HasF f() {
System.out.println("HasF::f()");
return this;
}
}

appears to allways return an object of type HasF. One cannot make any guarantees about whether it is a subtype.

This problem is very prevalent in the Object.clone() method as it makes it impossible to specify that the method always should return an object of the same type as the callee. IMHO this is a language oversight and should be corrected in later language versions. I would propose something like:

public class HasF {
public this.class f() {
System.out.println("HasF::f()");
return this;
}
}

in which case <T extends HasF> would see the function prototype as T f(), and the usage as proposed would work.

Krzysztof Sobolewski

Posts: 7
Nickname: jezuch
Registered: Dec, 2003

Re: Generics and covariant return types Posted: Nov 10, 2005 4:06 PM
Reply to this message Reply
Well, I didn't say it's impossible.

BTW: isn't "(T)this" in incr() goint to cause an "unchecked" warning? [I haven't checked this] I don't like warnings, you know ;)

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Generics and covariant return types Posted: Nov 10, 2005 5:54 PM
Reply to this message Reply
@Krzysztof Sobolewski

Yes there will be an unchecked warning that you would supress. It is a pity that the type checking in Java can't do the example without a cast. Paul de Vrieze has suggested this.class notation which is similar to what many languages do, e.g. Scala. Another alternative is that the existing type checking is changed so that:

1. The type of this is not taken as the type of the class but instead its type is the class or a subclass and the types from point 2 below

2. The compiler then looks for recursive type parameters and makes this have these types also.

3. In the example therefore the type of this would be the set {CBase, ? extends CBase, T}, since T is in the set of types the cast wouldn't be necessary.

I guess that both solutions are viable and it is a matter of chosing which one people prefer. In the mean time you have to use the cast. Personally my vote goes for something like this.class since I think most people find recursive type declarations difficult to follow. To show my complete biase I would just use this. IE:
class C {
    int x = 0;
    this incr() { ++x; return this; }
}
class D extends C {
    this decr() { --x; return this; }
}

Which says that the method can only return this or a this from a derived type. Note I added this to D also. If you want decr to be also extendable then you would at present need to introduce another recursive type definition.

Flat View: This topic has 17 replies on 2 pages [ 1  2 | » ]
Topic: Proposal: XML-- (read: XML minus minus) Previous Topic   Next Topic Topic: IQ is a Relatively Meaningless Number Consumed by Egotistical Narcissists


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us