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 : Do Feb 01 2024 - 07:15:05 CET