[m-dev.] Re: Deforestation in Mercury

[Simon Taylor]

> On 18-Nov-1998, Olaf Chitil <chitil at informatik.rwth-aachen.de> wrote:
> > In your announcement of Mercury 0.8 I read that you added deforestation to
> > your implementation. I am intested in deforestation but did not find any
> > further remarks on it on the Mercury web pages. 
> 
> Simon Taylor, who implemented deforestation, has written the first
> draft of a paper on it.  This paper is not yet on our web page since it
> is still a significant way from completion.  However, I think Simon
> would probably be happy to let you have a look at the draft.  Simon?

My Honours thesis is due next Monday. It contains an updated version of
the draft deforestation paper, so it's probably better to look at that.
I'll put it on the Mercury web page when it's done.

> > On which method is your deforestation based (e.g. a la Wadler, short cut
> > deforestation, hylomorphisms, etc)?
> 
> I think the method is our own invention, but see the paper for details.

It's an unfold/fold transformation, so in that sense is somewhat similar
to Wadler's, but it heavily uses the mode information provided by the compiler
to guide the transformation.

> > Is it really effective?
> 
> Depends on your coding style, I think.  Applying the optimization to
> the Mercury compiler itself apparently doesn't speed up it up to any
> measurable degree.  But I think the results on the various deforestation
> benchmarks are a lot better than that.

Definitely. The problem with the compiler is that it spends a lot
of its time in things like dictionary lookups to which deforestation
doesn't apply. Also, separate compilation gets in the way a little.

> > The only implemenations of deforestation in non-toy compilers I know
> > about, i.e. in GHC, were not very successful. I'm not familiar with
> > Mercury, but as far as I know it has a strict semantics. In contrast to
> > non-strict languages deforestation can turn non-terminating programs in
> > strict languages into terminating ones. Is that an issue for you?
> 
> Depending on the exact compiler options selected, it may or may not be
> an issue that the compiler has to worry about.  Have a look at the
> Semantics chapter of the Mercury language reference manual.

Turning non-terminating programs into terminating ones isn't necessarily
a bad thing, although it can be disallowed by choosing the appropriate
language semantics options as Fergus mentioned. We still have to make
sure we don't turn a terminating program into a non-terminating one.

Simon.