Mercury

[Fergus Henderson]

On 05-Mar-1999, Zuurbier, E. - AMSXE <Erik.Zuurbier@KLM.NL> wrote:
> > > The generated code must be as efficient as Clean's.
> > 
> > I haven't run any benchmarks against Clean, but I suspect
> > that we probably pass this criteria in most circumstances.  
> > We don't have to worry about lazy evaluation, which makes
> > generating efficient code a lot easier.
>
> Fergus, can you explain why lazy evaluation is so loved
> by functional programmers and, in contrast, apparently
> a non-issue in Mercury? Or else, would it be possible and
> useful to extend Mercury with lazy evaluation?

I just meant that it was a non-issue as far as the current
Mercury implementation is concerned, since currently we
don't support lazy evaluation.  It would certainly be
possible and potentially useful to extend the current
Mercury implementation to support lazy evaluation.

> I can imagine that Mercury programs that make use of the
> specific Logic-properties of the language, would virtually have
> to be redesigned (rather than run through a simple transformation)
> to convert them to Clean, which does not support multiple
> modes, for instance.

Few Mercury programs make *essential* use of multiple modes, so generally
it would be reasonably straight-forward to convert them to Clean.

An important exception is programs that make use of Mercury's support
for constraint solving (e.g. the CLP(R) interface).  These could be
converted to a language like Clean, but only at the cost of explicitly
passing around and returning the constraint store everywhere, and in
addition adopting a meta-representation for all variables, which is
a pretty high price to pay in terms of readability and declarativeness.

> But what about the other way around? What would a Mercury
> programmer do with lazy Clean algorithms to implement them
> in Mercury? If it is a mere syntax conversion, or some straight
> forward transformation, that is great. Tell me where I can read more
> about it.

It is indeed basically just a syntax conversion.  See
<http://www.cs.mu.oz.au/~lee/papers/eq/>, in particular section 7 of
the tech report there.  This deals with adding support for functions
and lazy evaluation to NU-Prolog, via a simple pre-processor.

Some of the issues discussed in that paper are slightly different in Mercury,
since Mercury is a strongly-typed and strongly-moded language.  For example,
in Mercury there's no need to use quote/1 to prevent evaluation, since you
can use overloading instead.  Also in Mercury you'd want to use some kind
of explicit destructive update for memoing the result of a computation
(thus giving you call-by-need rather than call-by-name),
rather than using the hack with dynamically moded Prolog variables and
var/1 described in that paper.  Indeed, using destructive update would be
better even in Prolog, since the technique described in the paper can
cause space leaks.  But to summarize, adapting those techniques to Mercury
would be reasonably straight-forward.

You could also look for stuff on `force' and `delay' in Scheme, 
since that is basically about the same thing.

I have an implementation of lazy (call-by-name) lists in Mercury lying
around somewhere which I can dig up if anyone is interested.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3        |     -- the last words of T. S. Garp.