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.

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
See [most](http://www.haskell.org/haskellwiki/Generics) [functional](http://msdn.microsoft.com/en-us/library/dd233215.aspx) [languages](http://docs.scala-lang.org/tutorials/tour/generic-classes.html) — Alex, Oct 17 '14 at 16:20
@Doval Well, they're design goals rather than strict constraints, so they can be a little ambiguous. The point is that once programmers in a language community start complaining about overly complex type declarations, we can eliminate that language. As for the compile-time safety, the main point of introducing generics into a language is to turn runtime errors into compile time errors. You can design your generics to be simpler (no bounds or wildcards, only invariant generic types), but then you have to do more casting and get more runtime errors again. So it's a trade-off. — Peter, Oct 17 '14 at 16:59
@Peter Sometimes the types involved in whatever you're trying to do get complex even if what you're trying to do is conceptually simple. The fact that the types *can* get complicated doesn't mean something is wrong, and it becomes a non-issue in most cases if the compiler can infer them. Like I said, the main complication is subtyping. — Doval, Oct 17 '14 at 17:03
@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
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
To insert my own opinion, I feel the C++ template system WILL have it done right once they add Concepts. Until then, it's good but I wouldn't say it "gets it right" — chbaker0, Oct 17 '14 at 21:51
@peter - most of the arguments I see for Java's flawed generics aren't because they're complicated or hard to use - it's because they do type erasure. — Telastyn, Oct 17 '14 at 22:50
@Alex G GHC.Generics has absolutely nothing to do with Java Generics — alternative, Oct 18 '14 at 01:48
There's nothing wrong with Java's generic wild cards or bounds. The problem with Java's generics is due to type erasure. I have at one point or another wished C# has wildcard types; I had to circumvent that weakness with an inferior design. — Thomas Eding, Oct 18 '14 at 02:38
@emodendroket: I think my two biggest complaints about C# generics are that there's no way to apply a "supertype" constraint (e.g. `Foo 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` were such a type, then an `IEnumerable>` could be cast to `IEnumerable>`, but only if the type couldn't be boxed. — supercat, Oct 18 '14 at 04:38
I would say Scala got generics much better than Java. On the other hand, the answer to whether the result is "easy to learn" is not obvious. It's more complex than Java because in order to not have loopholes, it requires some extra entities like the `Nothing` type. But I think it's reasonably easy to understand if you don't try to use all the most advanced features at first. — Michał Kosmulski, Oct 18 '14 at 09:25
The consensus argument falls prey to [No true Scotsman](http://en.wikipedia.org/wiki/No_true_Scotsman) fallacy because in some circles, what actually happens is that "once --programmers-- ***a programmer*** in a language community start complaining about overly complex type declarations, we can eliminate that --language-- ***programmer***." — rwong, Oct 18 '14 at 10:51
@supercat: one applicable advice is to http://stackoverflow.com/questions/383947/what-does-it-mean-to-program-to-an-interface , that is, program to the `Animal`s and the `Vehicle`s and standardize your entire code base so that anything *derived from* `Animal` will be passed as an `Animal`, not as a specific `SiameseCat`. — rwong, Oct 18 '14 at 10:56
@AlexG are you sure you know haskell? GHC.Generics has *absolutely nothing to do with what hes talking about*. GHC.Generics is just a scrap-your-boilerplate type library, what we are talking about here is type polymorphism which is built into the language! I think you should read the question again. — alternative, Oct 18 '14 at 14:04
@ThomasEding (and Telastyn): I don't think type erasure is the problem. Have a look at these examples: http://www.artima.com/weblogs/viewpost.jsp?thread=222021 collated by Joshua Bloch. Those would read the same with or without type erasure. Sure with persistent types, you could do some more runtime checking, but the main benefit of generics is that they allow problems to be found at compile time anyway. Given that, I don't see how type erasure could have much to do with the question of what makes a generic type system good. — Peter, Oct 18 '14 at 14:17
@djechlin C# has quite neat generics. There is no "but" about them. They've got full runtime (and debugging) support, have quite a range of constraints that can be applied, can be used on structs, classes, methods and delegates (and any combination), support polymorphism, compile-time checks... Pretty much everything one could hope for. — Vercas, Oct 18 '14 at 14:35
@djechlin meriton's answer covers that. The generics are checked at compile-time. There is no error that slips through. Because nothing is known about the generic type, the compiler will restrict the usage a bit. If you add constraints for it, then the compiler can know more and let you do more with it. The declarations are pretty straight-forward, the type name goes between angle brackets ("<" and ">") after the identifier (of a class, struct, method, delegate). For methods, the compiler can infer the types in every practical case, so there's no need to specify the generic type name manually. — Vercas, Oct 18 '14 at 14:44
@rwong: Although I wouldn't say that every typecast is indicative of a defect in either program or language design, a good program design should minimize the need for typecasts which aren't compelled by crummy language design [as in `f1 = (float)((double)f2+f3+f4);` where IMHO a good language shouldn't require any typecasts but Java and C# both require two]. If some has a collection of `SiameseCat` but needs to pass the collection to code that expects to read a collection of `Animal`, the collection should be defined as a collection of `SiameseCat`. — supercat, Oct 18 '14 at 16:36
@Vercas: The generics in C# are quite good. If the type system supported more parameter and local-variable types [e.g. declaring that a passed-in reference should be considered "ephemeral", so the called method couldn't store a copy and the caller would know that] then it would be possible to have function parameters which could behave in covariant and contravariant manner while retaining the advantages of value-type generics. For example, a `Dictionary` could implement `IQueryableSet` with method `Contains(T item);`. Code which wants something that can report... — supercat, Oct 18 '14 at 16:45
...whether a particular `Cat` is contained within should be happy with a container of `Animal` or a container of `SiameseCat`. Casting directly from `IQueryableSet` to `IQueryableSet` wouldn't make particular sense (the set couldn't possibly have any matches) but an `IQueryable` should have no trouble handling a call to `IQueryable.Contains(someCat)`; it should simply return `false`. — supercat, Oct 18 '14 at 16:47
@AlexG: Actually the type of `id` in Haskell, `a -> a`, would already be considered a generic type in Java/C#. An example of Haskell's generics would be a *single* method with 'signature' `public A sum(Container)` i.e. generic over the container type, not the contained type. — yatima2975, Oct 18 '14 at 17:37
you can maximize the compile time errors by replacing every type in java with Ä It's also easy to learn. — Jens Schauder, Oct 18 '14 at 18:07
@supercat I've never really found myself needing that. `Contains(object item)` (non-generic interface) exists for this. What you are suggesting seems like a **serious** challenge to implement with generics. — Vercas, Oct 18 '14 at 18:30
@Vercas: Being able to have a method guarantee that it won't persist a passed-in method would be a *major* win in many cases (e.g. an interface like `IEnumerable` could accept a `CopyTo` method which would receive an `IDataSink` and call its `ImportFromRange(T[] src, int start, int count)` method to feed it data from any backing arrays, thus making it possible to copy data from one array-backed collection into another, without it having to go through a temporary array, and without having to process every item individually. Covaraince would be a bonus. — supercat, Oct 18 '14 at 18:47
@supercat: [@JonSkeet's answer to your question](http://stackoverflow.com/a/7365279/377657) — rwong, Oct 18 '14 at 19:53
@rwong: The reason a `List` is not a `List` even when `B:A` is that invoking the `Add` method on a `List ` would cause it to try to *persist* an `A` in the collection of `B`'s. Parameters which will not be persisted could use looser rules. If one wants to find those items of an `IEnumerable` which are also in an `IEnumerable`, then the set of `Dog` shouldn't have to bother looking for any `Animal` that isn't a `Dog`. If it were an `IEnumerable` which simply didn't happen to contain anything that wasn't a `Dog`, however, it would have to search for such items. — supercat, Oct 18 '14 at 20:10
@AlexG, however, Scala's generics have the disadvantage of using the JVM (which enforces type erasure). As a result, you need to use a manifest to avoid type erasure, and sometimes that's not possible (eg, with generic traits). — Kat, Oct 21 '14 at 21:06

score 34 · Answer 1 · answered Oct 17 '14 at 16:48

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.

answered Oct 17 '14 at 16:48

Karl Bielefeldt

146,727
38
279
479

1

Thanks for this answer. This article starts with some of Joshua Bloch's examples of where generics get too complicated: http://www.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 00:01

score 24 · Accepted Answer · answered Oct 18 '14 at 14:17

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:

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.
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;
```

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);
        }
    }
}

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

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>. 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 09:12
Java 7's [generic type inference](http://docs.oracle.com/javase/tutorial/java/generics/genTypeInference.html) and [C++'s auto](http://en.cppreference.com/w/cpp/language/auto) help with some of these concerns, but are syntactic sugar and do not change the underlying mechanisms. — , 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. — , Oct 21 '14 at 03:51

Wandering Logic · Answer 3 · 2014-10-18T02:09:46.933

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.

Rust traits are similar to Haskell Type classes. But there are two angles one can look at it: 1. See it as a means to state constraints. 2. Define a generic interface, which can be associated to a concrete type or generic class of types. — BitTickler, Dec 05 '19 at 04:16

A good generic type system

3 Answers3