monomorphisation in Haskell

[Stephen Weeks]

> Thankyou very much for your prompt reply and helpful information. 
> I am very pleased to read about your technique - it is essentially the
> same thing that I do for Haskell programs. Up until now I thought that I was
> the only person doing this. It is somewhat reassuring that other people take
> the same approach. Note that I am not performing the transformation for
> compilation purposes, but rather for debugging purposes.

We were definitely not the first.  Reference [3] and [26] from another of our
papers, http://www.star-lab.com/sweeks/papers/00-esop.ps, point to other
monomorphisation work on SML.  One of those papers (or something by the same
authors) spells out in pretty gory detail their monomorphisation algorithm.  I
also vaguely remember hearing about someone doing monomorphisation of Haskell
for compilation purposes several years ago, but I can't remember the cite or
if there even was a paper.

> I imagine that you are still using the whole-program compilation scheme, which
> means you don't have any problems about module boundaries?

Yes.

> Monomorphisation is not possible in general (as far as we know) when you 
> encounter polymorphic recursion. I think this point is made in some of the
> material that Stephen sent me.
> 
> So we can only debug the subset of Haskell that is restricted to monomorphic
> recursion.

Although monomorphisation in the presence of polymorphic recursion may not
terminate, it may be possible in many (all?) instances to transform the
nonuniform datatypes and polymorphic recursion into uniform datatypes and normal
recursion.  Okasaki gives a hint how to do this on p 143 of his book.  I think
the technique that he describes there could be automated for use in a compiler
or debugger.  I don't know of anyone that's done so, but it would be very
interesting to see, IMO.