Generics and Constrained Polymorphism versus Subtyping

Question

In this PDF presentation on Haskell Type Classes, slide #54 has this question:

Open Question:

In a language with generics and constrained polymorphism, do you need subtyping too?

My questions are:

1. How do generics and constrained polymorphism make subtyping unnecessary?

2. If generics and constrained polymorphism make subtyping unnecessary, why does Scala have subtyping?

Answer 1

How do generics and constrained polymorphism make subtyping unnecessary?

It is not known that they do. If you put the slide in context, I think that the argument the speaker was trying to make goes something like this:

• In the old days, subtyping provided an important kind of polymorphism.

• Also in the old days, in another country, type abstraction and type parameters provided an important kind of polymorphism. This kind is known in its native land as parametric polymorphism, but in foreign lands it is called generics.

• Modern generics admit of constraints, sometimes called "bounded polymorphism", which can achieve many of the same things as subtype polymorphism.

• Subtyping carries with it substantial baggage—in particular, you have to worry about covariance and contravariance. Languages wind up with uncomfortable restrictions, heavyweight notations, and sometimes outright safety violations (e.g., Eiffel).

The open question: perhaps constrained parametric polymorphic solves enough of the same problems that in the happy future, we can get rid of subtype polymorphism entirely, and with it the nasty question of when subtyping is covariant, contravariant, and invariant.

Answer 2

Well if that is indeed an open question, then by definition we don't know the answer to #1. The design spaces are pretty different, and it isn't obvious to me how you might directly encode subtyping into constrained polymorphism. The encoding is direct when the arguments are polymorphic. For example, a Haskell function with type

foo :: (Num a) => a -> Bool

is equivalent to, say:

Bool foo(Num x)

in an OO language. However it is not clear how to encode:

// I will return some Num, but I'm not going to tell you what kind exactly
Num bar(Bool x) 

into constrained polymorphism, nor is it clear how to encode:

-- I can return any kind of Num, *you* tell *me* what kind
bar :: (Num a) => Bool -> a 

into subtyping.

My best guess for #2 is that Scala has to talk to Java, and Java talks about subtyping. And because Scala has every type system feature known to man because it thinks it has to in order to be cool. :-P