[bitc-dev] Type Classes: Pragmatics Questions

Jonathan S. Shapiro shap at eros-os.org
Tue Jul 19 22:48:36 EDT 2005

There are some purely pragmatic issue concerning type classes that
concerns me.

One claim about type classes is that it is often possible to derive the
concrete type at compile time, and if you know this you can partially
evaluate out the wrapper procedure and the runtime dictionary
indirection. This especially important for things that are close to
ground in the type system. If we have to execute the path through a
generalized + operator, for example, we end up executing something like
the following:

   push arg2
   push arg1
   push num-dictionary-for-concrete-type
   jmp abstract-+   [1]
   ...which does...
   movl %eax,(%esp) [1]
   call *offset_for_+(%eax)
   ... at target ...
   movl %eax,4(%esp)
   addl %eax,8(%esp)
   addl %esp,$12

when what we wanted was


We can improve on this if we know that the operator invoked is a
constant binding by eliminating the instructions marked [1], but we can
only reduce it to a single instruction if both the operator "+" is
evaluated from a constant binding and the actual parameter type (and
therefore the correct instantiation) is concretely known.

In practice, we will usually know the operator as a constant. In O'Caml
and Haskell, where the numeric types are Int, RealFloat, Complex, and
<something else>, I suspect it is rare for the concrete type to be

I am concerned that in BitC, where there is a larger number of integral
and floating point types, it is likely to be more difficult to establish
a concrete type if the ground operators do not assist in reducing the
permissable selections of type by the unifier. Obviously, we're not
going to do it at all when we are looking at a use that is buried inside
some larger scale generic procedure.

This raises three questions that I am unable to answer. I would
appreciate enlightenment from people who are more experienced with

1. I would really appreciate it if someone with greater experience in
this than we have could give some intuition about how much trouble we
should expect in establishing concrete integral types in the normal

2. It is moderately distressing that performance of abstract containers
should rely so intensively on optimization. Is there any published,
coherent discussion of how to compile this sensibly and efficiently?

More information about the bitc-dev mailing list