[bitc-dev] Type Classes for BitC

[Jonathan S. Shapiro]

It's finally time to deal with the overloading issue. Mark Jones has
graciously joined the discussion, so I look forward to being flogged by
the expert here. :-) Rebekah should definitely chime in too! [One
advantage of being the list admin is I know who is lurking... :-)]

Far too long ago, I declared that I wasn't going to do six billion
variations on the operator '+'. From a usability perspective, it's
simply not practical for us to adopt the O'Caml approach, because it's
not just a matter of integers and floats. BitC has 8 distinct integral
types and 3 distinct floating point types -- maybe four if you count
Pentium extended, which I have no plans to support in BitC.

Speaking purely on pragmatic grounds, I think I can get users to accept
that you can only add two quantities if they are the same type, but I
really don't think that I can get people to accept 12 addition operators
with pleasant names like

  +i8 +i16 +i32 +i64 +u8 +u16 +u32 +u64 +f32 +f64 +f128

Yuck!


Haskell-style type classes would allow us to resolve this by introducing
a type class Num similar to the one in Haskell. Here is a (bad) notional
syntax:

  ; Declare the type class. This introduces the method
  ; names as identifiers in the containing scope, so
  ; after this definition, "+" is defined in the
  ; containing scope.
  (deftypeclass Num
     + : (fn (tuple Num Num) Num)
     - : (fn (tuple Num Num) Num)
     ; ...
     / : (fn (tuple Num Num) Num))

  (definstance Num int32
     +i32 -i32 ... /i32)

That is, we are saying that the type int32 is a member of the type class
Num, and that the corresponding specializations of the type class
methods are as given (positionally).

One effect of the type class introduction is to implicitly define a
dictionary structure that maps the method names to type-specific
implementations.

So the "real" function "+" is actually a function with a third, hidden
argument: the dictionary. In any context where the type of the Num
argument can be resolved concretely, the compiler can inline the
dictionary lookup, which eliminates the need to actually pass the type
variable.


Okay. So much for my (poor) explanation of type classes. The proposal
under consideration is that we should introduce some variation of
Haskell-style type classes into BitC.  In the next few emails I will
explore a couple of issues that need to get resolved or that we need to
understand.


shap