A good generic type system

Question

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.

Answer 1

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#.

Answer 2

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.

Answer 3

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.