On 20-Mar-2001, Jerzy Karczmarczuk
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