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

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

Answer 2

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