Linearity Requirement for Patterns
Thu, 22 Mar 2001 12:31:35 +1100
On 20-Mar-2001, Jerzy Karczmarczuk <firstname.lastname@example.org> 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
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
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 <email@example.com> | "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.