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

[Michel Vanden Bossche]

Hi,

For unknown reasons, the mail I posted on the Mercury list Wednesday
didn't come through. Here it is.

Best regards,

Michel

On Tue, Jan 27, 2004 at 10:49:47AM +0000, Nicholas Nethercote wrote:
> 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?

Here at Mission Critical we do write Mercury programs for solving
real-life business problems.  The largest system that we have in
production (since October 2000) has on the order of 20,000 lines of
Mercury and 30 non-deterministic modes on a total of about 1,700 modes:

Total number of modes        >=   1685
                             =<   1926
        - det:                    1630 ( 96.74%)
        - semidet:                 245 ( 14.54%)
        - nondet:                   30 (  1.78%)
        - multi:                     6 (  0.36%)
        - cc_nondet:                 0 (  0.00%)
        - cc_multi:                  2 (  0.12%)
        - erroneous:                 4 (  0.24%)
        - failure:                   0 (  0.00%)

We are currently working on an ontology based system which is in
pre-beta.  This is our first parallel Mercury application
(multi-threaded server to improve scalability).  The critical kernel of
the application has on the order of 7,000 lines and shows the same kind
of distribution:

Total number of modes:       >=    459
                             =<    507
        - det:                     408 ( 88.89%)
        - semidet:                 309 ( 67.32%)
        - nondet:                   10 (  2.18%)
        - multi:                     0 (  0.00%)
        - cc_nondet:                 0 (  0.00%)
        - cc_multi:                 30 (  6.54%)
        - erroneous:                 0 (  0.00%)
        - failure:                   0 (  0.00%)

So yes, in most cases programs that are written are largely
deterministic, however as Ralph noted, sometimes having the
non-determinism is extremely useful.

In a more detailed example, we have written a Coloured Petri Net
implementation.  The heart of which requires a search to find a
transistion that can fire.  In the original naive implementation we used
commited choice non-determinism to ensure that we found a transition to
fire, but also keep the deterministic properties of the program at the
same time.  In the latest implementation we still use cc_nondet, but now
have reduced the search space by being a little bit smarter in our
algorithm.

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

I think the same could also be said for laziness in Haskell.  Most of
the time it is not needed, but sometime it is extremely useful.

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

I believe that many people see logic programming and they think Prolog,
and that they don't realize that Mercury was designed with building
large scale systems in mind.  We consider Mercury as a "general purpose
language" to develop "evolving dependable software intensive systems"
(of course not "hard" real-time).
 
As a matter of fact, we tend to agree with Allan Robinson when he calls
"classical" logic programming, relational programming, and the
combination of functional and relational programming, logic programming.


Here at Mission Critical, we find the two aspects of Mercury the most
important.  

1. The fact that it allows one to use a higher level of 
   abstraction and so focus on solving the problem in hand 
   rather than worrying about the low level details of
   programming the machine. 

2. The dependability of the written code, by this we mean 
   that we can be sure that our code is correct to with 
   respect to what we have declared about our program, 
   types, modes, determinism and so on.

These two aspects allow us to write code which requires minimal
corrective maintenance (fixing bugs) and where adaptive maintenance
(adding new features) is simplified as the high level abstraction means
less to change and the checking ensures that we quickly determine all
the places that need to be changed.

Two additional remarks...

Being a pure declarative language, static analysis of Mercury code is
much easier.  This has been leveraged to develop an experimental
Compile-Time Garbage Collector that looks very promising. 

Up till now, we haven't had performance problems (see attached graph
with the response time for the change of the state of a business
process, the system being used by about 100 users). Of course, this is
not yes a very large systems with 10,000+ concurrent users ;-)

Best regards,

Michel Vanden Bossche
Mission Critical



-------------- next part --------------
A non-text attachment was scrubbed...
Name: PFlowPerformance.jpg
Type: image/jpeg
Size: 35879 bytes
Desc: not available
URL: <http://lists.mercurylang.org/archives/users/attachments/20040130/f91ae82c/attachment.jpg>