Re: Proposal: Lazy matching for local patterns (fwd)

From: Wolfgang Lux <lux_at_wi.uni-muenster.de>
Date: Wed, 24 Oct 2001 11:02:25 +0200

Oops, the following answer to German's mail did not make it to the list
(I must have hit the wrong button :-)


Hi German,

> Yes, I agree with your proposal. When programming in Curry,
> I usually rewrite the above function to something like
>
> bar n xy
> | n == 0 = success
> | otherwise = bar' xy
>
> bar' (x,y) = x =:= y
>
> in order to avoid the problem you mentioned. And this situation
> occurs very often in practice...

I have made the proposal (and implemented it in our compiler :-) for
exactly that reason.

> Just one thing:
>
> > 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.
>
> I'm not sure about this change. In principle, one expects
> that variables get instantiated by local declarations
> (indeed, this is how it actually works in PAKCS).

This should happen only in a flexible function (like bar) but not for
rigid functions. E.g. for

  rigidBar n xy
    | n == 0 = True
    | otherwise = x == y
    where (x,y) = xy

the expression "foo z" where z is a free variable should suspend and
not instantiate z (at least according to the current semantics).
(Anyway, even if z were instantiated the evaluation would suspend
because z is only instantiated to the pair (x1,x2) where x1 and x2 are
free variables and then x1 == x2 suspends.)

> What could be the problems? Could you provide a concrete
> example?

The problem is the following. Without an evaluation annotation for
the accessor functions (and without a global pragma) the default rules
apply. E.g., the accessor functions

  f_1 (x,y) = x
  f_2 (x,y) = y

generated for the expansion of bar and rigidBar are both rigid
functions. Thus, "foo z" and "bar 1 z" where z is a free variable
will both suspend.

Now, if we replace the pairs by the type

  data StrangePair a = StrangePair Success a

the new accessor functions are now

  f_1 (StrangePair x y) = x
  f_2 (StrangePair x y) = y

where f_1 is now flexible function (because its result type is Success)
and f_2 is still rigid. Ignoring for a moment the fact that the Success
type is abstract and does not support equality, the result of the
application "bar z" would depend on the order in which the accessor
functions are evaluated. If f_1 z -- i.e. the x argument of bar' -- is
evaluated first, then z is instantiated to a pair (x,x) while if f_2 z
-- i.e., y -- is evaluated first, the evaluation suspends. In order to
avoid such situations, all accessor functions should use the same
evaluation mode which is achieved by adding the evaluation annotations
to the program.

The question then is, which mode to use for theaccessor functions?
Probably, the best thing is to require that the accessor functions use
the same mode as the function in which the pattern declarations occur
(this would be compatible with current report). However, this mode
depends on whether an evaluation annotation for the function or a
global pragma is present and eventually on the type of the function.
>From my last discussion with Michael I suspect he doesn't like to
introduce such dependencies into the lifting algorithm. So the
remaining choices are either eval flex or eval rigid.

In most -- if not all -- cases where I use local pattern declarations
I want them to be rigid (they are all of the kind of the rigidBar example
where instantiating the pattern would lead to another suspension
immediately) which lead me to suggesting rigid evaluation; but I'm open
to be convinced otherwise.

Wolfgang

P.S. In case you care, here is another example which does not rely on
equality for the Success type.

  data StrangeTriple = StrangeTriple Success Int Int

  rId c x | c = x
  f triple = x + rId g y
    where StrangeTriple g x y = triple

------- =_aaaaaaaaaa0
Content-Type: text/plain; charset=us-ascii

--
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 Wed Oct 24 2001 - 11:51:45 CEST

This archive was generated by hypermail 2.3.0 : Mon Sep 23 2019 - 07:15:05 CEST