Generics: The Importance of Wildcards

Martin Bravenboer writes about generic wildcards in Java, and concludes that it is unfortunate that C# will not support wildcards or a similar mechanism.

Eric Gunnerson from Microsoft replies.

I was originally a type-erasure fan, but these days I am not so sure. I hope this turns into a fruitful discussion that helps me decide...

P.S

The Java paper was mentioned on LtU before.

By Ehud Lamm at 2005-05-26 20:05 | Software Engineering | Type Theory | other blogs | 5588 reads

Hairy details

While scanning Eric Gunnerson's blog

The key difference between C# boxing and Java 5.0 boxing is that C# boxes between primitive types and object, and Java does it between primitive types and the predefined wrapper types. This allows them to do implicit conversions both directions (an Integer and an int are pretty close in behavior).

There are some issues on this that have to do with object identity. Consider the following:

Map m = new Map(); m.add(3, foo); string s = m.at(3);
What does the third line do? Well, it turns out that the two 3 values arent the same because they are autoboxed to different reference types. That behavior is a bit surprising.

To improve the situation, theyve come up with an interesting modification, which I believe this is not part of the standard, but part of javac.

They get around this and Im not making this up by playing tricks for small integer values, but not for large integer values. They did not give an exact description for how this behavior is controlled.

Brwtfltlft? My god, I am thinking.... 31 bits....?

By marco at Thu, 2005-05-26 21:10 | login or register to post comments

Wow

Wow, talk about the blind flaming the blind. The problem with variance in both languages isn't type erasure versus runtime support, or wildcards versus pure generics. Neither writer seems to even understand the problem.

The problem is that both languages only expose mutable arrays. If they exposed read-only arrays (similarly to lists in Haskell), those would be covariant in C# and Java; and if they exposed write-only arrays, those would be contravariant.

But there is a solution that is more fundamental still: to separate arrays from mutable references entirely, so that arrays are always covariant. Then the type of arrays of integers is a subtype of the type of arrays of numbers, and the true source of the invariance is exposed: it is the reference type constructor (like IoRef t in Haskell) that is invariant.

Microsoft employs the greatest set of programming language researchers ever assembled; they should be able to do better than this.

By Tim Sweeney at Fri, 2005-05-27 02:03 | login or register to post comments

Maybe MS don't know that they do

... but they have great taste covered.

By Koray Can at Fri, 2005-05-27 02:29 | login or register to post comments

Orthogonal to type-erasure

I was originally a type-erasure fan, but these days I am not so sure. I hope this turns into a fruitful discussion that helps me decide...

Ignoring technical artefacts of the two platforms in question, is the adoption of wildcards really related to the choice for or against type erasure? Wildcards are just crippled existential quantification (with ad-hoc restrictions like "top-level" only "capturing" due to the desire of leaving quantifiers implicit). I see no fundamental reason why existential quantification couldn't be supported in a type passing framework like CLR.

By Andreas Rossberg at Fri, 2005-05-27 09:16 | login or register to post comments

Type deducible from call stack...

I am still going through the Java paper. Something I don't get [well, my life is like that ;-)]

In the cited paper on page 6 they discuss functional language parametric polymorphism.

This is what I understand from it for now:

They discuss a list example, continue to discuss ML's value restriction, and then discuss that, because of the side effects of an impure language, there are not enough static guarantees such that an application of a polymorphic function will be type-safe (because in a functional language this information is derivable from the stack?).

Que? This seems untrue to me. Should I read this as: we don't have enough enough information at JVM-class-load time to prove type consistency of the whole program? What is this stack stuff?

By marco at Fri, 2005-05-27 11:30 | login or register to post comments

Maybe they meant function call graph.

I agree... The stack is a runtime thing and cannot be used for static analysis. I think they might have meant function call graph, which is like a static description of all possible runtime stacks.

By Kannan Goundan at Fri, 2005-05-27 20:19 | login or register to post comments

Makes more sense

That would make more sense, at least to me. But then, ?assignments? making type inference hard? They must have meant something else.

[edit: snapped a comment everybody knows]

By marco at Sat, 2005-05-28 14:29 | login or register to post comments

Mutablity?

I also don't know what the exact type stuff has to do with mutability. I thought the reason you can't statically determine the exact type of something in an OO language was subtyping:

f (x : Boolean) : Shape {
   if (x)
      then return new Square()
      else return new Circle()
}

By Kannan Goundan at Fri, 2005-05-27 20:33 | login or register to post comments

mutability (somewhat) leads to the value restriction

The problem isn't in determining exact types; its in whether you can generalize an expression to have polymorphic type and retain a sound type system.

Essentially, people came up with a rule (for inferring a polymorphic type) that worked when you didn't have mutation, but then when they added mutation, that rule was no longer sound.

So Andrew Wright suggested the value restriction, which most ML implementations have adopted, I believe.

http://citeseer.csail.mit.edu/wright93polymorphism.html

(Other solutions were proposed in the research literature of that time, such as adopting an effect system to retain soundness. But the value restriction is really quite understandable, and the remarkable thing is that most programs already conformed to it.)

I didn't read the Java paper closely enough to know whether they were talking about this particular detail or not. But this is one place where mutability come into play with type inference.

By pnkfelix at Sat, 2005-05-28 15:30 | login or register to post comments

Ouch - generalization

Ha! thanks for the reference, I noted and somewhat understood ocaml's odd behavior but didn't read the paper with design decisions.

Still, it isn't about mutability, right? It seems it is the same question as: Can I stick \x -> x + 1 into a list of type [a->a]? (That was the thing I edited away above)

Dated 93, hmmm, I guess most people nowadays call this value restriction, well, a feature?

By marco at Sat, 2005-05-28 19:51 | login or register to post comments

Hmpf

Ah, now I get it. They were discussing exact typing vs subtyping in programming languages [wich also allow polymorphic types]. Seems to me that they got some stuff wrong in their reasoning though; as far as I know, you do have static guarantees in subtyped languages [even with polymorphism] and you don't need to carry around all type information [at run time]. Ah well, whatever.

[edit: didn't get it, it's about generalization, see argument above by felix]

By marco at Sat, 2005-05-28 15:33 | login or register to post comments

Lambda the Ultimate

User login

Navigation