[mercury-users] Mercury applications, AI, backtracking

[Fergus Henderson]

On 14-Sep-1998, Don Smith <dsmith at cs.waikato.ac.nz> wrote:
> 
> Sure, Mercury has good language support for expressing deterministic code,
> and it tries to pay for nondeterminism only where it's really needed.
> But if my application is quite deterministic (as the vast majority of 
> conventional applications are), then why would I choose Mercury over, 
> say, Haskell or Clean?

One reason why you might choose Mercury over Haskell or Clean is that
Haskell and Clean use lazy evaluation whereas Mercury uses eager
evaluation.  Lazy evaluation certainly does have its advantages, but
it also has some significant disadvantages.

One disadvantage of lazy evaluation is that it makes things
less efficient.  Of course modern compilers for lazy functional languages
do their best to optimize away laziness where it is not required.
However, although they do a pretty good job with regard to optimizing
lazy functions, they do a bad job of optimizing away the laziness of
lazy data structures.  Furthermore, the effort spent optimizing laziness
means that less effort is available for implementing other optimizations.
(The same applies to nondeterminism in Mercury, of course -- the effort
required to implement nondeterminism means that less effort is available
for other optimizations -- but the point is that lazy functional languages
are no better than Mercury in that respect.)

But as well as making things more difficult for the implementor,
laziness can also make things more difficult for the programmer.
Laziness makes the operational semantics much more complicated (and the
optimizations to avoid laziness make it even more complicated, and less
predictable).  The complicated operational semantics makes debugging
more difficult.  They also make it much harder to reason about
performance.  Indeed, laziness can cause space leaks in ways that are
difficult for even highly experienced functional programmers to
diagnose.  Because the whole performance model much more complicated,
Haskell is a much worse language for "close to the metal" or even
"moderately close to the metal" programming.

Another issue is that while nondeterminism in Mercury is easily
isolated, so that you only pay the price when you're using it,
lazy evaluation is generally not so easy to isolate in lazy functional
languages.

OK, so your next question is why use Mercury rather than ML?
Well, one reason is that Mercury is a purely declarative language.
(Or rather -- since Mercury _does_ support impure code now -- I
should say that Mercury provides a much cleaner interface between
pure code and impure code, with static checking to ensure that
pure code doesn't call impure code except where the programmer
explicit promises that the impure code has a pure interface.)

Another reason is the support for unique modes.  This is related to the
purity issue, since ML does of course provide imperative features such
as destructive update, but it doesn't give them a declarative
interface.

> Maybe one could argue that Mercury is good 
> because it is a single, universal language that supports both deterministic 
> and nondeterministic programming.  (But functional languages can simulate 
> some backtracking, using list comprehensions.)   

Note that you have to use *lazy* lists to simulate this properly
(unless you want breadth-first search rather than depth-first search).
So doing this in a non-lazy functional language is a bit more complicated:
first you simulate laziness, then you use simulated lazy lists to simulate
backtracking ;-)

> Operating systems, spreadsheets, device drivers, file systems, GUIs,
> graphics packages, word processors, and food processors typically won't
> need backtracking, it would seem.  (Yet on second thought I wonder
> whether committed choice nondeterminism  -- cc_multi and cc_nondet --
> may not come in handy in lots of applications.

Yes, I think it does.

It would be possible to add support for committed choice
nondeterminism to functional languages such as Haskell using
an abstract data type representing a set (I posted an article
outlining this to the Haskell mailing list a couple of months
ago, which I can forward to anyone who is interested.)

In the functional community this issue has been glossed over a bit,
since the Haskell IO Monad includes committed choice nondeterminism
(as well as I/O and exception handling!).
The IO Monad is less expressive than the aforementioned set ADT
would be or than committed choice nondeterminism in Mercury is,
since it forces you to impose sequentiality.

> Does the Mercury compiler make much use of 
> {cc_}nondet and {cc_}multidet modes?)

No.  But most of the Mercury compiler was implemented well before
we added support for those modes.

-- 
Fergus Henderson <fjh at 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 at 128.250.37.3        |     -- the last words of T. S. Garp.