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.