[mercury-users] Re: Microsoft Common Lisp?

[Fergus Henderson]

Holger Schauer wrote:
> 
> In comp.lang.lisp Fergus discussed some differences between
> Turbo Prolog (nowadays called Visual Prolog) and (ISO-)Prolog.

(Actually the thread was crossposted; I was reading it on comp.lang.misc.)

> I would be interested in which respect you would say Mercury differs
> from standard prolog and from Visual Prolog.

Mercury differs significantly from both. 

For a brief overview of Mercury features, see
<http://www.cs.mu.oz.au/mercury/features.html>.

I have experience with Turbo Prolog, but I don't have any experience
with Visual Prolog, so I'll address my comments to Turbo Prolog.
However, from what I have heard the Visual Prolog language is
essentially the same as Turbo Prolog (only the environment and
extra-linguistic tools have changed).

One significant difference is that Visual Prolog and ISO Prolog are
both logic programming languages, whereas Mercury integrates logic
and functional programming.  In a sense this could be regarded as just
syntactic sugar, but it is nevertheless very nice syntactic sugar.
Using functions and named constants (zero-arity functions) is often
very elegant and makes many things a lot more concise and/or more
readable.

Another even bigger difference is that Mercury is purely declarative:
predicates and functions in Mercury do not have non-logical side
effects.  There are no non-logical builtins such as cut or var/1.
Every Mercury predicate or function has a declarative interpretation.
In contrast, Turbo Prolog and ISO Prolog could be described as
``imperative languages with logic variables and backtracking'';
in the vast majority of programs, most predicates do not have
declarative interpretations.

Mercury does I/O through built-in and library predicates that take an
old state of the world and some other parameters, and return a new
state of the world and possibly some other results.  The language
requires that the input argument representing the old state of the
world be the last reference to the old state of the world, thus
allowing it the state of the world to be updated destructively.
backtracking will not be needed.  Mercury also requires that I/O take
place only in parts of the program where backtracking will not be
needed.  (The compiler checks this.)  This gives code that does I/O a
clean declarative semantics and allows a nice clean semantic interface
between code that does I/O and code that does not.  The I/O state
threading is usually made automatic by the use of DCGs.

Mercury and Turbo Prolog are very different from ISO Prolog in
that both Mercury and Turbo Prolog have strong static typing, and
static mode and determinism analysis.  However, Mercury's type, mode,
and determinism systems are significantly more expressive than
Turbo Prolog's.

In Turbo Prolog type declarations are always required, but the mode and
determinism analysis are normally implicit.  Turbo Prolog performs
global mode and determinism inference.  Mercury puts greater emphasis
on the software engineering advantages of explicitly declaring
interfaces.  In Mercury, type, mode and determinism declarations can be
inferred within a module, but the default behaviour is to require them,
and for predicates exported from a module they are always required.

There are two major differences in the type system of Mercury and Turbo
Prolog, as well as several minor ones.  The major (IMHO) differences
are

	- Mercury's type system supports parametric polymorphism
	  whereas Turbo Prolog's does not.  (Turbo Prolog does
	  have one polymorphic data type -- lists are treated
	  as a special case -- but it doesn't allow any user-defined
	  polymorphic data types or predicates.)

	- Mercury's type system supports higher-order predicates,
	  whereas Turbo Prolog's does not.  

These differences make Mercury's type system much more expressive
than Turbo Prolog's.

Another quite significant difference is that Mercury also supports
sub-types (through the mode system), which Turbo Prolog does not.
(I can explain that in detail if someone wants.)

Another significant difference is that Mercury supports a "universal"
data type called `univ'; anything can be converted to type univ and
back.  If you attempt to convert a univ back to a different type than
the one it was created from, the conversion will fail.  This is a bit
like a safe equivalent to C's `void *'; it provides an "escape" from
static typing for those rare occaisions on which you need to create
heterogenous data structures or provide inferfaces which cannot be
statically typed.

One example of the use of `univ' is functor/3 and arg/3.  The next
release of Mercury will support equivalents to [the forwards mode of]
Prolog's functor/3 and arg/3.  [We're working on the backwards modes too,
but that's not complete yet, so it might not be ready for the next release.]

Turbo Prolog supports a `symbol' data-type, which is interchangeable
with strings but has different performance characteristics -- because
symbols are stored in a symbol table, creation of symbols is slower,
but equality tests can be a simple comparison.  In Mercury,
programmers tend to use enumerations instead, if the set of symbols in
a type is known in advance.  Enumerations in Mercury are represented as
integers 0, 1, 2, ..., so they are more efficient than symbols would
be.  You could use enumerations in Turbo Prolog too, although I don't
know how the Turbo Prolog compiler represents enumerations.

Turbo Prolog allows implicit conversions from real to integer and vice
versa; conversion from real to integer is done by truncation.  Mercury
does not.  (Silent truncation is a feature I'm quite happy to live without ;-)

Although both Mercury and Turbo Prolog support defining one type as
equal to another, the semantics are different.  In Mercury, the two
types are fully interchangable (just as with typedef in C).  In Turbo
Prolog, if two different types, say apples and oranges, are defined as
equal to integer, Turbo Prolog will ensure that you don't mix apples
and oranges.  But unfortunately it is only possible to define a type to
be equivalent to one of the basic types (integer, char, real, string,
or symbol).

To get distinct types in Mercury, you have to define the
types using an explicit functor to distinguish between them,
e.g.

	:- type apple ---> apple(int). 
	:- type orange ---> orange(int). 

The Mercury compiler avoids any runtime overhead for such functors:
types apple and orange are represented in exactly the same way as type int.

Mercury's determinism system is a lot more flexible and expressive than
Turbo Prologs `nondeterm' declaration.  Mercury's determinism analysis
includes inferring when predicates cannot fail.  Users can declare when
a predicate cannot fail (which is almost invariably a useful thing for
the reader to know).  The compiler will check such declarations,
allowing it to catch at compile time the very common error of a
predicate failing even though the programmer intended it to always
succeed.  The compiler also uses this information to generate better code.

Mercury also allows committed-choice nondeterminism.  If only one
solution is required, the Mercury compiler will automatically prune
away unnecessary alternatives, or (more often) it will avoid creating
any choice points in the first place.  This is done in a declaratively
sound manner, without all the semantics problems caused by cuts.
In Mercury, if you use determinism declarations the you never get
any unexpected nondeterminism or space leaks due to unpruned choice
points.  In Mercury, you do have to write code in a slightly different
style sometimes, using if-then-elses instead of cuts, but and you don't
have to worry about first-argument indexing, cuts, and so forth.

Mercury and ISO Prolog support DCGs, Turbo Prolog does not.

Mercury and ISO-Prolog allow if-then-elses, Turbo Prolog does not (at
least not last time I looked).

Mercury's negation and if-then-else and all-solutions primitives
are logically sound, whereas Turbo Prolog's and ISO Prolog's are not.

> How does Mercury perform when it comes to handling knowledge which is
> not good handled at compile-time i.e. some kind of meta-reasoning (you
> know, like asserting some rule and being able to call it afterwards) ?

I find these general questions a little bit difficult to answer --
it would be much easier if you gave me a Prolog program and said
"how would I write this in Mercury"?

Mercury doesn't have assert and retract, but I didn't find them very
useful in Prolog, except as ways of implementing global variables.
[Yes, there are ways of implementing global variables in Mercury too.]
Mercury does have ways of constructing predicates at runtime and
then calling them -- namely higher-order predicates.  Mercury's support
for higher-order predicates is in fact a lot better than ISO Prolog.
ISO Prolog does provide sufficient primitives to support them,
but only very inefficiently, and most Prolog compilers do a quite bad
job of optimizing them.  Also Mercury has lambda expressions, which
Prolog doesn't.  Turbo Prolog is worst -- it has not support at all
for higher-order programming.

Many things that you can do in ISO Prolog are done differently in Mercury.

In ISO Prolog, you can use variables in non-logical ways as a means of
achieving (backtrackable) destructive update.  This is often used in data
structures like open-ended trees and in non-ground meta-programming,
because without it, you can't get reasonable efficiency.
I don't know off-hand whether Turbo Prolog's mode system lets you do
that sort of stuff.  In Mercury, destructive update is achieved using
unique modes.  Unfortunately that is one part of the current Mercury
implementation that isn't complete (we're working on it!).  In the
mean time, Mercury has a quite good C interface that you can use to
implement (non-backtrackable) destructive update using inline C code --
and when Mercury 1.0 comes out, you'll be able to implement those parts
using the Mercury standard library instead.

Mercury does not have ISO Prolog's preprocessing (term_expansion),
although it's quite easy to do preprocessing as a separate step, and
the GNU make based Mercury build environment can handle this quite easily.
Mercury's module system, named constants and cross-module inlining mean
that there is little need for a C-style preprocessor.

Turbo Prolog does not have garbage collection.  (They still haven't fixed
this in Visual Prolog, from what I hear.)

Mercury and Turbo Prolog do not have exception handling; ISO Prolog does.
(We know how to implement it, we're just not sure whether it is a good idea.)

Mercury and Turbo Prolog have module systems. ISO Prolog does not, at least
not yet -- they're working on it.

There's probably a few more differences I've forgotten, but I won't go on.
Still, I'd be very happy to answer any "how would I rewrite this Prolog
program in Mercury?" type questions.  I think that some examples would
illustrate things better.

Cheers,
	Fergus.

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