[m-dev.] Re: Deforestation in Mercury

[Olaf Chitil]

Simon Taylor wrote:
> 
> > 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.

Thank you very much for your information. I'm looking forward to read your
thesis next week. I just fear I have to read a bit about Mercury before...


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

I just read on comp.lang.functional that Mercury programs usually don't make
much use of higher-order functions. This may make deforestation for Mercury
easier. Deforestation for Haskell definitely has to cope well with higher-order
functions.


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

I don't consider turning non-terminating programs into terminating ones as a
serious problem. However, it may be annoying when you write a non-terminating
program by mistake and don't notice it because the compiler turns it into a
terminating one. It may take a long time until you notice your mistake.

Olaf

-- 
OLAF CHITIL, Lehrstuhl fuer Informatik II, RWTH Aachen, 52056 Aachen, Germany
             Tel: (+49/0)241/80-21212; Fax: (+49/0)241/8888-217
             URL: http://www-i2.informatik.rwth-aachen.de/~chitil/