9-27-04 Puzzling Through Erasure IV

One thing that Neal pointed out was that even though I had discovered a particular programming idiom in the Java libraries, he had been sloppy when writing that code and so we shouldn't actually do that. I have added a new weblog entry to address this. I also added a note about the "type injection" idea to address one of Neal's points.

The answer to "Why do we have erasure?" is called "Migration compatibility." This means that the new generic version of an API is compatible enough with the old version so that existing clients will continue to compile (for source) and run (for binaries).

So the problem is that you want the same library to look both generic (for new code) and non-generic (for old code). To satisfy this, the compiled code must therefore be the least-common denominator: non-generic. Thus, erasure.

Having written that, my brain is saying "but, but ... why would it be so bad to have two versions of the libraries, the generic and the non generic? Then people who are ready to move to generics can, and those who don't want to have legacy code." Of course, I'm only imagining the Collections library when I think of it this way, but in truth generics are shot through much of the Java libraries. So we would be talking about maintaining two different versions of the Java standard libraries for all time to come. I wouldn't wish that on anyone.

Neal's example of companies A, B and C and their individual issues with migrating to generics reminds me of the "Diamond Problem" with multiple inheritance. You have to stare and think about it for awhile before it becomes clear, but once it does, it stays clear (Perhaps a diagram would help illuminate things with that example?). I haven't quite gotten over that hump yet, but I'm starting to get glimmerings of it. I think it comes down to what I said before: if it's a least-common denominator then everyone, old and new, can play.

I'm also unresolved about two issues:

1. The assertion that erasure was the only way to solve this problem. It would probably take a theoretical mathematician to prove this one way or another, but looking at the real world, the second unresolved issue also brings erasure into question:

2. The continuing assertion that something about .NET generics is not going to be "migration compatible." In our interview last summer, Anders Hejlsberg went into great detail about issues of versioning and I have so far seen no indications of any version compatibility problems, migration or otherwise. I'm waiting to hear from Anders about these issues, and will post it here when I do.

In the midst of discussions about the Java Generics effort, I've come to realize that there are at least two major issues that must be observed about the decision-making process:

1. The forces that Neal et. al. (although, if I understand correctly, Neal is the sole compiler writer; but from his comments it sounds like he is also responsible for some of the libraries) must contend with. I'm familiar with these – committees (from serving on the C++ Standards Committee), business needs (from consulting), and historical factors (from studying different programming languages). Especially in the commercial environment of Sun, it's much harder to make a decision that – although it might benefit the language – could cause short-term pain to companies using Java.

2. What we, the programmers who consume Java, are left with as a result of these decisions, and how we must absorb and adapt to these results.

How we got what we got

Here's what I think happened. It's clear that most if not all parameterized type systems were studied, for quite awhile. But strong conservative commercial forces said in effect: "fine, as long as it has no impact." These forces "won," and the result is that generics were added as long as all evidence of them could be erased for the sake of migration compatibility. While a generics system such as C++, Ada or Eiffel has would have caused big waves, Java's Generics appears to cause no ripples at all. So if migration compatibility was indeed the most important design parameter for generics, then it succeeded admirably.

After achieving that, what are we left with? A system that prevents ClassCastException. That wasn't actually what people had been clamoring for. People had been asking for a parameterized type system. It is most likely that the people asking for this had come from C++ (rather than Eiffel or Ada), and were asking for it based on their experience with C++. I'll wager that none of those people imagined a parameterized type system like Java Generics.

But since Java Generics only solves the problem of preventing ClassCastException^[1], what's to be done? If that's the problem that was solved (regardless of how we got there), it must therefore be a Really Important Problem. So we've started hearing about how bad ClassCastException is, as if it has been crippling the forward momentum of all Java development projects since the beginning of the language.

I have to accept some of the responsibility for this. I have been teaching the problem of the "Dog in Cat collection" error for years, without giving it serious thought. Now, instead of saying:

List listOCats = new ArrayList();

List<Cat> listOCats = new ArrayList<Cat>();

If you try to put anything but a Cat (or an object derived from Cat) into the collection, you find out at compile time. That is in fact one of the (many) features that the parameterized type systems in other languages give you. But only one, and in my opinion one of the least interesting.

How often does this kind of ClassCastException happen? I don't remember it ever happening to me, and when I asked people at conferences, I didn't hear anyone say that it had happened to them. A book used an example of a list called files that contained String objects – in this example it seemed perfectly natural to add a File object to files, so a better name for the object might have been fileNames. No matter how much type checking Java provides, it's still possible to write obscure programs, and a badly-written program that compiles is still a badly written program. Perhaps most people use well-named collections such as "cats" that provide a visual warning to the programmer who would try to add a non-cat.

And even if it did happen, how long would such a thing really stay buried? It would seem that as soon as you started running tests with real data you'd see an exception pretty quickly. One author asserted that such a bug could "remain buried for years." But I do not recall any deluge of reports of people having great difficulty finding "dog in cat list" bugs, or even producing them very often. Whereas with threads, it is very easy and common to have bugs that may appear extremely rarely, but only give you a vague idea of what's wrong.

I am not saying that it is useless to detect potential ClassCastExceptions at compile time. But:

1. There's a cost-benefit analysis between the benefit of preventing ClassCastException and the cost of the extra complexity added to the language. Is the prevention of ClassCastException really worth the confusion produced by Java Generics?

2. I understand that the original goal of parameterized types was converted over time into preventing ClassCastException, but if the latter had been the original goal I suspect we might have been able to find a very different and more straightforward approach.

3. Suggesting that this is a true paramaterized type mechanism when it is just "autocasting" is confusing for those of us expecting real parameterized types.

I believe the intent of the general-purpose language feature called "generics" (not Java's particular implementation of it) is expressiveness, not type-safe collections. Type-safe collections come as a side-effect of the ability to create more general-purpose code. Even though the "dog in cat list" argument is used to justify Java Generics, I do not believe that this is what the concept of parameterized types is really about. Instead, generics are as their name implies – a way to write more "generic" code that is less constrained by the types it can work with, so a single piece of code can be applied to more types.

Here's a thread where "ortliebj" repeatedly questions the frequency of ClassCastException in production programming, and doesn't get particularly convincing answers.

I would go further and ask "how terrible is it to get ClassCastExceptions at runtime rather than finding out at compile time? Considering the big picture and all the other problems that could be solved (like the aforementioned threading problems), is it the most important problem to solve, especially given the mental expense of learning Java Generics?

I asked Chuck Allison (former C++ Committee member and long-time editor of C/C++ Users Journal) about this. He said:

"I spoke about this with Greg Colvin when I worked at Oracle. He complained about having to cast. I admitted that it was tedious, but that I had never once put the wrong object into a container. I have never seen the mistake of being surprised by what's in a container in my or anyone else's experience since Java came about.

"There's the purist view (ultimate type safety - "don't let me make any mistakes"), and the pragmatic view ("make simple things simple, dangerous things difficult, but for goodness sake, let me do my job"). As nice as purity is, some mistakes are bigger than others (containers of Object is not a major one), and eventually we have to be pragmatic to get things done - we have to use our tools correctly. To me, except for wildcards (which are cute, but again, not pragmatically exciting), Java generics just eliminate the need to cast, so they shouldn't make such a big deal about them."

Chuck (now a computer science professor at Utah Valley State College) is also where I got the term "Latent Typing." I didn't make it up, it has history in computer science. See, for example, Types and Programming Languages, Benjamin C. Pierce, MIT Press, 2002.

"Java is a Statically Typed Language ...

...and Bruce prefers dynamic typing." I should take another shot at making this clear.

I am well aware of the value of static typing. Going from pre-ANSI C to C++ made me think that enough static type checking might be able to guarantee the proper execution of all programs.

But eventually I saw that static type checking is just one form of testing. And testing is what your program needs. It's great if the compiler can perform those tests for you, and it can make things a lot easier when it does. But static testing is only one part of the picture, and has its limits. At some point you must also have dynamic testing, as you try to get your coverage more and more complete.

Ironically (in this discussion) dynamic testing is one of the things that Java brought to the table. C++ is actually the language that can be called (almost) purely statically-typed. The runtime model in C++ is that of C, which is to say, that of assembly, which is to say "effectively none." C++ must do all of its checking at compile-time; it has no choice^[2]. The Java designers understood that some tests, array-bounds checking and incorrect casts, to name two, must occur at runtime. So Java has sophisticated runtime support, and this allows powerful features such as reflection that C++ could not hope to duplicate.

So Java (and C#) has both compile-time testing and runtime testing. Of course, there's another boundary – the language system can only know so much, and at some point you have to start writing your own tests, that know the specifics of your particular program.

I do not mean to argue against static type checking. Discovering errors is the goal, and if they can be discovered (A) at the earliest point in the development process and (B) automatically, by the compiler, that seems like a good thing (however, the XP folks have cast some doubts on the conventional wisdom that the cost of an error goes up exponentially the later it is found). Even Python has pychecker, a tool to perform static checks.

The issue is trickier than that. What I'm trying to point out is the tradeoff between when the errors are found, and how much it's costing to find them. And as much as we like answers that are hard and fast, saying "static type checking is universally good and always the best solution" is a recipe for eventual disaster, because even the most avid static type checking fan will grow tired of arguing with the compiler when enough rules have been heaped upon the language. The desire for expression over constraint will eventually win out.

Java Generics are a good example of this. They prevent ClassCastExceptions. How big of a problem is this, versus the overhead of (1) learning and (2) maintaining the code of the new syntax of the feature? I've made a similar argument about checked exceptions – the type of error they prevent is not worth the cost. In both cases the errors can still be found, by automatic language mechanisms, at runtime. So it's still an improvement over a purely-statically-typed language like C++ (yes, I'm aware of runtime exception checking in C++, but I'm trying to speak in general terms).

So to summarize, I maintain:

1. It's about testing the correctness of your code and your system.

2. Testing is a spectrum: compile-time, runtime, hand-written.

3. Whenever you choose one part of the spectrum over another, it's a tradeoff.

No early protest?

I will take issue with Neal when he says:

"You might not agree with migration compatibility as a goal for the generics extension to Java. That would have been very useful feedback in 1999 when jsr14 was formed, and in fact the issue was discussed at great length at the time. Whatever your feelings, I hope you agree that now, a month before the product ships, is a poor time to reconsider the most fundamental design goals that were set five years earlier for the product and on which the existing design and implementation depends deeply."

If Neal is referring to me, personally, he's almost right. My first comment on generics was last March, when I discovered (as I began my initial struggle with Java generics, thinking that it would be a cake walk because I knew so much about C++ templates and that naturally generics would be simpler than that) that generics did not support latent typing, a feature I just assumed would be available in anything that purported to be a parameterized type system, since every other one that I had seen at that time did (C# generics also doesn't support latent typing, for reasons of cross-language compatibility on .NET).

But if he is talking about the Java community in general, I've certainly come across some very strong calls to abandon erasure-based generics on the Sun Java forums, some of them at least 2 years ago. Here's a strong discussion questioning erasure from about a year ago. And here's a very pointed thread on those forums in early July asking how to stop generics from going into Java in their current form. In one entry, Toby Reyelts sums it up by listing all the things you can't do with Java Generics that you can in C++ templates, that he's willing to give up, if:

"I'm not asking for C++ templates - I'm willing to put aside the fact that I can't use constants, I can't perform compile-time recursion, I can't do compile- time loop unrolling, I can't create full or partial specializations, I can't work with primitive types, I can't create arrays of generic types, I can't check generic casts at compile time, I can't do type analysis at compile time, I can't do anything with generics that would create multiple instantiations of the generic code, and the list goes on... That doesn't mean that I've thrown all hope out of generics being used for more than simple wrapping of un-typesafe containers."

And Neal is almost right in saying that I could have joined the JCP and given my opinion earlier. Except that my lawyer will not let me sign the JCP agreement, which is too broad and could be used to assume rights of my IP. Having been sent, several years ago, a "cease-and-desist" letter from Sun's lawyers telling me to stop using the word "Java," I agree with my lawyer that it's not worth the risk.

But I have to concur with Neal that at this point it's water under the bridge. As he said, backwards compatibility is hard and he and the Sun team did their best given the onerous constraint of migration compatibility. I can't see anything that would stop Java 5.0 from shipping in a few days, or that could change the shape of Java generics in the future.

I suppose if the term "generics" (and all that it promises) had not been used at all, the conversations around it would have been much simpler; if it had been called "Autocasting," for example. Then we wouldn't have had to argue whether it had particular features we expected from other parameterized type implementations. But the term "generics" has now been co-opted into Java, and my job is now to do my best to understand Java Generics and to explain it.

What does all this mean?

Before I can explain something to someone, I need to plumb the depths of that topic so I can get the full picture of where the ideas came from. This allows me to answer the question that inevitably comes up, "why is it like this?" These articles and this forum allows me to work through the issues (with help of people like Joshua Bloch, Neal Gafter, Anders Hejlsberg, and others) in ways that don't necessarily fit into book format (I usually need to express an idea multiple times before it begins to communicate itself cleanly).

Erasure will not make sense to programmers first learning Java Generics unless they have the context in which it arose. Otherwise it will just seem like a strange and annoying limitation, odd and arbitrary behavior by the compiler that forces them to remember that information doesn't exist when it seems like it ought to.

I think I can give a sense of that context now. And perhaps make the case that the various forces were too strong for Java to go anywhere else than it has. I will probably show that other parameterized type systems allow significantly more expression and power than Java Generics. But in the end, Java Generics are what they are, and they are what we have, and so most of my effort in the book will go to explaining them in a clear fashion.

An Alternative

One of the comments that has often been made on the Sun Java newsgroups when someone questions generics is "if you can come up with a better design and implementation (that satisfies the constraint of Migration Compatibility) then prove it." Combining the current state of Java with the constraint of Migration Compatibility, perhaps erasure is the only solution.

Another solution is to design a different language that has a "programmer migration path" from Java, that looks similar enough to Java to be familiar, that still interacts with Java by generating Java bytecodes and libraries that can be called from Java as well as being able to call Java libraries, but at the same time tries to improve programmer productivity using powerful language constructs. This is exactly the approach that C++ took with respect to C, and it is why C++ became the most successful Object-Oriented language at the time, and the first really widely accepted OO language (ignoring the arguments that some large fraction of C++ programmers were still programming in C).

I was recently introduced to such a language by its creator, Daniel Bonniot. The language is called Nice (see nice.sf.net), and although I've just begun looking at it and discussing it with him, I have so far found it to be very impressive. It could be just the thing if you begin to feel overconstrained by Java, but must still produce Java libraries and applications. I hope to be able to explore Nice more in the future.

Feedback Wiki Page

^[2] I am aware that there is a tiny bit of runtime support in C++ in the form of RTTI and dynamic_cast. But in comparison with what Java has, it is effectively none.