A New Approach to the Implementation of Type Classes

[Mark.Jones@prg.oxford.ac.uk]

Original-Via: uk.ac.nsf; Thu, 28 Feb 91 09:08:49 GMT
Date: Wed, 27 Feb 91 15:26:27 GMT
From: Mark.Jones@prg.oxford.ac.uk
To: haskell@edu.yale.cs
Subject: A New Approach to the Implementation of Type Classes
Sender: haskell-request@cs.glasgow.ac.uk


The following article describes a new approach to the use of type classes,
which I believe will enable a much more efficient implementation of
overloading using type classes.

The complete article is rather long and so I am sending only the first
part to this mailing list.  Please send me mail (mpj@prg.ox.ac.uk) if
you would like a copy of the full article.  Alternatively, if there is
sufficient interest, I will post it article to this list in a couple of
days.

I hope this will be of interest to fellow Haskell enthusiasts ...  Any
comments gratefully received.

Mark
______________________________________________________________________
A New Approach to the Implementation of Type Classes:
-----------------------------------------------------

A Problem Involving Numbers:
----------------------------
Suppose I ask you to find a number whose last digit is 1 which is also
a multiple of 13?  Perhaps you know a formula that can be used to find
an answer?  Maybe you could use a `lookup' table?  Or would an `exhaustive
search' be easiest?

However you decide to go about it, you'll need a couple of moments to
come up with an answer.

On the other hand, suppose I tell you that 91 is a multiple of 13 and
ask you to give me its last digit.  This time you hardly need to think
at all.  The answer to the problem is immediate.

Compile-time vs Run-time:
-------------------------
Now imagine that we are compiling a program that needs to use a multiple
of 13 ending in the digit 1 (not a common requirement, I confess).  We
have two options:
either - the compiler generates code which will produce a solution when the
         program is executed,
    or - the compiler solves the problem itself and compiles its solution
         into the code it produces.  This approach should produce smaller
         and faster executable programs, at the (probably marginal) cost
         of a slower but more sophisticated compiler.
Obviously, the second option is preferable, given the usual assumption
that the program will be used many more times than it is compiled.

But What Has This Got To Do With Type Classes???
------------------------------------------------
To explain the relevance of the above discussion to the implementation
of type classes, consider the function:

    example x []     = False
    example x (p:ps) = p==(x,'c') || example x ps

The type inferred by a Haskell system is:

    example         :: Eq a => a -> [(a,Char)] -> Bool

and the definition of example is translated to use explicit dictionary
arguments giving:

    example' d x []     = False
    example' d x (p:ps) = ((==) (dictEqPair d dictEqChar) p (x,'c')) ||
                          example' d x ps

where dictEqChar is the dictionary for Eq Char, and dictEqPair is the
dictionary constructor function for Eq (a,b).

The evaluation of a call to example' for a non-empty argument list requires
the evaluation of (dictEqPair d dictEqChar) to construct a dictionary for
Eq (a,Char).  We then select a single member function before discarding the
rest of the newly constructed dictionary.  Clearly this is inefficient; and
the problem is even worse because this construction will be repeated at each
stage as example' makes its way through the argument list.

Going back to the type checking stage, we find that the type class constraint
originally generated requires an instance Eq (a,Char) and this is simplified
to Eq a using the instance declarations for Eq Char and Eq (a,b).  Having
spotted this, a more natural typing for example is probably:

    example :: Eq (a,Char) => a -> [(a,Char)] -> Bool

which more accurately reflects the use of equality in example and leads to
the translated definition:

    example'' d x (p:ps) = (==) d p (x,'c') || example'' d x ps

Using this definition, the use of type classes does not carry a significant
run-time cost (the only overhead is the extra argument to example'').

Of course we will still need to construct a suitable dictionary before
using example'' ... but unlike the original example, this only needs to be
done once.  More importantly, since the type with which the type variable
`a' is instantiated at each occurrence of example'' is known when the program
is compiled, we can arrange for the compiler to construct all of the
dictionaries that will be required at compile-time, completely eliminating
the need to construct new dictionaries at run-time.
______________________________________________________________________