[mercury-users] cost/benefit analysis of non-determinism in Mercury

[Ralph Becket]

Hi Nicholas,

how's tricks back in Cambridge?  God, I miss the beer sometimes.

Nicholas Nethercote, Tuesday, 27 January 2004:
> One of Mercury's distinguishing characteristics is its support for
> non-determinism.  However, my gut feeling is that people using Mercury for
> writing real, large programs use non-determinism very little.  Can anyone
> estimate the number of predicates in the Mercury compiler (or other large
> Mercury programs) have a non-deterministic procedure?

$ grep ':- mode.*is multi' ~/mercury/mercury/compiler/*.m | wc -l
     14
$ grep ':- mode.*is nondet' ~/mercury/mercury/compiler/*.m | wc -l
     55

So the compiler doesn't use that many!  I think part of the problem is
that we're only just putting in proper support for Herbrand types (i.e.
types supporting full Prolog style unification) and constraint types,
both of which rather go hand-in-hand with non-determinism.  Another
thing is that few programmers are comfortable with non-determinism at
all.  My own experience is that non-determinism is something you only
need every now and then (unless you're writing theorem provers or
planners or type checkers or register colouring algorithms or...), but
on those occasions it can be indispensible.

> This led me to wonder:  if one removed non-determinism from Mercury, how
> much simpler would the implementation (compiler, debuggers, profilers,
> runtime system) be?  In terms of lines of code, and general
> understandability and maintainability.

We do make some use of "reversible" computation, where the same code
for appending two lists, say, can be used also for testing for and/or
identifying prefixes and suffixes of a list and also the partitions of a
list, merely by adding an extra mode declaration.

It's not clear to me that ditching non-determinism would make the goal
reordering required for this sort of thing noticably simpler.

> This thought came from me thinking about Haskell, which I think is a great
> language -- pure, statically typed, functional -- except for the default
> laziness, which I consider an unfortunate evolutionary hangover, rather
> than a good feature.  Mercury is also pure, statically typed, functional;
> it also has a feature (non-determinism) that, to me, is a baroque remnant
> of its heritage, albeit one that's far less intrusive than Haskell's
> laziness.

You can use Mercury as a strict, pure functional language and not pay
any performance penalty (although our type classes aren't yet as
powerful as Haskell's and our syntax is a little weightier and our
version of currying is more limited.)

An interesting direction we want to take Mercury in is to migrate the
extensible constraint logic programming facilities from HAL to Mercury
(otherwise there's actually little real difference between the
languages: HAL compiles to Mercury anyway).

> Drifting off-topic, I wonder how many people have been put off learning
> Mercury because they thought it was like Prolog?  Ie. pigeon-holed it as a
> "logic/AI" language, rather than a general-purpose language.  In my
> experience, lots of people are very dismissive of Prolog.

Yes, in the same way that many people dismiss Haskell etc. as toy
languages.  Prolog does have many flaws, but it also has full
unification.  I'm working on adding Herbrand types supporting Prolog
style unification to Mercury as we speak, so hopefully some of the
motivation for teaching an impure language like Prolog will go away
after that [he says, tongue firmly in cheek.]

-- Ralph
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------