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

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 2

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 3

Let me start bold: I perfectly understand the motivation of having it and can't understand the motivation of some people to argue against it...

What you want is nonvirtual ad hoc polymorphism.

• ad hoc: implementation can vary
• nonvirtual: for performance reasons; compiletime dispatch

The rest is sugar in my opinion.

C++ already has ad hoc polymorphism via templates. "Concepts" however would clarify what kind of ad hoc polymorphic functionality is used by which user defined entity.

C# just doesn't have any way to do it. An approach that wouldn't be nonvirtual: If types like float would just implement something like "INumeric" or "IAddable" (...) we would at least be able to write a generic min, max, lerp and based on that clamp, maprange, bezier (...). However it wouldn't be fast. You dont want that.

Ways of fixing this: Since .NET does JIT compilation anyway also generates different code for List<int> than for List<MyClass> (due to the differences of value and reference types) it probably wouldn't add that much of an overhead to also generate different code for the ad hoc polymorphic parts. The C# language would just need a way to express it. One way is what you sketched up.

Another way would be to add type constraints to the function using an ad hoc polymorphic function:

    U SuperSquare<T, U>(T a) applying{ 
         nonvirtual operator (*) T (T, T) 
         nonvirtual Foo U (T)
    }
    {
        return Foo(a * a);
    }

Of course you could end up with more and more constraints when implementing Bar that uses Foo. So you may want a mechanism to give a name to several constraints that you regularly use... However this again is sugar and one way to approach it would be to just use the typeclass concept...

Giving a name to several constraints is like defining a type class, but i'd like to just look at it as some sort of abbreviation mechanism - sugar for an arbitrary collection of function type constraints:

    // adhoc is like an interface: it is about collecting signatures
    // but it is not a type: it dissolves during compilation 
    adhoc AMyNeeds<T, U>
    {
         nonvirtual operator (*) T (T, T) 
         nonvirtual Foo U (T)
    } 

    U SuperSquare<T, U>(T a) applying AMyNeeds<T, U>        
    {
        return Foo(a * a);
    }

At some place "main" all the type arguments are known and everything becomes concrete and can be compiled together.

What's missing still is the lack of creating different implementations. In the upper example we just used polymorphic functions and let everybody know...

Implementation then again could follow the way of extension methods - in their ability to add functionality to any class at any point:

 public static class SomeAdhocImplementations
 {
    public nonvirtual int Foo(float x)
    {
        return round(x);
    }
 }

In main you now can write:

    int a = SuperSquare(3.0f); // 3.0 * 3.0 = 9.0 rounded should return 9

The compiler checks all "nonvirtual" ad hoc functions, finds both a built-in float (*) operator and a int Foo (float) and therefore is able to compile that line.

Ad hoc polymorphism of course comes with the downside that you have to recompile for each compile time type so that the right implementations get inserted. And probably IL doesn't support that being put into a dll. But maybe they work on it anyway...

I see no real need for instanciation of a type class construct. If anything would fail on compilation we get the errors of the constraints or if those were boundled together with an "adhoc" codeclock the error message could get even more readable.

    MyColor a = SuperSquare(3.0f); 
    // error: There are no ad hoc implementations of AMyNeeds<float, MyColor> 
    // in particular there is no implementation for MyColor Foo(float)

But of course also the instanciation of a type class / "adhoc polymorphism interface" is thinkable. The error message would then state: "The AMyNeeds constraint of SuperSquare has not been matched. AMyNeeds is available as StandardNeeds : AMyNeeds<float, int> as defined in MyStandardLib". It also would be possible to put the implementation in a class together with other methods and add the "adhoc interface" to the list of supported interfaces.

But independant of the particular language design: i don't see the downside of adding them one way or the other. Save statically typed languages will always need to push the boundary of expressive power, since they started by allowing too little, which tends to be a smaller set of expressive power a normal programmer would have expected to be possible...

tldr: i am on your side. Stuff like this sucks in mainstream statically typed languages. Haskell showed the way.

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?

Answer 5

But still no "mainstream-language" provides [type classes.]

When this question was asked, this might have been true. Today, there is a much stronger interest in languages like Haskell and Clojure. Haskell has type classes (class / instance), Clojure 1.2+ has protocols (defprotocol / extend).

What's the reasoning against [type classes]?

I don't think that type classes are objectively "worse" than other polymorphism mechanisms; they just follow a different approach. So the real question is, do they fit well into a particular programming language?

Let's briefly consider how type classes are different from interfaces in languages such as Java or C#. In these languages, a class only supports interfaces that are explicitly mentioned and implemented in that class' definition. Type classes, however, are interfaces that can be later appended to any already defined type, even in another module. This kind of type extensibility is obviously quite different from the mechanisms in certain "mainstream" OO languages.

---

Let's now consider type classes for a few mainstream programming languages.

Haskell: No need to say that this language has type classes.

Clojure: As said above, Clojure has something like type classes in the form of protocols.

C++: As you've said yourself, concepts were dropped from the C++11 specification.

On the contrary: Concepts, which are a quite analogical idea, have been excluded from the next C++!

I haven't followed the whole debate around this decision. From what I've read, concepts weren't "ready yet": There was still debate about concept maps. However, concepts weren't given up completely, it is expected that they will make it into the next version of C++.

C#: With language version 3, C# has essentially become a hybrid of the object-oriented and functional programming paradigms. One addition was made to the language that is conceptually quite similar to type classes: extension methods. The main difference is that you're (seemingly) attaching new methods to an existing type, not interfaces.

(Granted, the extension method mechanism is not nearly as elegant as Haskell's instance … where syntax. Extensions methods are not "truly" attached to a type, they are implemented as a syntactical transformation. In the end however, this doesn't make a very big practical difference.)

I don't think this is going to happen anytime soon — the language designers probably won't even add extension properties to the language, and extension interfaces would even go a step further than that.

(VB.NET: Microsoft has been "co-evolving" the C# and VB.NET languages for some time, so my statements about C# happen to be valid for VB.NET, too.)

Java: I don't know Java very well, but of the languages C++, C# and Java, it is probably the "purest" OO language. I don't see how type classes would fit naturally into this language.

F#: I've found a forum post explaining why type classes might never get introduced into F#. That explanation centers around the fact that F# has a nominative, and not a structural type system. (Though I'm not certain whether this is a sufficient reason for F# not to have type classes.)

Answer 6

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.