Re: A New Approach to the Implementation of Type Classes

[Simon L Peyton Jones <simonpj@cs.glasgow.ac.uk>]

To: haskell@cs.glasgow.ac.uk
Cc: simonpj@cs.glasgow.ac.uk
Subject: Re: A New Approach to the Implementation of Type Classes 
Date: Thu, 28 Feb 91 10:22:41 +0000
From: Simon L Peyton Jones <simonpj@cs.glasgow.ac.uk>
Sender: haskell-request@cs.glasgow.ac.uk


Mark Jones posted an interesting message, pointing out some potential
repeated work in the translations of Haskell programs to resolve
overloading, and he suggests a way to fix the problem which involves
adjusting the type system somewhat.

There is certainly no theoretical objection to allowing more 
complicated contexts in function types, as he suggests, but I think
it is worth realising that the problem yields to at least two 
transformations which a compiler might wish to do anyway, without
requiring changes to the type system.

I elaborate below.  I'm afraid this is fairly long, but Mark's message
raises a number of interesting issues.

Simon

I begin by recalling his example:

| 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 eac
|  h
| stage as example' makes its way through the argument list.

A BETTER TRANSLATION SCHEME FOR OVERLOADING
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Absolutely right, but this isn't the translation which the Glasgow
Haskell compiler builds!  Instead, we generate the following translation:

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

This is of course, exactly what Mark suggests the caller doing.  The
d1 is shared between all the recursive invocations of example.

It is fair to ask whether we have to go to a lot of trouble and hackery
to get this laziness, and for once the answer is as pure as the driven
snow: this is what we do because of the way the static semantics rules
are formulated (and have to be, to cope with mutual recursion), and the
fact that it is lazy just comes out for free.  Indeed I hadn't really 
cottoned on to this aspect till Mark's mesasge came in (for which much
thanks).

Indeed the translation of mutually-recursive overloaded definitions
gets a section to itself in the paper "A static semantics of Haskell",
which Phil Wadler and I wrote, and which we'd be glad to send to anyone
who wants it.  (Warning: 45 pages.)


A GENERAL TRANSFORMATION TO IMPROVE OPPORTUNITES FOR FULL LAZINESS
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In general, though, it is often a good idea to transform a recursive
function defn such as 

	f x y z = .... (f x E z) .... (f x E' z) ...

where all the recursive calls leave certain arguments unchanged.
(They don't have to be the leading ones.) 

This can be transformed to:

	f x y z = f' y where f' y = ... (f' E) ... (f' E') ...

The main benefit of doing this is that it may expose opportunites
for full laziness.  For example, suppose that the second "..." part
contains the expression (length x).  In the original definition of f
(length x) would get recomputed at every call.  But in the new
definition, we can make a further transformation:

	f x y z = f' y where f' y = ... (f' E) ...v... (f' E') ...
		  	     v = length x

Now v will get computed only once.  This latter transformation is discussed
in "A modular, fully-lazy lambda lifter in Haskell", by David Lester and me,
which is to appear in Software P&E in May.  (Again, I can send you a copy if
you prefer.) The "modular" bit in the title refers to the main contribution
of the paper which is to show that full laziness can be introduced entirely
separately from lambda lifting; previously they were confused together, in
my mind at least.  

In any case, if both transformations are applied, even Mark's translation
of example will be lazy as he wanted.

This business of performing transformations to improve the opportunities for
full laziness seems to be a recurrent theme.  Carsten Kehler Holst's paper
"Improving full laziness" gives another lovely example of a transformation
which improves full laziness.  (It is in the process of being published. 
meanwhile his email address is kehler@cs.glasgow.ac.uk)


INTERACTION WITH LAMBDA LIFTING
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
An obvious question is: doesn't a lambda-lifter just re-introduce
all the arguments you have carefully lifted out?  Well, if you do
lambda lifting (which our compiler does not (!)), you will get either

	f x y z = f' y  where  f' = $f' v x z f'
			       v = length x
	$f' v x z f' y = ... (f' E) ...v... (f' E') ...

or (if you do it a la Johnsson) 

	f x y z = f' v x z y where v = length x
	f' v x z y = ... (f' v x z E) ...v... (f' v x z E') ...

Both still share the evaluation of (length x), which is done only once,
so we have still made progress.


INTERACTION WITH STRICTNESS ANALYSIS (and other static analyses)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The Glasgow Haskell compiler does NOT (yet) spot these recursions in 
which some arguments are unchanged.  But let me conclude by giving one
more reason why spotting such things is a Good Thing.  Consider map:

	map f [] = []
 	map f (x:xs) = f x : map f xs

Strictness analysers, even ones which can deal with higher-order functions,
have great trouble with this sort of definition, because they need to look
for the *fixpoint of the abstract version of map*.  Finding fixpoints is
worst-case exponential in the number of arguments, even if the arguments
cannot be functions, but it explodes horribly if the arguments are 
functions.  Even clever stuff like minimal function graphs / pending
analysis keels over.  It is MUCH easier to transform to:

	map f xs = map' xs where map' [] = []
				 map' (x:xs) = f x : map' xs

Now map, the function with a function argument, is not recursive,
so we don't need to find a fixpoint.  Only map' is recursive, and
it has only a first-order argument.

Indeed I will venture the following (wooly) hypothesis:

	For a large majority of higher-order programs, it is quite
	sufficient to perform the above transformation and then
	find good fixpoints only for first-order recursions.
	Effort invested in finding fixpoints for higher-order functions
	is largely wasted.