Lambda the Ultimate

inactiveTopic Variance in Java Generics
started 5/29/2003; 12:59:42 PM - last post 5/30/2003; 6:52:39 AM
Ehud Lamm - Variance in Java Generics  blueArrow
5/29/2003; 12:59:42 PM (reads: 2114, responses: 2)
Variance in Java Generics
This link was posted to the discussion group and while I haven't really had the chance to explore this in any detail, the proposal sounds interesting.

I'd like to hear more, if anyone has any thoughts he'd like to share.

Posted to OOP by Ehud Lamm on 5/29/03; 1:01:42 PM

Daniel Bonniot - Re: Variance in Java Generics  blueArrow
5/30/2003; 4:41:52 AM (reads: 970, responses: 0)
Are the variance annotations (+,-,*) syntactic sugar for the parameterized versions, or do they involve a modification of the type system?

The syntactic sugar I have in mind is:

+T is replaced by a fresh type variable Tn, added to the type parameters of the method with the constraint Tn extends T.

-T is replaced by a fresh type variable Tn, added to the type parameters of the method with the constraint T extends Tn.

* is replaced by a fresh type variable Tn, unconstrained.

Ah, I see a problem for -T: since GJ has only upper-bounded polymorphism, you could express it: static <T> foo(-T, -T); would be desugared into static <T0, T1, T extends T0 AND T1> foo(T0, T1); There is no way to express this in GJ, right?

Provided arbitrary constraints, is this desugaring a correct (equivalent) formalization of the variance proposal?

The two PDF documents in the distribution gives no formal description of the type system. I suppose one should read the research paper by Igarashi and Viroli (it's in the references of the whitepaper, but not even mentioned...)?

On a related note, this proposal does not seem to include the possibility to declare covariant classes. Or did I miss it?

(BTW, why did the "notify me by email" checkbox disappeared?)

Daniel Bonniot - Re: Variance in Java Generics  blueArrow
5/30/2003; 6:52:39 AM (reads: 958, responses: 0)
There is a section in the Ecoop2002 that compares with parametric methods. To summarize: 1) Yes, variance can often be obtained by using type parameters. 2) For contra-variance, it requires 'extendedby', that is, lower-bounds. They say this domain is little studied (hum, hum). 3) Some cases cannot be expressed by variance, and need type parameters. Namely, to express type dependencies between method arguments and results. 4) To conclude, a language should have both, "to achieve even more power and expressiveness".

They illustrate this last point with a method that uses both features. However, it turns out that you could write it with bounded type parameters only. Here is the code in Nice (changing some method names to match the JDK):

// Pair in not in the JDK, so we add it here.
abstract class Pair<A,B>
  A getFst();

<X, Xminus, A, P | Xminus <: X, P <: Pair<Xminus,A> > Vector<X> unzipleft(Vector<P> vp) { Vector<X> v = new Vector(); for (int i = 0; i < vp.size();i++) v.add(i, vp.elementAt(i).getFst()); return v; }

True, the type parameters are quite hard to read. That's where syntactic sugar comes handy (I got it right simply by applying the above desugaring to their code). But they don't show how variance adds any expressiveness. Actually, I doubt it does.

So it all really gets to point 2. If you want contra-variance (and I agree it is useful), then you need at least lower-bounds. The original GJ proposal does not have it. So they chose to add an ad-hoc extension to deal with variance. It's a reasonable choice, but I am not sure it is the best. The type system is becoming an accumulation of partially overlaping features ("because we needed them!"), which makes it more difficult to understand as a whole, and more open to fundamental errors that might go unnoticed for a while (the first GJ specification was unsound, and it took time to find it out). The more constructs you add, the more likely that some surprising interaction occurs. It will be interesting to see if they decide to add this to Java 1.5 or not.

Personally, I prefer to start with a slighly more powerful system that has been known to be sound for a long time (7 years for ML-sub). When needed, it is always possible to add some syntactic sugar to help solving a particular, common problem, without fearing that it might break the whole type system. It was already considered to add sugar like + for method types in Nice, I suppose this proposal will make it happen faster! :-)