What's wrong with type classes?

Question

Type classes seem to be a great possibility to write generic and reusable functions in a very consistent, efficient and extensible way. But still no "mainstream-language" provides them - On the contrary: Concepts, which are a quite analogical idea, have been excluded from the next C++!

What's the reasoning against typeclasses? Apparently many languages are looking for a way to deal with similar problems: .NET introduced generic constraints and interfaces like IComparable which allow functions like

T Max<T>(T a, T b) where T : IComparable<T> { // }

to operate on all types that implement the interface.

Scala instead uses a combination of traits and so called implicit parameters/view bounds, which are automatically passed to generic functions.

But both concepts shown here have great disadvantages - Interfaces are inheritance-based and thus relatively slow due to indirection and moreover there is no possibility of letting an existing type implement them.

If we needed an abstraction for a Monoid, we could pretty well write an interface and let our types implement this, but builtin types like int could never operate on your functions natively.

Implicit parameters instead are inconsistent with regular interfaces/traits.

With type classes, there wouldn't be a problem (pseudo-code)

typeclass Monoid of A where
    static operator (+) (x : A, y : A) : A
    static val Zero : A 
end

instance Int of Monoid where
   static operator (+) (x : Int, y : Int) : Int = x + y
   static val Zero : Int = 0
end

So why don't we use type classes? Do they have serious disadvantages after all?

Edit: Please don't confuse typeclasses with structural typing, pure C++ templates or duck typing. A typeclass is explicitly instantiated by types and not just satisfied by convention. Moreover it can carry useful implementations and not just define an interface.

Answer 1

Interfaces need not be inheritance-based... that's a different and separate design decision. The new Go language has interfaces, but doesn't have inheritance, for example: "a type automatically satisfies any interface that specifies a subset of its methods", as the Go FAQ puts it. Simionato's musings about inheritance and interfaces, prompted by Go's recent release, may be worth reading.

I concur that typeclasses are even more powerful, essentially because, like abstract base classes, they let you additionally specify useful code (defining an extra method X in terms of others for all types that otherwise match the baseclass but don't define X themselves) -- without the inheritance baggage that ABCs (differently from interfaces) almost inevitably carry. Almost inevitably because, for example, Python's ABCs "make believe" that they involve inheritance, in terms of the conceptualization they offer... but, in fact, they need not be inheritance-based (many are just checking the presence and signature of certain methods, just like Go's interfaces).

As for why would a language designer (such as Guido, in the case of Python) choose such "wolves in sheep clothing" as Python's ABCs, over the more straightforward Haskell-like typeclasses that I had proposed since back in 2002, that's a harder question to answer. After all, it isn't as if Python has any compunction against borrowing concepts from Haskell (e.g., list comprehensions / generator expressions -- Python needs a duality here, while Haskell doesn't, because Haskell is "lazy"). The best hypothesis I can offer is that, by now, inheritance is so familiar to most programmers that most language designers feel they can gain easier acceptance by casting things that way (although Go's designers must be commended for not doing that).

Answer 2

Concepts were excluded because the committee didn't think it could get them right in time, and because they weren't considered essential to the release. It's not that they don't think they're a good idea, they just don't think the expression of them for C++ is mature: http://herbsutter.wordpress.com/2009/07/21/trip-report/

Static types try to prevent you passing an object to a function, that doesn't satisfy the requirements of the function. In C++ this is a huge big deal, because at the time the object is accessed by the code, there's no checking that it's the right thing.

Concepts try to prevent you passing a template parameter, that doesn't satisfy the requirements of the template. But at the time the template parameter is accessed by the compiler, there already is checking that it's the right thing, even without Concepts. If you try to use it in a way it doesn't support, you get a compiler error[*]. In the case of heavy template-using code you might get three screens full of angle brackets, but in principle that's an informative message. The need to catch errors before a failed compile is less urgent than the need to catch errors before undefined behaviour at runtime.

Concepts make it easier to specify template interfaces that will work across multiple instantiations. This is significant, but a much less pressing problem than specifying function interfaces that will work across multiple calls.

In answer to your question - any formal statement "I implement this interface" has one big disadvantage, that it requires the interface to be invented before the implementation is. Type inference systems don't, but they have the big disadvantage that languages in general cannot express the whole of an interface using types, and so you might have an object which is inferred to be of the correct type, but which does not have the semantics ascribed to that type. If your language addresses interfaces at all (in particular if it matches them to classes), then AFAIK you have to take a stance here, and pick your disadvantage.

[*] Usually. There are some exceptions, for instance the C++ type system currently does not prevent you from using an input iterator as if it were a forward iterator. You need iterator traits for that. Duck typing alone doesn't stop you passing an object which walks, swims and quacks, but on close inspection doesn't actually do any of those things the way a duck does, and is astonished to learn that you thought it would ;-)

Answer 3

Try define a Matroid, which is what we do (logcally and not orally saying a Matroid), and it's still likely something like a C struct. Liskov principle (latest turing medalist) gets too abstract, too categorical, too theoretic, less treating actual data and more pure theoretical class-system, for handson pragmatic problemsolving, briefly glanced it which looked like PROLOG, code about code about code about code...while an algorithm describes sequences and travelsals we understand on paper or blackboard. Depends which goal you have, solving problem with minimal code or most abstract.

Answer 4

What's the reasoning against typeclasses?

Implementation complexity for compiler writers is always a concern when considering new language features. C++ already made that mistake and we've already suffered years of buggy C++ compilers as a consequence.

Interfaces are inheritance-based and thus relatively slow due to indirection and moreover there is no possibility of letting an existing type implement them

Not true. Look at OCaml's structurally-typed object system, for example:

# let foo obj = obj#bar;;
val foo : < bar : 'a; .. > -> 'a = <fun>

That foo function accepts any object of any type that provides the necessary bar method.

Same for ML's higher-order module system. Indeed, there is even a formal equivalence between that and type classes. In practice, type classes are better for small scale abstractions such as operator overloading whereas higher-order modules are better for large scale abstractions such as Okasaki's parameterization of catenable lists over queues.

Do they have serious disadvantages after all?

Look at your own example, generic arithmetic. F# can actually already handle that particular case thanks to the INumeric interface. The F# Matrix type even uses that approach.

However, you've just replaced the machine code for add with dynamic dispatch to a separate function, making arithmetic orders of magnitude slower. For most applications, that is uselessly slow. You can solve that problem by performing whole program optimizations but that has obvious disadvantages. Moreover, there is little commonality between numerical methods for int vs float due to numerical robustness so your abstraction is also practically useless.

The question should surely be: can anyone make a compelling case for the adoption of type classes?