Hi Heribert,
| The idea is that for every class assertion in the type of a variable,
| the variable gets an additional parameter that will be instantiated by a
| value representing the appropriate instance declaration. These values
| are tuples (let's call them "instance tuples") containing
| - one component for every superclass (viz. an instance tuple) and
| - one component for every class method (viz. a function with an
| additional argument expecting the instance tuple)
This is exactly the scheme proposed by Wadler and Blott in their paper
"How to make ad-hoc polymorphism less ad-hoc"! The things that you've
called "instance tuples" here are more commonly referred to as
"dictionaries", and so the translation that is used to implement
overloading by adding these extra dictionary parameters is known as
the "dictionary passing translation". It is also the implementation
technique used in all current Haskell compilers/interepreters, as far
as I'm aware. I'm not particularly proud of them, and they weren't
the main topic, but you can find a couple of chapters, going into
many of the gory details of all this in my thesis (Chaps. 7 and 8, to
be precise.
[Historical aside: I did, however, produce a version of Gofer at one
stage that didn't use dictionaries: the compiler still used a
dictionary passing translation internally, but then followed that
with a specialization phase so that no dictionary values were used
at run-time. To my initial surprise, it actually resulted in smaller
compiled programs in every example that I tried. Two caveats: (1) the
technique doesn't work well with separate compilation, and would need
a very fancy linker; (2) the introduction of polymorphic recursion in
Haskell means that there are programs for which the technique cannot
be used. You can read more about this in my paper on "Dictionary-free
overloading".]
| - Does this work completely as intended or have I missed something, such
| as strictness problems or the like?
Well I hope I've dealt with all this above. One thing to note,
however: when you add extra arguments to a variable definition, you
can end up with a function where there wasn't one before, and that
has an impact on which computations get shared, and which don't.
So it can have an impact, and that was one of the original motivations
for the "dreaded monomorphism restriction", which is still there
lurking in the definition of Haskell 98.
| - Does this still work if more complex features of the type/class system
| are used?
Yes to all the things you listed. (Except your last point --- "dependent
types" --- to which I'd reply that I'm not exactly sure what you were
referring to ... perhaps the kind of work that Hongwei Xi has been
doing? Or maybe to the kinds of things that you've seen in Lennart's
Cayenne? Or perhaps something else.)
| - Can the transformed program be evaluated as efficiently as the
| original one? (The original program gets an advantage if some class
| constraints are resolved at compile time. But perhaps a similar effect
| for the transformed program can be achieved with GHC's transformation
| rules.)
The real question here is how can the program be executed at all
*without* doing the translation. This is one of the criticisms
that has been made of Haskell's class mechanisms, and one of the
motivations for other proposals. You might, for example, want to
take a first look at Odersky, Wadler, and Wehr's "A second look
at overloading" to see the kind of compromises that you might need
to make and the benefits that you might hope to gain.
| - Do type classes provide an advantage with respect to expressiveness of
| types? For example, can the types of an API be formulated in a more
| flexible way with classes as compared to the transformed style?
They shouldn't, in theory, but along the route to Haskell, some
additional expressiveness snuck in. Dictionary components in
Haskell, for example, can have polymorphic types (think of fmap
in the Functor class), but the components of a tuple in a regular
Haskell type cannot. Similarly, before Haskell went official and
allowed polymorphic recursion, you could still code it up by
hacking with classes. You can restore the balance by adding
support for rank-2 polymorphism, as is done in Hugs and GHC.
Once that's don't you don't get an extra expressiveness by programming
with type classes, but it might still make some programs seem easier
to code (because you don't have to add the extra parameters yourself).
[Historical aside 2: when constructor classes were first introduced,
several people (myself included) wrote about the "Expressiveness
of constructor classes" ... it was only later that I realized how
much of that expressiveness came from rank-2 polymorphism instead
of higher-order kinds. I wrote something about this in the tail
sections of my paper on "First-class polymorphism with type inference"
if you want to know more.]
| Most of this is probably well-known stuff and written down in papers.
| Which ones? The Haskell report concentrates on the static semantics of
| classes and instances. It looks like the dynamic semantics is expected
| to be already understood by the reader or intuitively clear. Are the
| references [6] (Jones: A system of constructor classes: overloading and
| implicit higher-order polymorphism) and [11] (Wadler/Blott: How to make
| ad hoc polymorphism less ad hoc) of the report available on the Web?
Well I think I've given a few pointers to get you started! Philip
Wadler's papers on this are available from:
http://cm.bell-labs.com/cm/cs/who/wadler/topics/type-classes.html
My own papers are available via my home page:
http://www.cse.ogi.edu/~mpj
(Some of the more recent items listed there have yet to make it to
the publications page proper.)
Hope this helps!
Mark
