Re: A New Approach to the Implementation of Type Classes

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

Original-Via: uk.ac.nsf; Fri, 1 Mar 91 19:19:27 GMT
Date: Fri, 1 Mar 91 10:58:14 GMT
From: Mark.Jones@prg.oxford.ac.uk
To: haskell@edu.yale.cs
Subject: Re: A New Approach to the Implementation of Type Classes
Sender: haskell-request@cs.glasgow.ac.uk


Simon Peyton Jones mentions a number of interesting points in his reply
to my article, and I'd like to say a few words about them here.

Firstly, Simon points out that the Glasgow compiler translates my example:

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

to give:

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

which certainly doesn't cause the problem of repeated construction of the
dictionary d1 that I described.  My original translation was based on the
approach taken in the type classes paper, rather than the more sophisticated
translation scheme described in "A static semantics of Haskell".

However, I do not think that sophisticated translation schemes can completely
eliminate repeated construction of dictionaries, even using the program
transformations that Simon describes.  As an example, consider the expression:

                       map (example x) zs

Surely (please correct me if I'm wrong) this will still entail the repeated
construction of d1 for each element in the list zs?

Once again, program transformation (partial evaluation) might help to
eliminate this repeated work, but I do not think this will always be
practical and/or possible (e.g. what would happen if example had been
defined in a separate module?  The type signature in the interface for
the module does not carry enough information to properly describe which
dictionaries will need to be constructed).  Compare this with my approach
which extends the type system with just enough information to make such
transformations unnecessary.

[Incidentally, whilst I very much like the idea of program transformation,
my own time is limited and I cannot hope to include the more sophisticated
transformations in my own work.  Although they will be essential in any
high quality optimising compiler, it would be nice if less sophisticated
systems could also give reasonable performance without the need for
complicated transformations.]

Finally, at the risk of changing the direction of this discussion, I am
rather puzzled by the idea that it would be easier to apply strictness
analysis to:

|   map f xs = map' xs where map' [] = []
|                            map' (x:xs) = f x : map' xs
 
rather than the original definition of map.  Whilst I can see that the
definition of map' takes only a first-order argument, surely we still
need to account for the abstract value of f in finding the abstract
value of map' ... which seems to lead us straight back to the problem
we started with.  Could somebody enlighten me please?
 
Mark