I thought he was going to talk about how OOP can be broken down into several simpler orthogonal concepts, namely:
1) Code reuse (e.g. inheritance)
2) Implementation hiding (e.g. methods)
3) Subtyping (e.g. interfaces)
4) Code composition / programming in the large (e.g. classes)
5) Run-time dynamic dispatch (e.g. instances)
Functional languages such as Haskell, Mercury, OCaml, and Scheme do a good job of teasing these apart:
1) Code reuse doesn't need anything fancy. You can do this with function calls even in C.
2) You can hide implementations using opaque types + accessor functions. OCaml has some pretty neat typing constructs that allow partial type hiding as well. You can even do this in C with incomplete types.
3) Subtyping is provided at the module level by OCaml's module interfaces, at the opaque type level by Haskell and Mercury's type classes, and at the transparent type level by OCaml's polymorphic variants and functional objects.
4) Code composition / programming in the large is provided by OCaml's module functor system or Scheme's unit system. You can even do this in C at the linker level.
5) Run-time dynamic dispatch is a feature that's rarely actually needed in practice. (Compile-time dynamic dispatch is usually sufficient; that's provided by Haskell's type classes or OCaml's module functors.) Nonetheless OCaml provides RTTD -- with multiple dispatch -- through functional objects, Mercury provides the same through a combination of type classes + existential types. (I think you can even use existential module types in the latest OCaml.)
Just to be pedantic, what Haskell type-classes provide is not usually known as sub-typing. Sub-typing usually implies some relation between types such that every element of a sub-type is also an element of the super-type.
Haskell does not have any sort of sub-typing in this sense. Every single value only belongs to a single type. What you get with type-classes is polymorphism: your function works for all types in the type-class, but each type is disjoint.
Now, I should add that your observations about how type-classes are used are correct--they really do serve many of the same roles as sub-typing does in other languages. However, the distinction between polymorphism and type-classes is still important both in practical and in theoretical terms. Not having sub-typing significantly simplifies the Haskell type system--you never have to worry about covariance or contravariance, for example--but also makes some things, like heterogenous lists, slightly more tricky.
I think you could safely replace your "sub-typing" header with "polymorphism"; sub-typing with interfaces is just one kind of polymorphism, and other kinds also serve a similar rule of making your code more generic by letting it work on multiple types.
Anyhow, I think that covers my daily dose of pedantry :).
Edit: also, to clarify: I like and agree with your post, I just think the distinction between sub-typing and polymorphism more generally is important.
In a project of my own I did a similar thing with intervals to what he did with lattices: I defined a type class for intervals and then made lists of intervals an instance of the class. Greatly simplified my own code for very little cost.
The pedant in me agrees (class-constrained types are not types and therefore not subtypes), but the pragmatist in me still wants to think of class-constrained types as forming a subtyping hierarchy :) even if doing so requires explicit typecasting. Some food for thought:
In Mercury, you can combine existential types with typeclasses like so:
type foo ---> some [T] (foo(T) => printable(T)).
Pedantically, foo is a distinct type from any other. However, any T which is printable is effectively a subtype of foo, since you can use it wherever a foo is expecected, modulo some ugly syntax:
I believe you can do something similar in OCaml using module types. (Of course OCaml has true subtyping via polymorphic variants and functional objects.) I am not as familiar with Haskell, so I'm not sure if it supports existential types or not.
Dependent languages like Coq go even further -- you can augment types with arbitrary predicates to form "sigma types" which can act as subtypes of one another. You can even write entire programs using sigma types without explicit typecasting. However they remain distinct from true types, and therefore do not provide true subtyping (regardless how well-executed the illusion is).
{-# LANGUAGE ExistentialQuantification #-}
data Foo = forall a. Show a => Foo a
[Foo 10, Foo "blarg", Foo (Foo (Foo "str"))
However, I think having the extra constructor there is very important. If you were willing to overlook extra syntax and the behavior of the type, then even a normal tagged union starts to look like sub-typing!
In fact, in practice, that's exactly what you use where you would use sub-typing in a different language. There are some significant differences, but I'm sure you can see a parallel.
There is also an intuitive parallel between existential types and normal tagged unions. The existential type is somewhat like a way to create a tagged union for an unbounded number of types. This naturally means it can't actually be tagged--the tag loses its meaning and you now can't recover the type of the contents--but in practical terms they're similar.
As I said, thinking of it like sub-typing is a pretty good intuitive guide (although it might lead you astray sometimes). I was just being pedantic; there's something about formal semantics and type theory that just raises the pedant in me :P.
1) Code reuse (e.g. inheritance)
2) Implementation hiding (e.g. methods)
3) Subtyping (e.g. interfaces)
4) Code composition / programming in the large (e.g. classes)
5) Run-time dynamic dispatch (e.g. instances)
Functional languages such as Haskell, Mercury, OCaml, and Scheme do a good job of teasing these apart:
1) Code reuse doesn't need anything fancy. You can do this with function calls even in C.
2) You can hide implementations using opaque types + accessor functions. OCaml has some pretty neat typing constructs that allow partial type hiding as well. You can even do this in C with incomplete types.
3) Subtyping is provided at the module level by OCaml's module interfaces, at the opaque type level by Haskell and Mercury's type classes, and at the transparent type level by OCaml's polymorphic variants and functional objects.
4) Code composition / programming in the large is provided by OCaml's module functor system or Scheme's unit system. You can even do this in C at the linker level.
5) Run-time dynamic dispatch is a feature that's rarely actually needed in practice. (Compile-time dynamic dispatch is usually sufficient; that's provided by Haskell's type classes or OCaml's module functors.) Nonetheless OCaml provides RTTD -- with multiple dispatch -- through functional objects, Mercury provides the same through a combination of type classes + existential types. (I think you can even use existential module types in the latest OCaml.)