Deforestation in Mercury

[Fergus Henderson]

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?

> 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.

> 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.

> 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.

This issue is discussed in the draft paper, but I think the discussion
there has plenty of room for improvement and in fact may be a little
misleading.

Cheers,
	Fergus.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "Binaries may die
WWW: <http://www.cs.mu.oz.au/~fjh>  |   but source code lives forever"
PGP: finger fjh at 128.250.37.3        |     -- leaked Microsoft memo.