# Proposal: Lazy matching for local patterns

From: Wolfgang Lux <lux_at_wi.uni-muenster.de>
Date: Mon, 22 Oct 2001 17:04:54 +0200

Hello,

the semantics of purely functional programs in Curry is mostly similar
to that of Haskell (except for the handling of overlapping rules).
However, there is one major difference, which results in valid Haskell
programs to fail under Curry: The lifting algorithm given in appendix
D.8 of the report is too strict wrt local patterns. E.g. consider the
definition

foo xy = length [x,y]
where (x,y) = xy

In Haskell the expression "foo undefined" evaluates to 2, while in
Curry this expression fails. Another example is

bar n xy =
| n == 0 = success
| otherwise = x =:= y
where (x,y) xy

for which the expression "bar 0 undefined" is going to fail even though
the argument xy is not used at all.

The reason for these failures is the lifting algorithm of appendix D.8
which transforms local patterns declarations into additional arguments
of an auxiliary function. E.g., the definition of foo above is
translated into (after removing unused variables)

foo xy = foo' xy
foo' (x,y) = length [x,y]

This translation demands too much evaluation. A better solution is to
use accessor functions in order to extract the components of the
pattern:

foo xy = foo' (fst x) (snd y)
foo' x y = length [x,y]

With this definition the evaluation of "foo undefined" will no longer fail
but yield 2.

In order to get this behaviour, I propose to change the sub-paragraph
Eliminate patterns on pp. 71f into

Select a local pattern declaration which contains only argument
variables from the main function's left-hand side in the expression,
i.e., the rule has the form

l = C[let { decls_1; p = e'; decls_2 } in e]_p

with free(e') \subset free(l). Then transform this rule into the rules

l = C[f' x_1 ... x_k e']_p
f' x_1 ... x_k z = f'' x_1 ... x_k (f_1 z) ... (f_m z)
f'' x_1 ... x_k y_1 ... y_m = let { decls_1; decls_2 } in e
f_1, ..., f_m eval rigid
f_1 p = y_1
...
f_m p = y_m

where x_1 ... x_k are all the variables occurring in l, y_1 ... y_m
are all the variables occurring in p, z is a new variable symbol and
f', f'', f_1 ... f_m are new function symbols. Repeat this step until
all local pattern declarations are eliminated.

This translation can be optimized in a few special case. If p is just a
variable the function f' is not needed and the definition of l can be
simplified into

l = C[f'' x_1 ... x_k e']_p

Similarly, when e' is a variable the function f' is also not needed and
the definition of l can be replaced by

l = C[f'' x_1 ... x_k (f_1 e') ... (f_m e')]_p

The evaluation annotation for the f_i serves the purpose to avoid a
possible instantiation of the result of e' by any of the functions f_i,
which is IMHO not very useful and -- due to the lazy evaluation of the
applications -- in fact unpredictable.

Regards
Wolfgang

```--
Wolfgang Lux				  Phone: +49-251-83-38263
Institut fuer Wirtschaftinformatik	    FAX: +49-251-83-38259
Universitaet Muenster		      Email: wlux_at_uni-muenster.de
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
```
Received on Di Okt 23 2001 - 08:51:12 CEST

This archive was generated by hypermail 2.3.0 : Mi Okt 28 2020 - 07:15:04 CET