Friday, January 04, 2008

Java Generics Broken? We Report, You Decide.

Since I've been taken to task in the past for my cogent observations of Java's, um, shall we say "unintuitive" behavior, particularly in the era of generics and autoboxing, I'm just going to put this one out there without making any (public (explicit)) value judgments.

So it seems that if you define a method thusly (note: requires Java 5 ("Gangly Geek") or better greater having a numerically higher version number):
public void doSomethingGenerically(Collection<Supertype>){...}
and you attempt to call it thusly:
List<SubtypeOfSupertype> bogus = new ArrayList<SubtypeOfSupertype>();
doSomethingGenerically(bogus);
you get a compiler error saying you can't call that method with those arguments.

So my question here is: why the heck not?

Inheritance 101: a List isa Collection, right? A SubtypeOfSupertype isa Supertype, right? So why am I being told that an instance of type List<SubtypeOfSupertype> isn'ta Collection<Supertype>?

Paging Dr. Liskov...

12 comments:

C�dric said...

Try the following :

public void doSomethingGenerically(Collection<? extends Supertype>){...}

David Rupp said...

@cédric: Will do, thanks. (P.S.: I'm guessing on the diacritic for the second letter of your name; it's not displaying properly for me for some reason. Sorry if I got it wrong.)

dr said...

I think Cedric's suggestion is the correct approach. Passing a List<SubtypeOfSuperType> as a Collection<SuperType> would invalidate the contract of List<SubtypeOfSuperType>. That is, inside the method, any subclass or SuperType could be added to the list (since it's just a Collection of SuperType) but then List<SubtypeOfSuperType> would not only contain SubtypeOfSuperType objects.

David Rupp said...

@dr: I see what you're saying, but it seems that Cédric's approach would be susceptible to the same problem. It also looks like it wouldn't allow me to pass in a collection of Supertypes, which I might want to do (hence the original signature).

Your point about adding something higher in the inheritance hierarchy is well taken. The compiler would probably not be able to catch that kind of thing, it would have to happen at runtime. Which would defeat the purpose of the static typing. But the status quo defeats the purpose of generics. Hmm.

Sean Fritz said...

@David "It also looks like it wouldn't allow me to pass in a collection of Supertypes, which I might want to do (hence the original signature).
"

This catches my students up all the time. The extends in "? extends Super" is semantically different than "class X extends Y" for class declarations

In this situation your defining a contravariant type parameter ? bound by Supertype. See wikipedia for more discussion.

I will make a value judgement, Java generics solve a lot of hard problems that C# generics sweep under a rug. It's impossible in C# 2.0 to match a contravariant type hierarchy. Instead C# allows you to implement a interface multiple times to avoid the issue in a lot of cases.

If this is good or bad, I don't know. First order generics are generally fairly weak, so I'm not really convinced Java's extended expressive power is that useful.

On the other hand C# has some serious problems with reflexivity of comparisons in subtype hierarchies, and their typing system allows overload driven "polymorphism" that behaves completely differently than override driven "polymorphism". A subtle point that I doubt many developers fully appreciate.

Sean

David Rupp said...

@Sean: Very nice. Thanks for pointing that out. And for reminding me that terms like "contravariant" exist. :-) I've run across it before, but I see I'm going to have to brush up.

Thanks all for the helpful (and civil) discussion.

Jon said...

Does this make sense why it shouldn't work?

public static void main(String[] args) {
ArrayList<Square> squareList = new ArrayList<Square>();
Rectangle r = new Rectangle();
...
addAnotherRectangle(squareList, r);

}

public static void addAnotherRectangle(Collection<Rectangle> c, Rectangle r) {
c.add(r);
}

Ricky Clarkson said...

In an immutable world, List[String] as a subtype of List[Object] works fine. Add mutation and you have a problem, conveniently demonstrated through Java's arrays:

Number[] nums=new Double[1];
nums[0]=5;

The above compiles, and gives an ArrayStoreException, because Java arrays know their type at runtime and do checks. So if the following was allowed:

List[Double] list=new ArrayList[Double];
List[Number] sup=list;
sup.add(5);

That would run fine, but the mutation (adding) has broken the original List[Double]. Java tries not to allow that in its generics.

I'd say the broken thing is either David Rupp, or mutability in programming languages. ;)

(no offence intended)

David Rupp said...

@ricky: Well then, I have to vote for mutability in programming languages. :-)

But seriously, folks. Take my IDE. Please.

I think your example of how arrays work makes my point: the error can't be detected at runtime, so it's deferred to runtime, when the JVM knows the actual type (Double[]) of the thing that is being treated as a Number[]. This is what I would expect the runtime type system to do.

What I would like is for the typing of generics to be consistent. If the thing I pass in to the argument that accepts a Collection<Number> is really a List<Double>, let me use it, for pity's sake! It's a Collection of Numbers! And if I try to do something stupid that violates the contract of the actual thing I passed in, well then you can let me know and I'll accept the consequences.

I understand that the current policy prevents me from making the kind of error you describe. But, as it happens, my method doesn't mutate the state of the collection. So the current policy also prevents me from doing reasonable work with my language of choice. Which is bad.

David Rupp said...

re: my last comment:

s/runtime/compile time/1

Ricky Clarkson said...

I think your intuition about how this works belongs more in a dynamically-typed language, because you actually want to choose a runtime error over a compile-time error.

You can use a List[Double] as a List[? extends Number] (meaning list of some number type or other), and then if your code happens to call numList.add(something) you will get a compile error. This is preferable to a runtime error, for me. What isn't preferable is that ? extends Number looks complex.

Eirik said...

Cédric's first comment was halpful, explaining how to accept subtypes at the element-level in a Collection.

However, what if one wants the generics to work at the Collection level? Here's a small example. Suppose one wants to calculate the average of the Integer elements of a Collection. Obviously, this would be as applicable to lists as to sets, and would be convenient to do with a single method.

The following method declaration does not work:

public Integer sum(Collection<Integer> c) {...}

Neither does the following:

public Integer sum(<? extends Collection<Integer>> c) {...}


The following will do the trick, but it's terribly unelegant:

public Integer sum(Anything<? extends Collection<Integer>> c)
  Integer retVal = 0;
  Iterator<Integer> it() = c.t.iterator();
  while (it.hasNext())
    retVal += it.next();
}

In addition one needs the following class:

public class Anything<T> {
  public T t;

  public Anything(T t) {
    this.t = t;
  }
}

This kind of does what I'm trying to do, but then every declaration and instantiation of a generic collection needs to mention the Anything class, and every reference to such a collection will need to refer to the .t variable of Anything in order to get access to the actual content.

Supporting notation like "public Integer sum(<? extends Collection<Integer>> c) {...}" would take away this problem, and I can't believe it would be hard to support. Mostly an issue of supporting the syntax, because the semantics are already supported, just not at the top level yet.