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

Sandro Magi naasking at higherlogics.com
Sun Apr 8 17:28:02 PDT 2012


On 08/04/2012 3:06 PM, Jonathan S. Shapiro wrote:
> 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).

This semantics always struck me as odd as well, though I've convinced
myself that Haskell's trivial solution is mostly workable, which is why
it hasn't been fixed yet. Namely, just define a newtype and declare an
instance for the newtype, ie.

data Foo = Foo ...
class Bar a where ...
instance Bar Foo where ...

useBar :: Bar a => a -> ...

-- we now want an overloaded instance of Bar, so:
newtype Foo2 = Foo2 Foo
instance Bar Foo2 where ...
...
  useBar Foo2 foo

The only problem with this solution is that you lose the natural
isomorphism with the original Foo, so this requires "wrap/unwrap" at the
coercion boundary. Two possible solutions to this:

 1. Introduce an iso relation of sorts so that Foo2 instances can be
used where Foo is used. Depending how you do it, this could have a
subtyping flavour, so no doubt it will be fraught with subtleties.

 2. Take the named instances proposal you linked to, and additionally
add a (implicit?) phantom type to each class which specifies the
instance selected. You can then discriminate which instances were used
where by the name.

These are not based on any deep analysis of the problem though, just
standard type tricks that worked in other domains.

> 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.

The obvious solution seems to simply provide a single guarantee:
efficient code generation/inlining of these overloads only when whole
program compilation is possible. At first, this would only be provided
when source is available, so you didn't need a runtime linking
architecture. This obviously limits the use of binary blobs, but you
can't inline those in general anyway.

> 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.

Perhaps the problem was really trying to co-opt type classes for laying
out record structures. You really wanted a record calculus, and
conflating overloading with record operations will inevitably lead you
down the rabbit hole of subtyping and inheritance (which also conflate
the two). I'm partial to Leijen's first-class labels [1], but that's
probably overkill for BitC.

Sandro

[1] http://lambda-the-ultimate.org/node/174



More information about the bitc-dev mailing list