Mercury applications, AI, backtracking

Don Smith dsmith at cs.waikato.ac.nz
Mon Sep 14 14:32:14 AEST 1998


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

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?)

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?

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.

For NLP applications, I wonder whether Mercury lacks an expressive
typed feature structure system (as in ALE or Life).  Has anyone 
looked at this?

Rather than asking, "Can Mercury be used to implement an operating system?" 
I think we should ask:  "Can it be used to program a good theorem prover, 
unification grammar, planner, or constraint-based scheduling system?"

       Don



More information about the users mailing list