Linearity Requirement for Patterns

Jerzy Karczmarczuk
Tue, 20 Mar 2001 11:20:19 +0000

Michael Hanus wrote:
> Lennart Augustsson wrote:
> > Yes, your definition of non-linear patterns would give you extra
> > power.  It would also destroy the nice semantics of Haskell!
> > By using this facility you can now observe intensional properties
> > of the term, and the clean denotational semantics crumbles.
> > So this definitions of non-linear patterns is not an option for a
> > language that claims to be "referentially transparent" (whatever 
> > that means :).

> However, I agree that there are good reasons (mainly, operational
> simplicity) to allow only linear patterns and constructor-based
> rules in a real programming language, since non-linear patterns
> or non-constructor-based rules require other and more advanced
> operational principles. I only wanted to remark that there is
> no simple way to translate non-linear pattterns into linear
> patterns in the general case.
> Michael

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

What is the status of the referential transparency of Prolog or

Anybody, with a clever comment on that?

Jerzy Karczmarczuk
Caen, France