Lambda the Ultimate

But the recursive Enum type is the one that really gets me: how could it possibly be any easier to understand? I think what we're seeing in this example doesn't really have anything to do with types; it has to do with most programmers' discomfort with inductive reasoning and recursion in general.

I must confess that I have problems with the Enum definition. What is the base case for the inductive definition?

Enum<T extends Enum<T>>

Seems like the equivalent of:

foo n = foo n

How does it work?

In Smalltalk the type of Class is Class Class. A hard concept to grok, but allows a powerful mechanism for reflection.

[on further reflection, I wonder if it is more akin to Recursive Functors. Oh well, just a thought.]

...it works because the enumerated type is finitary, and the induction is total, rather than relying on a statically-defined "base case." That is, the base case is when there are no more enumerations in the type, or when you hit the "empty type," or "bottom."

Though I think I understand why it is possible, do you know why they used that definition? The API shows that they use the type parameter in only one method:

Is that the only reason? Maybe the compiler-generated enum code uses it but since type information is not present in the bytecode, I can't use "javap" to see what that is.

This idiom appears in C++ as the "curiously recurring template pattern" and is used as a kind of substitute for inheritance when it is appropriate. It's not "obvious" the first time you come across it, but then, nothing interesting is :)

In C++:

template 
class base {
public:
  T* asDerivedClass() { return static_cast<T>(this); }
...
}

class derived : public base {
...
}

Then you can use asDerivedClass to safely get a pointer to the derived class. There are other uses too.

Kannan Goundan: Though I think I understand why it is possible, do you know why they used that definition?

No, I don't. The obvious reason would be because it's supported by the type system, concise, and has the feature that I like most about these kinds of type systems: once you understand the underlying principles, those principles apply relatively consistently throughout the system. But I guess this example is sticky, once again, because unless you already know a bit of the metatheory of subtyping, it might not occur to you that it's sensible to talk about an inductive definition without a supplied base case—that is, to talk about total induction, with the contextually-supplied base case being what type theorists call "bottom" in a subtyping context. But once you get a few chapters into TAPL, you find yourself doing a fair number of structural proofs with total induction, and once you get into subtyping, you encounter "bottom" essentially immediately. This observation, coupled with my earlier observation about most programmers not having even a passing familiarity with covariance and contravariance even though those concepts are crucial to a correct understanding of the popular object-oriented programming languages, is why I lack patience with the argument that programmers have done just fine without them: they haven't done just fine without them, these "new" features exist for reasons other than a desire to feel cool on the part of their designers, and simply reading a few chapters of a couple of books, say OOSC and TAPL, provides sufficient information to at least be able to engage in informed criticism of the concepts or the implementations of the concepts. Instead we get ill-informed nonsense like "Generics are a mistake" without any competent exploration of the design decisions that were made in their implementation in Java, or contrasting with languages that support parameteric polymorphism well, and yes, even in conjunction with objects. Instead, the reference is back to C++, another language that's known to be full of compromises of various kinds for reasons very similar to those in the Java case, and a throwing up of the hands. I suppose this might be red meat to the pre-Java 1.5 faithful, but it doesn't help address the issue of how Java might evolve to handle both its object model and its parametric polymorphism model in the future.

Instead we get ill-informed nonsense like "Generics are a mistake" without any competent exploration of the design decisions that were made in their implementation in Java, or contrasting with languages that support parameteric polymorphism well, and yes, even in conjunction with objects.

First, the claim "Generics are a mistake" in the original article is being made specifically in the context of Java 5. I expanded the scope somewhat in posting it here, because similar issues arise in C++, with one big common factor being mainstream OO languages that had generics tacked on after the fact. The fact that there are languages that support parameteric polymorphism well doesn't really affect the original claim, although I realize that may not have been obvious.

More importantly, calling such complaints "ill-informed nonsense" makes the mistake of interpreting the argument as an entirely PL-theoretic technical one. It's not. Ken Arnold raised the issue of the complexity budget, asking if the benefits are worth the problems. "Problems" don't only include things that are theoretically wrong, but can also include things that make programmers unhappy and/or less effective, which has a cost. There's an economics issue as well as issues of taste and preference here.

Similar issues have tended to ensure that C++ gets used as a language of last resort, rather than a language of choice. As Java grows in complexity, it may face a similar situation. Are we just seeing transition pains of the sort described by Tim Bray, or are we watching canaries keel over?

Ken Arnold's article certainly wasn't an in-depth technical critique of Java's generics. Keith Lea posted a wishlist in What Java generics needs which includes some nice examples of the way in which the weakly-inferenced generics syntax can obscure code. I consider this kind of stuff to be almost worthy of a Fox special, "When type systems attack". But I get the impression you're acknowledging some of this:

I suppose this might be red meat to the pre-Java 1.5 faithful, but it doesn't help address the issue of how Java might evolve to handle both its object model and its parametric polymorphism model in the future.

Examining problems that real users encounter is an important first step, surely?

Anton van Straaten: First, the claim "Generics are a mistake" in the original article is being made specifically in the context of Java 5.

I would say that this is only the case implicitly, because my criticism of the article is precisely that it doesn't go far enough in situating the rather strong statement that "generics are a mistake," which is, after all, a direct quote, in the context of the trade-offs against backwards compatibility with existing Java code that relies, e.g. on arrays being covariant. That is, the quote isn't "Generics interact poorly with these other features of Java, so there's a question as to what should change, generics or, painfully, these other features." The observation that there's a complexity budget that you want to minimize expenditures from is a good one, but my reading of the article is that only generics were perceived as drawing on that account, rather than the admittedly complex web of Java language features, of which covariant arrays and generics are both strands.

Anton: I expanded the scope somewhat in posting it here, because similar issues arise in C++, with one big common factor being mainstream OO languages that had generics tacked on after the fact. The fact that there are languages that support parameteric polymorphism well doesn't really affect the original claim, although I realize that may not have been obvious.

Here's where I have to respectfully disagree: the observation that Java and C++ had parametric polymorphism bolted on ex post facto, and that there are languages that lack the issues of C++ and Java, dramatically affects the original claim by shifting it from "generics are a mistake" to "the current combination of generics and other Java language features don't interact as well as isomorphic features in some other, less popular, languages. How might we be able to revisit some of those interactions in 1.6 or 2.0?" Now, you can make an argument, I suppose, that that is actually what the article was attempting to do, but that would be a very different reading than I got from it.

Anton: More importantly, calling such complaints "ill-informed nonsense" makes the mistake of interpreting the argument as an entirely PL-theoretic technical one. It's not. Ken Arnold raised the issue of the complexity budget, asking if the benefits are worth the problems.

Yes, and again, this is a good thing, but the only variable that the article seems to address is the presence or absence of generics. I suppose my criticism boils down to the article conflating two totally different complexities: the one-shot complexity of learning enough about covariance and contravariance for the array issue to be comprehensible, and the existential complexity of the array issue arising from Java's historic use of covariant arrays being coupled with the introduction of generics. Generally speaking, when you talk about "balancing a budget," you recognize that there are N things that you wish to have, and you might not be able to afford all of them. The article seems structured to me as if to ask "can we afford generics?" as if there were no other costs on the table and the cost of generics were inherent. While I completely understand the desire not to put, e.g. the cost of revisiting covariant arrays on the table, it strikes me as at least intellectually dishonest not even to observe that the presence or absence of that cost has a direct effect on the complexity cost of generics. But of course, before you can even have that conversation, you have to understand the interaction between covariant arrays and generics, and it's not clear from that article that Ken Arnold does, so we're back to my concern about what critics of generics in Java do or don't know about type theory when formulating their criticisms.

Anton: Similar issues have tended to ensure that C++ gets used as a language of last resort, rather than a language of choice.

Boy, I wish I could agree with that statement. I've seen a lot more software that was written in C++, and shouldn't have been, than the converse!

Anton: As Java grows in complexity, it may face a similar situation. Are we just seeing transition pains of the sort described by Tim Bray, or are we watching canaries keel over?

An excellent question. Given that we're at the 10-year mark since Java's introduction, would a new popular language arising necessarily mean that Java had gotten too complex, or would it merely reflect the roughly-typical cycle for new language adoption? Of course, this just begs the question as to what motivates new language adoption in the first place.

Anton: I consider this kind of stuff to be almost worthy of a Fox special, "When type systems attack". But I get the impression you're acknowledging some of this... Examining problems that real users encounter is an important first step, surely?

Absolutely. I strongly believe, however, that part of the process is to help those users separate out distinct concerns and address them individually. To reiterate, if we want to say that covariant arrays in Java are inviolate, that's fine, I guess, but let's at least acknowledge that we're doing that and that it imposes a complexity cost on generics that doesn't have to be there. Otherwise the "discussion" of the complexity cost of generics is just hand-waving.

most programmers not having even a passing familiarity with covariance and contravariance even though those concepts are crucial to a correct understanding of the popular object-oriented programming languages

I think you would find that anyone who programs in Java DOES have a full intuitive familiarity with covariance/contravariance over methods, even though they don't use those technical terms.

A programmer proficient in such a language knows that a parameter to a method can be any subtype of the stated type, and that the return value can be use as any super type of the stated type, without even thinking about it.

What neither Java programmers nor Haskell programmers are used to is how polymorphism imposes covariant/contravariant restrictions across the WHOLE TYPE in the presence of sub-typing.

So even though I have studied the theory, the first time someone asked me why a List<Integer> is not a subtype of List<Number>, I had to think about it quite a bit before it clicked in.

Given that we still haven't taught most Java programmers why they shouldn't go wild making everything static, I think it is a bit much expecting them to develop intuitions that a PLT geek has to think twice about. ;-)

Instead we get ill-informed nonsense like "Generics are a mistake" without any competent exploration of the design decisions that were made in their implementation in Java, or contrasting with languages that support parameteric polymorphism well, and yes, even in conjunction with objects.

Remember that most people are mainly interested in getting useful work out of the languages they know, not exploring the theory and design philisophy of their PL. (That's just us. ;-) )

If you said that what really needs to happen is that a new, redesigned-from-the-ground-up Java should be designed that is not fundamentally broken, include generics as a fundamental feature, and Sun should push it as the next big thing, well, I couldn't agree with you more. ;-)

But I think the existing implementation of generics in Java just doesn't given enough bang for the complexity buck.

[Lots of good stuff elided...]

Marc Hamann: What neither Java programmers nor Haskell programmers are used to is how polymorphism imposes covariant/contravariant restrictions across the WHOLE TYPE in the presence of sub-typing.

Really? This is pretty common knowledge in the O'Caml community. Perhaps due to the issue being forced by O'Caml's inclusion of inclusion polymorphism? :-)

Marc: Remember that most people are mainly interested in getting useful work out of the languages they know, not exploring the theory and design philisophy of their PL. (That's just us. ;-) )

While there's a great deal of truth to this, my thesis, if you will, is that there comes a point at which you have to explore more theory in order to do more useful work with the tool. Thankfully, in this particular instance, it isn't even that hard to do: you can indeed start with the observation that function arguments are contravariant and function results are covariant, and use that to motivate an investigation of arguments and return values of generic type, and what happens in the presence of arrays. That is, we can (and, I believe, should) leverage the observation that there is already an intuition about contravariance and covariance—the issue at hand is merely that the intuition is incomplete, not that it's mistaken.

Marc: If you said that what really needs to happen is that a new, redesigned-from-the-ground-up Java should be designed that is not fundamentally broken, include generics as a fundamental feature, and Sun should push it as the next big thing, well, I couldn't agree with you more. ;-)

Short of that, I think it's worth discussing what, if anything, should be done differently in Java 1.6 or 2.0 or whenever, and it's hard to do that if some of the folks in the discussion—and I hasten to point out that I don't know whether Ken Arnold or anyone else falls into this category or not—don't even know that there's a covariance/contravariance issue with arrays. The fact that I couldn't tell whether Ken Arnold is aware of that from the article is actually my only real complaint about the article! I certainly don't have an issue with him raising the question. I merely find "Generics are a mistake" to be quite a bit too strong and to neglect treating the balance of the new feature vs. maintaining backward compatibility in the type system.

Marc: But I think the existing implementation of generics in Java just doesn't given enough bang for the complexity buck.

I haven't used Java 1.5 myself, and so far, arrays of generics are the only area in which there seems to be confusion, so I can't say that I agree with this, but neither can I say that I disagree with it. Are there other issues that you're aware of that make Java 1.5 generics seem like they have too many corner cases/exceptions, or just generally work in a counterintuitive fashion?

Really? This is pretty common knowledge in the O'Caml community. Perhaps due to the issue being forced by O'Caml's inclusion of inclusion polymorphism? :-)

This is part of my point: you have to evaluate an addition to a language based on how it interacts with the existing features and expectations of its proficient users.

OCaml was designed from inception with this kind of type system, so it is better integrated with the language as a whole.

With Java, its a makeshift bandaid on a gaping wound.

Are there other issues that you're aware of that make Java 1.5 generics seem like they have too many corner cases/exceptions, or just generally work in a counterintuitive fashion?

The Keith Lea piece that Anton recommended gives a good flavour of the problems. Mostly annoying details of syntax or implementation limitations.

One additional big problem is the choice of type erasure for generics.

Given that I'm on record as being "anti-meta", this might seem an odd quibble coming from me, but given that reflection is widely used for various frameworks and libraries in the Java world, it would have been nice if they could at least be made consistently type safe by having generics available at runtime, the way all other type information is in Java.

Independent of this problem, this choice can be condemned on the basis of inconsistency: it is yet another special case you have to understand to use generics properly.

(As a side note, anyone who justifies bad design choices in the name of backwards compatibility deserves the criticisms they get.)

I think you would find that anyone who programs in Java DOES have a full intuitive familiarity with covariance/contravariance over methods, even though they don't use those technical terms.

A programmer proficient in such a language knows that a parameter to a method can be any subtype of the stated type, and that the return value can be use as any super type of the stated type, without even thinking about it.

But that's is not what variance is about! Variance is a property of type constructors. In OO variance primarily comes into play when you ask about what method type is a subtype of another one - not just how you use the argument or result in isolation. Usually this is relevant in OO only when you consider how WHOLE object types relate. And as you noticed, most programmers don't grok that anymore. Hence they indeed don't grok variance.

And no, variance issues do not only arise in the presence of polymorphism.

But that's is not what variance is about! Variance is a property of type constructors.

But that's not what variance is about! Variance is a property of functors, of which type constructors are a puny, insignificant practical application.

We shouldn't let programmers write even a "Hello World" program until they complete a Ph.D in a purely theoretical branch of category theory.

That will make the Java implementation of generics good.

;-}

You claimed that programmers had an intuitive understanding of variance. But the examples you gave did not support that claim, they rather contradicted it.

In all mainstream OO languages, where subtyping is nominal, variance is completely irrelevant for understanding plain subtyping like you rely on for argument passing - which was your example.

OTOH, the scenario you described were programmer's alleged intuition begins to fail was extactly were variance starts to come into play.

I don't see how your reply relates to any of that. And I have to agree with Paul that most programmers don't have the slightest clue about variance. Sometimes not even the so-called experts - consider Eiffel.

Whether this is a problem with people, or a problem with subtyping, I'm not so sure.

My apologies if you were offended by my post; I was going for a playful rather than a sarcastic tone.

The serious point about variance underlying the frivolity is that it is quite a general concept: any mapping between arrows either preserves or reverses direction. As such the terminology has many uses.

One such use, as evidenced by Pierce in TAPL, is in describing the subtype relation, taken as arrows in a poset, as they map to the subtype relation on function types. If S1 <: T1 and T2 <: S2, then S1 → S2 <: T1 → T2. The reversal of the relation in the codomain is referred to as contravariant.

This effect as you point out happens more generally in quantified types, and my first intuition is that it is an effect of any kind of binding in the presence of subtyping.

So my original contention that a proficient Java programmers has of necessity an intuitive understanding of at least one form of contravariance still applies.

Hopefully, you will not find that I have swung too far from silly to pedantic in my response. ;-)

Marc Hamann: So my original contention that a proficient Java programmers has of necessity an intuitive understanding of at least one form of contravariance still applies.

I would agree with this—I haven't run into any programmers who have difficulty with a simple-minded description of arguments being contravariant and return values being covariant. Usually I just get questions about why the highfalutin' terminology. :-) But then when the subject moves past arguments and return values and gets into subtyping and parametric polymorphism, the value of the precise terminology generally becomes more apparent.

That's really all I was trying to say earlier: it's much easier to discuss issues like array of generics in Java with just a little bit more information than most programmers have. How many working Java programmers even can tell you, off the top of their heads, that String[] is a subclass of Object[]? Of those, how many can tell you that that's "covariance?" Of those, how many can tell you that generic containers aren't covariant? And so on. Raise those numbers, and (IMHO) you can have a much more productive conversation about how to address whatever issues there might be in Java generics.

"If S1 <: T1 and T2 <: S2, then S1 → S2 <: T1 → T2. The reversal of the relation in the codomain is referred to as contravariant."

"If T1 <: S1 and S2 <: T2, then S1 → S2 <: T1 → T2. The reversal of the relation in the domain is referred to as contravariant."

"If T1 <: S1 and S2 <: T2, then S1 → S2 <: T1 → T2. The reversal of the relation in the domain is referred to as contravariant."

Absolutely right. Thanks for the catch!

this is the Java Generic FAQ entry about Enum.
It is peculiar imho, but I'm not an expert.

Earlier versions of GJ would not let you do this: you could not refer to a type variable in its own bound. One of the reasons we built/designed Jiazzi (OOPSLA 2001) was so we could have some form of self typing in Java, which we couldn't do with GJ at the time.

Adding self types to Java in a more elegant way would be better, even if it was just syntactic sugar. For example, Java could define THIS as a keyword, which resolves to an implicitly resolved type variable that is always bound to the actual type of the object.

Is there any advantage in implementing it in terms of generics? It seems like this feature might even require a special-case in the implementation! Does anybody know whether this is true?

The fact that Object.clone() doesn't use this trick only adds to the confusion. After all, the self-typing for enums is merely used to obtain more accurate typing for getDeclaringClass() which is only used for reflection. I'd consider proper typing on Object.clone() to be a much higher priority (though you'd need the type parameter to default to Object to avoid breaking existing code).

A "this" type would be very welcome. The generics trick is clearly an abuse of the type system that adds type parameters where they are not really necessary.

The problem, as far as I can tell, is that most popular languages don't force the programmer to have even a passing familiarity with covariance and contravariance

worse, no-one is using those terms. i'm at javaone now and yesterday went to an appalling presentation on the new features in java 1.5 - "covariant" was mentioned once, and it wasn't related directly to generics. there was no way i could have gone from that meeting and known that reading up on co/contra-variance would help me understand the issues, unless i already knew them (which i did thanks to eiffel - my notes say "eh?! must read up on co/contra-variance").

incidentally, annotations are having a huge (positive) impact, and ejb3 makes j2ee a lot more sane. so the changes are generally for the better.

(but there are wrinkles, i think - is the issue with T[] mentioned in the link "the standard example of why [...] arrays of generic type are problematic" (which i assume is that you can both read from and set them, so want co and contra variance together) or is it related to implementation by type erasure and/or a possible lack of empty constructors?)

(but there are wrinkles, i think - is the issue with T[] mentioned in the link "the standard example of why [...] arrays of generic type are problematic" (which i assume is that you can both read from and set them, so want co and contra variance together) or is it related to implementation by type erasure and/or a possible lack of empty constructors?)

The article
Arrays in Java Generics has some discussion of this. [Edit: of a Java-specific quirk in this area, that is.] Summarizing, ordinary Java arrays are covariant, e.g. Object[] is a supertype of String[], but generic collections are not, e.g. LinkedList<Object> is not a supertype of LinkedList<String>. The type erasure issue also plays into this: arrays carry runtime type info, but generic collections do not.

andrew cooke: is the issue with T[] mentioned in the link "the standard example of why [...] arrays of generic type are problematic" (which i assume is that you can both read from and set them, so want co and contra variance together) or is it related to implementation by type erasure and/or a possible lack of empty constructors?

I was thinking specifically of mutable arrays manifesting type-invariance, as I alluded to in referring to Tim Sweeney's comments about that exact issue in another thread—I should have been more explicit about that rather than assuming that it was obvious. But you raise good points regarding type erasure and nullary constructors that I need to give further thought to.

We could all start programming in Scala or Nice.

"The more interesting your types get, the less fun it is to write them down." — Benjamin Pierce

skybrian: That's not a problem; it's a feature, and it's why the languages became popular in the first place.

"Everything should be made as simple as possible, but no simpler." — Albert Einstein

Your observation is obviously true, but only to a point: Barbara Liskov didn't come up with the Liskov Substitutability Principle to show off. Bertrand Meyer didn't discuss covariance and contravariance ad nauseam in "Object-Oriented Software Construction because writing is fun. The damage in some languages and systems from not paying attention to issues of contravariance and covariance is real and well-documented. Sometimes it's mattered in practical terms, sometimes it hasn't—as has been discussed here before, that's basically an economic question.

skybrian: The purpose of a practical programming language isn't to force people to learn mathematics or to show off how clever you are. It's to hide complexity so that ordinary people can get the job done without having any mathematical sophistication whatsoever. The language designers sweat this stuff so the users don't have to. If Java programmers haven't had to learn something, it shows that the language designers did their job well (up until recently).

Not necessarily, by which I specifically mean that they might have done their jobs well under a certain set of assumptions, namely that Java would never have parametric polymorphism. But to the extent that Java's evolution has, from the outset, tracked that of C++, the hand was already writing on the wall: C++ couldn't avoid parametric polymorphism, and there are good reasons why Java ultimately couldn't either. So with that realization behind us, Anton nailed one good example of how Java's initial designers painted themselves into a corner earlier in the thread: Java arrays are covariant, but generic collections are not. Oops.

But to me, the more general issue in language design is almost completely philosophical: there's intense pressure, which I think I've just inadvertently reinforced :-), for the evolution of a programming language to be monotonic. But real progress can't always be monotonic; in order for it to be we'd all have to be omniscient. That is to say, Java's designers would have had to, from day one, have said "someday we'll want parametric polymorphism" and that might have led them to, e.g. reject making String[] an extension of Object[], among other things. But they didn't, and now they have a "ginormous," as my stepson would say, installed base, so they can't very well say "Remember when we said that all arrays were subclasses of Object[]? We lied." So we get "complexity," which looks an awful lot like non-orthogonality to me, and people wonder whether this "generics" stuff is really all that useful, thinking that the problems with its implementation in Java are inherent, just like the C++ community did with templates and their trade-offs in C++.

So I guess this really gets me closer to my answer to Anton's question: is there a benefit to the functional languages and their bread-and-butter approach to parametric polymorphism over Java and generics? Apparently I believe that there is, if for no other reason than that these languages were designed from the ground up with parametric polymorphism, and so exhibit a pleasing orthogonality ("lack of complexity"). Then you have the example of O'Caml, which has a powerful module and object system as well as parametric polymorphism, again all nicely orthogonal. Think of it as a proof by demonstration that the kinds of issues that you find in C++ and Java are avoidable. As Guy Steele pointed out in an interview about Fortress, it's not hard to create a technically-competent programming language. What's hard is to craft a language that hangs together in such a way that it doesn't end up having a bowl cut and bolts sticking out of its neck (this is my formulation, not Steele's). :-)

I assume the reasoning process went like this:

1. With v1.5 Java has become inconsistent and confusing.
2. With v1.5 came generics.
3. Generics are inconsistent and confusing

The root causes are actually covariant arrays and type-unsafe downcasts. Generics merely brought the problems to the surface and, as a result, looks like the cause.

"C++ couldn't avoid parametric polymorphism, and there are good reasons why Java ultimately couldn't either."

They did, in fact, avoid it for 9 years. There was nothing to stop them from avoiding it for longer - we could have happily (for the most part) continued to cast everything that comes out of collections. I'm glad they didn't, but it was a viable choice.

skybrian: They did, in fact, avoid it for 9 years. There was nothing to stop them from avoiding it for longer - we could have happily (for the most part) continued to cast everything that comes out of collections. I'm glad they didn't, but it was a viable choice.

Of course that's true in some narrow technical sense, but the historical fact is that both the C++ committee and Sun decided that the monumental effort of integrating parametric polymorphism into their exisisting languages, which were not designed with parametric polymorphism in mind, was worth it. Why do you suppose that is? Let me assure you that it wasn't because they were bored. The demand for it from the developer community in both cases was enormous, and that demand wasn't novelty based, but rather was very pragmatically driven, even if the driving force wasn't anything more "sophisticated" than type-safe containers. But all of this is a matter of public record, both for C++ and for Java, if you care to read the various postings on the subject.

I can't speak for C++ developers, but lord knows the C++ language includes all sorts of bad ideas. Anyway, we were talking about Java, and I don't see this "enormous demand" in the public record. In fact, this isn't the first time someone criticized the generics implementation - Bruce Eckel's been loudly against them and Tim Bray has said he doesn't fully understand them. The typical Java developer's reaction I've heard is, "All this just to avoid a few casts? It's not like we get a whole lot of bugs from ClassCastExceptions."

The Java community is quite conservative. I'm considered bleeding-edge for using Java 5 so soon and it's already been out for a year. Many Java developers are just starting to kick the tires now, which is why we're having this conversation now. If this were more than a nice-to-have, you'd think more people would have switched sooner.

Sun often gets pretty far out in front of the Java community on new features - they are often forward-looking rather than customer-driven. (And a good thing too - many Java programmers have no taste.) In particular, the generics implementation in Java has been more research-driven than customer-driven. It's based on research prototypes such as pizza and gcj, with improvements made by a standards committee.

skybrian: I can't speak for C++ developers, but lord knows the C++ language includes all sorts of bad ideas.

C++ reflects the set of constraints that it was sometimes deliberately, sometimes not developed under (cf. "The Design and Evolution of the C++ Programming Language"). C++ is still the only game in town if you want a multiparadigm language that you can talk to the hardware with, and trust me when I tell you that I grind my teeth every time I say that. It doesn't make it any less true. In any case, I wasn't holding C++ up as a paragon of virtue, but rather for what it is as a matter of history: the point of departure for Java.

skybrian: Anyway, we were talking about Java, and I don't see this "enormous demand" in the public record.

Go back on "The Server Side" for a couple of years before 1.5 came out, then there's the JCP materials around when generics showed up on the radar at Sun, then there are the communities around Pizza and GJ (and you have to somehow count the folks who would have liked to use Pizza or GJ but couldn't/wouldn't because they weren't standardized), and so on. It was a big issue for the entirety of the time—about eight years—that I slung Java for a living. It's out there, but I don't doubt that self-selection on both of our sides will color our perception of its scope.

skybrian: In fact, this isn't the first time someone criticized the generics implementation - Bruce Eckel's been loudly against them and Tim Bray has said he doesn't fully understand them.

I could find a lot more than two people who criticized, and continue to criticize, C++ templates, too. That doesn't mean that there wasn't enormous demand for parametric polymorphism in the language.

skybrian: The Java community is quite conservative. I'm considered bleeding-edge for using Java 5 so soon and it's already been out for a year. Many Java developers are just starting to kick the tires now, which is why we're having this conversation now. If this were more than a nice-to-have, you'd think more people would have switched sooner.

I think we all understand that adoption of new versions of a language, with new features, exhibits a Zipf distribution. We call the short initial arm "early adopters" or "pioneers," complete with imagery of arrows in their backs. Your characterization of the Java community matches my experience, but my experience has also been that the bigger and more complex the projects got, the less tenable the "treat things with complex lifecycles as Objects and cast as necessary" became. Generics give you one more thing the compiler can tell you about when you screw it up, and remember, unlike the Lisp or Smalltalk communities, the Java community already wants this, for the most part. Of course, they also still want runtime-checked downcasts, too.

skybrian: Sun often gets pretty far out in front of the Java community on new features - they are often forward-looking rather than customer-driven.

Totally honestly, you're the first person I've ever heard make that claim, and I have to completely disagree.

skybrian: n particular, the generics implementation in Java has been more research-driven than customer-driven. It's based on research prototypes such as pizza and gcj, with improvements made by a standards committee.

The Pizza and GJ efforts weren't academic research and weren't intended just to prove a point; they were intended to address a demand that Sun, at the time, wasn't addressing. The efforts came from researchers because those researchers knew the type theory necessary to do the job. As we've already established, the principal reason we're having this conversation is because of some implementation corners that the generics team couldn't resolve without breaking backward compatibility in a way that was identified as being unacceptable to the community. Don't be fooled: just because something gets proof-of-concept'ed by researchers before it gets commercially distributed doesn't mean that the point is research. The world is full of commercial systems that were built without sufficient theoretical underpinnings and exhibit a level of defect and even incoherence that reflect the fact. The generics team at Sun, and the Pizza and GJ teams before them, made a concerted effort to make Java-as-we-know-it-today and parametric polymorphism make sense together, and if arrays-of-generics are the only sticky point (and the recursive Enum definition, which works as you'd expect but might just not be an intuitively obvious definition to the average Java programmer), I'd have to say that they succeeded admirably.

I also think they succeeded. I think we mostly understand each other's positions, so I'll just make some clarifications:

Regarding demand, I think we're just quibbling over the word "enormous". I agree that generic types have been a prominent member on the Java wish-list almost since 1.0. I would reserve "enormous demand" for things that frustrate people enough to make them consider switching to other languages, like overly complex UI classes, large footprint, performance (in the early days), and excessive memory usage. I don't think there were many people who switched or considered switching because Java's type system was too weak for them. The communities for languages with better type systems have always been pretty small, no matter how compatible they are with Java.

It's true that commercial software is often very complex, but if someone in that situation asks my advice, upgrading to Java 5 is pretty far down the priority list. Most of the complexity I've seen is self-inflicted. There are all sorts of ways to make Java code hard to read, such as programming as if you were writing in C or C++, not structuring code into classes that match the problem domain, writing convoluted code for "performance" without even measuring whether it's any faster, using inappropriate frameworks, and so on. Putting in generic types can help as a first step when clarifying bad code, but refactoring it to be properly object-oriented helps a lot more.

When I said Sun is forward-looking, I was just being nice about the fact that they sometimes spend a significant effort building and promoting things for which I see little real demand. Some old examples: JavaSpaces, JINI, or writing Java3D instead of just providing standard OpenGL bindings. I also think it's fair to say that some things make it into Java when demand for them is only luke-warm. So the fact that Sun added something doesn't prove that a large community was demanding it.

In comment-7382, skybrian wrote:

Bruce Eckel's been loudly against them

Just for the sake of completeness, here's an xref to Bruce Eckel's followup to Arnold's piece.

It doesn't use subsumption. An expression must be explicitly coerced to a supertype to be treated as such, with :> operator.

Parametric polymorphism often avoids the need to use such coercion at all, so this is not as bad as it might sound to someone accustomed to Java.

BTW, OCaml doesn't have downcasts at all, which makes the type system less expressive in this respect than the one of Java.

Qrczak: BTW, OCaml doesn't have downcasts at all, which makes the type system less expressive in this respect than the one of Java.

Although it has been implemented as a syntax extension using camlp4.

Polymorphic subtyping in O'Haskell gives an overview of the type system of O'Haskell and has quite a few references to reading material.

Abstract for the article:

O'Haskell is a programming language derived from Haskell by the addition of concurrent reactive objects and subtyping. Because Haskell already encompasses an advanced type system with polymorphism and overloading, the type system of O'Haskell is much richer than what is the norm in almost any widespread object-oriented or functional language. Yet, there is strong evidence that O'Haskell is not a complex language to use, and that both Java and Haskell programmers can easily 1nd their way with its polymorphic subtyping system. This paper describes the type system of O'Haskell both formally and from a programmer s point of view; the latter task is accomplished with the aid of an illustrative, real-world programming example: a strongly typed interface to the graphical toolkit Tk.

I am trying to grasp the difference between the O'Haskell and O'Caml manner of type inferencing. Anyone got some basic insights into their differences?

Not for beginners, but then, what of TAPL is?

Not sure I agree with this sentiment, depending on what you mean by "beginner". For someone with some basic mathematical and computational sophistication who wants to learn about the fundamentals of type theory for programming, I don't think they could find a better introduction.

Sure, there are going to be challenges, since the subject matter is quite rich, but the step-by-step introduction and motivation of notation, methods and concepts, laid out in an exactingly consistent format, is simply the clearest, gentlest presentation of the material I have seen.

I wish TAPL had been around when I was a beginner so that I could have avoided learning type theory (and all its supporting notation and math) the hard way. ;-)

My copy arrived two days ago. So far I'm delighted with it...

Excellent! When you're done, Advanced Topics in... awaits you. :-)

What I was attempting to say, and failed to, is that if you wish to understand how inclusion polymorphism and parametric polymorphism can be accommodated in a single language, TAPL does answer the question, but the information is a) not in a single chapter, and b) relatively sophisticated: a beginning reader will not likely be able to "skip the earlier chapters" and just read the Subtyping section with any understanding.

I wholeheartedly agree that TAPL is a must-read for anyone with any interest in programming languages at all, but then, I've written that before. :-)

So what you're essentially asking for is a kind of "for dummies" explanation of inclusion polymorphism and parametric polymorphism. Now, I'm not entirely sure that is at all possible. It would be interesting to see an explanation which a) fits in a single chapter, and b) is not sophisticated. This kind of stuff is rather sophisticated and you have to make sure the reader has the right background knowledge in order to grok it. If you make the explanation too short you will have to assume a whole lot and then it is not a beginner's text any more.

But I do encourage you to write up a "for dummies" version if you feel you can do it. I agree it would be much needed.