Linearity Requirement for Patterns

[Fergus Henderson]

On 20-Mar-2001, Michael Hanus <mh@informatik.uni-kiel.de> 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
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 <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.