[bitc-dev] Retrospective: The Issues with Type Classes

Jonathan S. Shapiro shap at eros-os.org
Sun Apr 8 12:06:59 PDT 2012


I promised two weeks ago that I would send out a note addressing the
problems with type classes specifically. Here goes....

Anticipating confusion, let me say first that type classes are a very
powerful and useful idea. Especially so when the compiler is "in on the
joke" about what they mean. They allow the programmer to express new,
orthogonal factorings of types, and this is a *very* useful thing. They
also allow some degree of proof structure to be embedded in the program in
the form of type relations, which becomes especially powerful when a
kinding system is present - see what Mark Jones is doing in Habit as an
example. Finally, they provide a useful and general framework for
constraint propagation within the compiler.

So my objection here isn't to type classes as constraints at all, nor to
type classes *per se*. In fact, I would say that *certain* type classes in
BitC turned out to be tremendously useful.


The first problem we ran into appears to be generally recognized, but also
seems to be pooh-poohed in a lot of the languages community: type classes
can only be instantiated once at any given concrete type. From the
perspective of getting a practical job done, this is problematic:

   - The "one instance per type per program" rule defies programming in the
   large.
   - The "non-overlapping instances" rule defies specialization. There are *
   many* examples where I want to have a general (polymorphic) type class
   that has specialized implementations at certain types. For example, I want
   Collection('a) having a generally parametric instance, but simultaneously
   having a specialized instance at Collection(char).

The first problem is strictly practical and entirely obvious: two groups
build libraries, each defines instances of Mumble(char). Years later their
libraries get linked into a single program, and *Kaboom*. What has happened
here is so glaringly obvious that one wonders how this rule can be deemed
acceptable by most of the PL community: type class instances do not respect
rules of scope. I have a horrible confession to make. I recognized this
problem in Haskell's typeclass system from the very first moment. I simply
did not believe that the PL community could be so willing to ignore its own
history as to imagine that this state of affairs would continue. I
*assumed* that
the problem was a transient artifact of Mark Jones' initial work, and that
I would find a solution in the type classes literature as I proceeded. I
was wrong.

The long and short of this, in my opinion, is that type class instance
resolution *must* be performed by some form of lexical scoping. The
difficulty with this is that there are really only two ways to accomplish
that:

   1. Pass instance pointers at procedure calls, effectively turning type
   class instances into generalized Interfaces
   2. Require instances to be lexically visible to the *consuming* code.
   That is: require Arith(int32) to be lexically visible in all source modules
   that publish a function that can be instantiated at Arith(int32).

In practice, neither answer is entirely satisfactory. There are strong
motivating cases for both, and even one or two motivating cases for both
simultaneously.


Two approaches attempting to address this kind of issue have been brought
to my attention:

   - The work by Kahl and Scheffczyk: *Named Instances for Haskell Type
   Classes*
   - The work by Oliveira and Sulzmann: *Objects to Unify Type Classes and
   GADTs*

Neither, to my mind, offers a comprehensive solution. I find Oliveira's
work thought provoking, but mainly because it is strange. It leaves me with
an itchy feeling in my mind that Oliveria's solution isn't what I want but
there ought to be a related solution lurking around the corner from his
that should work.* *If there is, the keys to it lie in the fact that type
class instances are deep constants and *closed* type class instances (Bruno
calls these *sealed*) can be fully known at the point of use.



The second issue with type classes is more subtle, and mainly has to do
with operator overloading. It was very attractive in BitC to use type
classes at low-level operators. Most notably, the core arithmetic operators
(+, -, *, /) were type class methods. The efficient compilation of these
operators (and a few others) is so overwhelmingly critical that late
binding on these operators cannot be endured. Yet we want them to be
extensible. The problem with having ground operators defined by type
classes is that (a) we usually can't resolve the instance statically,
because it isn't in scope, and (b) having failed to resolve the instance,
we can't inline the operators, which can be performance-critical.

BitC's eventual solution to this was unattractive: we moved the definitions
into the preamble, with the result that they could not be overridden
elsewhere. Once the compiler knew this, it could compile these cases
aggressively. For basic arithmetic this was fine. For comparison operators
(which have inverses), it was less so. The problem with the comparison
operators lies in the fact that we may want to reverse the sort order later
while still writing the code to use the symbol '<' as the ordering
operation.

Having said that it is unattractive, it is practical. Certain types are
intimately intertwined with the compiler. You can make claims for
abstraction all you want, but final code performance demands that the
compiler be able to rely on certain things, including certain low-level
types.

I'd also add in hindsight that the problem with ordering is a bit of a red
herring. The alternative view is that the sort() function really shouldn't
be written to use '<' internally. In this view, '<' is not an arbitrary
total ordering operator; it is a well-known total ordering operator having
connotations to a human. In this view, Ord('a) should capture the notion of
a "natural" ordering, and we should have a separate way of capturing a sort
order. We probably want that separate way to be something like a type
class, because we want to take advantage of the compile-time-constant
nature of type class instances to perform eager specialization, but as
programmers we want to distinguish between "use the natural ordering" and
"use the ordering of the current sort".



The third issue with type classes is not so much an issue with type classes
per say as it is a problem with how I hoped to use them: type classes do
not replace inheritance.

In BitC, we introduced a built-in type class *has-field*. If struct S has
field *f* with type *T*, then has-field(S, f, T). This was a bit of a
kludge, in that the language doesn't admit atoms in general, but that's
minor and fixable. The interesting point is that it generalizes readily to
member functions and to structure methods (which we *did* have). Which
means that it can provide something very similar to a subclass relation at
parameters. To the extent that this works, *has-field* subsumes inheritance.

What *has-field* does *not* subsume is virtual member functions, though it
can actually be made to serve there. The problem is that without some form
of encapsulated This type, we end up with parametricity rather than
encapsulation. In most cases this is okay, but in some cases we really need
encapsulation. The single inheritance pattern, whatever its flaws, provides
a nicely controlled form of encapsulation.

So this isn't a critique of type classes as much as it is an observation
that type classes and object classes aren't the same thing and aren't
interchangeable. The catch is that you are now forced to contemplate the
introduction of object classes and inheritance. Once you do that, you end
up in a place where *almost* everything done by type classes and type class
instances can now be done by classes and object instances. The only thing
missing, really, is a way to get the deep constant and compile-time
constant properties captured so that we can inline things aggressively
enough to use this approach at ground operators. And *that* actually seems
to me like something that could be done. In the end, I'm left wondering
what purpose general type classes would still serve in such a system. The
built-in classes continue to have value as a way to capture, trace, and
manage constraints within the compiler implementation, but that's quite
different from user-extensible classes.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.coyotos.org/pipermail/bitc-dev/attachments/20120408/b19e5e0a/attachment.html 


More information about the bitc-dev mailing list