[m-dev.] Re: Deforestation in Mercury

[Fergus Henderson]

On 19-Nov-1998, Simon Taylor <stayl at cs.mu.OZ.AU> wrote:
> [Fergus wrote:]
> > On 18-Nov-1998, Olaf Chitil <chitil at informatik.rwth-aachen.de> wrote:
> > > 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.

Right.

> We still have to make
> sure we don't turn a terminating program into a non-terminating one.

Not necessarily.

The Mercury language semantics specifically allows the compiler to
generate code which does not terminate, when given programs that would
terminate under the strict sequential semantics but not under the
strict commutative semantics.

So unless the user has explicitly requested the strict sequential semantics,
it is perfectly OK, according to the specification in the Mercury language
reference manual, for enabling the deforestation optimization to change
the behaviour of the program from terminating to non-termination,
if that program was not guaranteed to terminate under the strict commutative
semantics.

If the current implementation of deforestation is not taking advantage
of the permissions allowed by the language reference manual, then it
sounds to me like there is a problem either in the implementation
of deforestation or in the language reference manual, and that problem
ought to be fixed.

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.