On 20-Mar-2001, Michael Hanus
Jerzy Karczmarczuk wrote:
Logic languages which allow for nonlinear patterns use unification, which is usually much more costly than simple pattern compiling. Now, I wonder whether in FP where there is no place for "logical variable" concept one needs or doesn't need the classical unification, with all the substitutions of variables. "Read-only" patterns are manipulated more efficiently, but in presence of laziness, of ~patterns etc., I feel - for the moment - rather lost.
What is the status of the referential transparency of Prolog or Mercury?
Prolog isn't referential transparent due to predefined predicates with side effects. However, logic programming ("pure Prolog") is referentially transparent if one considers a "non-deterministic" semantics where an expression is reduced to a disjunction of expressions (Prolog systems explore this disjunction in a left-to-right manner by backtracking).
I would talk about disjunctions of "goals" rather than disjunctions of "expressions". This is perhaps a pedantic distinction, but when you start talking about referential transparency it is important to be very precise, because often the distinctions are a matter of terminology.
Actually, one can extend Haskell by "logical variables" in a conservative manner. This is the idea of the functional logic language Curry
My understanding, from talking with Michael Hanus a few years ago, is
that Curry is not referentially transparent, in the sense that you can't
replace equals with equals, because it permits nondeterministic functions.
In particular, `let x = f y in g x x' is not the same as `g (f y) (f y)'
in Curry.
--
Fergus Henderson