Linearity Requirement for Patterns
Thu, 22 Mar 2001 12:07:09 +1100
On 20-Mar-2001, Michael Hanus <firstname.lastname@example.org> wrote:
> 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
> 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)'
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.