- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

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

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,

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

exactly that reason.

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.)

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.

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/curryReceived on Mi Okt 24 2001 - 11:51:45 CEST

*
This archive was generated by hypermail 2.3.0
: Fr Okt 23 2020 - 07:15:02 CEST
*