Generics and Constrained Polymorphism versus Subtyping

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?

---

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.

---

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

---

Oleg Kiselyov and Ralf Lämmel's "Haskell's overlooked object system" proposes a library for Haskell that implements an object system using Haskell's existing features, including type classes.

An excerpt from the "introduction" section of the paper (emphasis mine):

The interest in this topic is not at all restricted to Haskell researchers and practitioners since there is a fundamental and unsettled question — a question that is addressed in the present paper:

       What is the relation between type-class-bounded and subtype polymorphism?

In this research context, we specifically (and emphatically) restrict ourselves to the existing Haskell language (Haskell 98 and common extensions where necessary), i.e., no new Haskell extensions are to be proposed. As we will substantiate, this restriction is adequate, as it allows us to deliver a meaningful and momentous answer to the aforementioned question.

---

2 is easy: because Java (and JVM bytecode) has it. If we want to usefully call Scala from Java, we pretty much have to allow extending Java interfaces and classes; and if Scala classes get translated to JVM classes (and traits to interfaces), then we can extend them as well.

The same reason why Scala has null :)

As to 1, you also need to have existential types for encoding the

Num bar(Bool x) 

case:

bar :: Bool -> exists a. Num a