29

It's commonly accepted that Java generics failed in some important ways. The combination of wildcards and bounds led to some seriously unreadable code.

However, when I look at other languages, I really can't seem to find a generic type system that programmers are happy with.

If we take the following as design goals of a such a type system:

  • Always produces easy-to-read type declarations
  • Easy to learn (no need to brush up on covariance, contravariance, etc.)
  • maximizes the number of compile-time errors

Is there any language that got it right? If I google, the only thing I see is complaints about how the type system sucks in language X. Is this kind of complexity inherent in generic typing? Should we just give up on trying to verify type safety 100% at compile time?

My main question is which is the language that "got it right" the best with respect to these three goals. I realize that that's subjective, but so far I can't even find one language where not all it's programmers agree that the generic type system is a mess.

Addendum: as noted, the combination of subtyping/inheritance and generics is what creates the complexity, so I'm really looking for a language that combines both and avoids the explosion of complexity.

We're looking for long answers that provide some explanation and context. Don't just give a one-line answer; explain why your answer is right, ideally with citations. Answers that don't include explanations may be removed.

  • 2
    What do you mean by easy-to-read type declarations? The third criteria is also ambiguous: for example, I can turn array index out of bounds exceptions into compile time errors by not letting you index arrays unless I can compute the index at compile time. Also, the second criteria rules out subtyping. That's not necessarily a bad thing but you should be aware of what you're asking. – Doval Oct 17 '14 at 16:18
  • 17
    See most functional languages – AlexFoxGill Oct 17 '14 at 16:20
  • 9
    @gnat, this is most definitely not a rant against Java. I program almost exclusively in Java. My point is that it's generally accepted within the Java community that Generics are flawed (not a total failure, but probably a partial one), so it's a logical question to ask how they should have been implemented. Why are they wrong and did others get them right? Or is it actually impossible to get generics absolutely right? – Peter Oct 17 '14 at 17:06
  • 1
    Was everyone just stealing from C# there would be less complaints. Especially Java is in a position to catch up by copying. Instead they decide on inferior solutions. Many of the questions the Java design committees still discuss have already been decided and implemented in C#. They don't even seem to look. – usr Oct 17 '14 at 21:02
  • 2
    @emodendroket: I think my two biggest complaints about C# generics are that there's no way to apply a "supertype" constraint (e.g. Foo<T> where SiameseCat:T) and that there's no possibility of having a generic type which isn't convertible to Object. IMHO, .NET would benefit from aggregate types which were similar to structures, but even more bare-boned. If KeyValuePair<TKey,TValue> were such a type, then an IEnumerable<KeyValuePair<SiameseCat,FordFocus>> could be cast to IEnumerable<KeyValuePair<Animal,Vehicle>>, but only if the type couldn't be boxed. – supercat Oct 18 '14 at 4:38
24

While Generics have been mainstream in the functional programming community for decades, adding generics to object oriented programming languages offers some unique challenges, specifically the interaction of subtyping and generics.

However, even if we focus on object oriented programming languages, and Java in particular, a far better generics system could have been designed:

  1. Generic types should be admissible wherever other types are. In particular, if T is a type parameter, the following expressions should compile without warnings:

    object instanceof T; 
    T t = (T) object;
    T[] array = new T[1];
    

    Yes, this requires generics to be reified, just like every other type in the language.

  2. Covariance and contravariance of a generic type should be specified in (or inferred from) its declaration, rather than every time the generic type is used, so we can write

    Future<Provider<Integer>> s;
    Future<Provider<Number>> o = s; 
    

    rather than

    Future<? extends Provider<Integer>> s;
    Future<? extends Provider<? extends Number>> o = s;
    
  3. As generic types can get rather long, we should not need to specify them redundantly. That is, we should be able to write

    Map<String, Map<String, List<LanguageDesigner>>> map;
    for (var e : map.values()) {
        for (var list : e.values()) {
            for (var person : list) {
                greet(person);
            }
        }
    }
    

    rather than

    Map<String, Map<String, List<LanguageDesigner>>> map;
    for (Map<String, List<LanguageDesigner>> e : map.values()) {
        for (List<LanguageDesigner> list : e.values()) {
            for (LanguageDesigner person : list) {
                greet(person);
            }
        }
    }
    
  4. Any type should be admissible as a type parameter, not just reference types. (If we can have an int[], why can we not have a List<int>)?

All of this is possible in C#.

  • 1
    Would this also get rid of self-referential generics? What if I want to say that a comparable object can compare itself to anything of the same type or a subclass? Can that be done? Or if I write a sort method that accepts lists with comparable objects, that all need to be comparable to each other. Enum is another good example: Enum<E extends Enum<E>>. I'm not saying a type system should be able to do these, I'm just curious how C# handles these situations. – Peter Oct 20 '14 at 9:12
  • 1
    Java 7's generic type inference and C++'s auto help with some of these concerns, but are syntactic sugar and do not change the underlying mechanisms. – user22815 Oct 20 '14 at 15:19
  • @Snowman Java's type inference has some really obnoxious corner cases though, like not working with anonymous classes at all and not finding the right bounds for wildcards when you evaluate a generic method as an argument to another generic method. – Doval Oct 20 '14 at 18:55
  • @Doval that is why I said it helps with some of the concerns: it fixes nothing, and does not address everything. Java generics have a lot of problems: while better than raw types, they certainly do cause many headaches. – user22815 Oct 21 '14 at 3:51
34

The use of subtypes creates a lot of complications when doing generic programming. If you insist on using a language with subtypes, you have to accept there's a certain inherent complexity in generic programming that comes along with it. Some languages do it better than others, but you can only take it so far.

Contrast that with Haskell's generics, for example. They are simple enough that if you use type inference, you can write a correct generic function by accident. In fact, if you specify a single type, the compiler often says to itself, "Well, I was going to make this generic, but you asked me to make it only for ints, so whatever."

Admittedly, people use Haskell's type system in some startlingly complex ways, making it the bane of every newbie, but the underlying type system itself is elegant and much admired.

  • 1
    Thanks for this answer. This article starts with some of Joshua Bloch's examples of where generics get too complicated: artima.com/weblogs/viewpost.jsp?thread=222021 . Is this a difference in culture between Java and Haskell, where such constructs would be considered fine in Haskell, or is there a real difference to Haskell's type system that avoids such situations? – Peter Oct 17 '14 at 16:55
  • 10
    @Peter Haskell doesn't have subtyping, and like Karl said the compiler can infer the types automatically including constraints like "type a must be some sort of integer". – Doval Oct 17 '14 at 16:57
  • In other words covariance, in languages such as Scala. – Paul Draper Oct 18 '14 at 0:01
14

There was quite a bit of research into combining generics with subtyping going on about 20 years ago. The Thor programming language developed by Barbara Liskov's research group at MIT had a notion of "where" clauses that let you specify the requirements of the type you are parameterizing over. (This is similar to what C++ is trying to do with Concepts.)

The paper describing Thor's generics and how they interact with Thor's subtypes is: Day, M; Gruber, R; Liskov, B; Myers, AC: Subtypes vs. where clauses: constraining parametric polymorphism, ACM Conf on Obj-Oriented Prog, Sys, Lang and Apps, (OOPSLA-10):156-158, 1995.

I believe they, in turn, built on work that was done on Emerald during the late 1980s. (I haven't read that work, but the reference is: Black, A; Hutchinson, N; Jul, E; Levy, H; Carter, L: Distribution and Abstract Types in Emerald, _IEEE T. Software Eng., 13(1):65-76, 1987.

Both Thor and Emerald were "academic languages" so they probably didn't get enough usage for people to really understand whether where clauses (concepts) really solves any real problems. It is interesting to read Bjarne Stroustrup's article on why the first try at Concepts in C++ failed: Stroustrup, B: The C++0x "Remove Concepts" Decision, Dr Dobbs, July 22, 2009. (Further info on Stroustrup's home page.)

Another direction that people seem to be trying is something called traits. For example Mozilla's Rust programming language uses traits. As I understand it (which may be completely wrong), declaring that a class satisfies a trait is very much like saying that a class implements an interface, but you are saying "behaves like a" rather than "is a". It seems that Apple's new Swift programming languages is using a similar concept of protocols to specify constraints on the parameters to generics.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.