[mercury-users] Mercury applications, AI, backtracking

[Tyson Dowd]

On 14-Sep-1998, Don Smith <dsmith at cs.waikato.ac.nz> wrote:
> Hi,
> 
> I am wondering: is it reasonable to expect Mercury to succeed as a
> _mainstream_ programming language when the vast majority of
> conventional applications would seem to involve little or no
> backtracking? (But see below.)
> 
> 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?     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.)   

A few reasons.

1. Mercury may be faster than Haskell or Clean.  

A project to translate Mercury to Haskell (in an effort to run Mercury
programs faster) ended up showing that Mercury ran the programs
faster than Haskell anyway.  Mercury doesn't pay the cost of laziness,
and only pays for nondeterminism when it is used.

2. Logic programs offer features functional languages do not have.

Non-determinism.
Multiple input/output arguments
	(sure, it's just syntax, but it's nice syntax).
Reversible relationships
	(even if you don't use nondet, deterministic ones are nice).


3. Mercury's features and tools.

Type classes.
Existential types.
Termination analysis.
Tabling.
Submodules.

Many more being worked on right now (deforestation, deductive database
backend, accumulator introduction, type specialization, advanced
profiler, exception handling, debugger, etc).

4. Licensing.

The Mercury implementation has easy licensing conditions.
LGPL for the library (which is pretty unrestricted if you want to
use it as a library) and GPL for the compiler.  With this combination
you can write whatever programs you like in Mercury -- for profit,
for education or for fun.  You can also change the library and
compiler in any way you please under the GPL, and so you are not
tied to us for support in any way.

Concurrent Clean has a non-commercial/non-profit only license, you need
to buy a license from them for anything else.  You may not modify Clean.

Nobody knows what the licensing conditions are on GHC.
Strictly speaking, nobody is allowed to download and use GHC at all.
Some people claim GHC is public domain, which is obviously false because
there are copyright notices in the code!  Hugs isn't too bad, but for
commercial use you still need to get the permission of the authors.


> 
> 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.  For example, in an OS 
> one might want to get the first element of a queue that satisfies some
> constraints. Or, an optimizing compiler might use a bit of backtracking 
> for finding better orderings.  Does the Mercury compiler make much use of 
> {cc_}nondet and {cc_}multidet modes?)

s/modes/determinisms.

It doesn't make much use of committed choice, but then the compiler is an
atypical application because it has been largely written in an
intersection of Prolog and Mercury for bootstrapping reasons.
As the new execution tracer is quite functional now, the day is
fast approaching where that may change.

Nondet code isn't common, but it is used (usually with solutions).

But I belive cc_nondet and cc_multi are quite useful for doing
introspection and external interfaces as well as committed choice
selection.

> It seems to me that Mercury's strengths should be in high-level domains
> like deductive databases, NLP, theorem proving, planning, and constraint-
> based search.  (Many of these need full unification, it seems.) You can 
> code in Mercury in an imperative style, using unique modes, but if 
> basically all of your code is imperative, then one might as well use an 
> imperative or functional language, no?

You might as well use a functional language?  That's fine.
Except you have to do all that syntactic packing
and unpacking because functional languages have this fundamental idea
that a relationship is a one way function, and therefore has a single
return value.  And bijective functions need to be written twice.

So if you're writing in a functional language (and not desparate for
builtin laziness), you might as well write in Mercury anyway, use the
functional syntax, and take advantage of the syntactic convenience of
multiple input and output variables.  You don't pay anything for
non-determinism if you don't use it.

You might as well use an imperative language? I doubt it.
You have to give up (at least some of) higher order,
polymorphic types, automatic memory management, type classes, a
whole stack of static analysis and checking, a semantics without
side effects, etc.  And that means giving up the productivity
benefits that go with them.

> One thing that concerns me, though, is that for constraint-based
> applications, chronological backtracking is often inappropriate. You
> may claim that you can implement intelligent backtracking on top of
> chronological backtracking, but if the language doesn't provide
> explicit support, it's hard to code it efficiently and you end up
> rolling your own.     Heuristic search needs flexible support for 
> committed choice nondeterminism, I think.

Mercury does not dictate chronological backtracking except in
the strict sequential operational semantics (which is must be
provided in an implementation, but need not be the default).

It is quite possible for an implementation to add a number of
search strategies (including user defined) and have them applied
using a `pragma'.  Obviously there would be some up-front work involved
in allowing this.

--
Tyson.