Linearity Requirement for Patterns

[Fergus Henderson]

On 20-Mar-2001, Jerzy Karczmarczuk <karczma@info.unicaen.fr> wrote:
> 
> Logic languages which allow for nonlinear patterns use unification,
> which is usually much more costly than simple pattern compiling.

That's true, but the exceptions are important.
If you have sufficient compile-time mode information, then unification
need not be more costly than simple pattern matching.

> What is the status of the referential transparency of Prolog or
> Mercury?

As Michael Hanus said, Prolog is not referentially transparent because
it has a large variety of builtins that violate referential transparency.

For Mercury, the short answer is that yes, Mercury is referentially
transparent.

Still, I guess you want the long answer ;-)
Mercury's declarative semantics are referentially transparent.
Modifying some Mercury program by replacing equals with equals always
preserves the program's declarative semantics.  However, such
transformations do not necessarily preserve the operational semantics;
the transformed program may not terminate when the original does,
or may compute the set of solutions in a different order.
The same is true for pure Prolog.

Haskell's denotational semantics is referentially transparent.  AFAIK
Haskell doesn't have a standard operational semantics, but the typical
operational semantics used are also referentially transparent.  However,
if you use a more detailed operational semantics, e.g. one which takes
into account the fact that machines have finite memory, then the same
kind of thing applies to Haskell too: replacing equals with equals may
not preserve the operational semantics, because the transformed program
may run out of memory when the original didn't.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.