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

From: Wolfgang Lux <wlux_at_uni-muenster.de>

Date: Wed, 31 Oct 2007 19:11:04 +0100

Sergio Antoy wrote:

*>> So it do think that (?) is treated differently than other
*

*>> operations.
*

*>
*

*> If the variable is NOT shared, one has to make some exceptions,
*

*> e.g., a Wolfgang say, (?) must be treated differently.
*

Ooops. The statement you quoted above was missing a NOT (sorry).

I really wanted to say that (?) is treated in the same way as

all other functions.

*> A troubling point is that unless the variable is shared,
*

*> the order of evaluation matters. For example, consider:
*

*>
*

*> let x free; p = zero x; q = 1+x; zero 0 = 0 in (p, p?q)
*

*>
*

*> A problem with sharing the variable is that implementations based
*

*> on backtracking may become more difficult.
*

I do not see that it makes things more complicated -- at least

not fundamentally. Upon backtracking you have to restore the old,

unevaluated state of the variable. This is not much different from

resetting bound logical variables to their unbound state and is

exactly what is implemented by MCC. BTW, the same is done in Prolog

implementations which support attributed variables.

*> On the other hand, a
*

*> problem with NOT sharing the variable, is that some optimization
*

*> become more difficult. E.g., consider:
*

*>
*

*> positive(1+x ? zero x) where x free
*

*>
*

*> Which step should be executed first? Not the reduction of (?)
*

*> because if neither argument evaluates to a head normal form,
*

*> the reduction of (?) would not serve any purpose.
*

Maybe I'm too dense today, but I did not understand this.

*> To refine Wolfgang's statement, consider:
*

*>
*

*> (0 ? 1, f x) where x free
*

*>
*

*> Here, x is not bound a head normal form, however, sharing it
*

*> among the two branches of (?) is a good idea.
*

Why? x is used only in the argument of so it does not really

matter whether it shared or not. But you may want to share

the result of f x -- at least if its evaluation is deterministic.

*> Maybe Curry should always share variables and let the programmer
*

*> choose whether or not to share a variable. The syntax allows this
*

*> easily and there may be a reasonable way to share a variable
*

*> across the branches of (?) also in implementations based on
*

*> backtracking.
*

I think sharing of variables across different branches of a

non-deterministic choice should only be a matter of optimization.

An implementation *may* choose to share variables across

non-deterministic branches if it can prove that this does not affect

the results computed (though eventually the order in which they are

computed). On the other hand, within a particular branch of a

non-deterministic search, all occurrences of a variable should be

shared. Again, an implementation *may* choose to omit sharing within

a particular branch under the same condition that it does not affect

the results computed. An example for the latter could be simple

arithmetic operations, for which it might be more efficient to

recompute them rather than sharing their result.

Regards

Wolfgang

_______________________________________________

curry mailing list

curry_at_lists.RWTH-Aachen.DE

http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry

Received on Do Nov 01 2007 - 09:49:20 CET

Date: Wed, 31 Oct 2007 19:11:04 +0100

Sergio Antoy wrote:

Ooops. The statement you quoted above was missing a NOT (sorry).

I really wanted to say that (?) is treated in the same way as

all other functions.

I do not see that it makes things more complicated -- at least

not fundamentally. Upon backtracking you have to restore the old,

unevaluated state of the variable. This is not much different from

resetting bound logical variables to their unbound state and is

exactly what is implemented by MCC. BTW, the same is done in Prolog

implementations which support attributed variables.

Maybe I'm too dense today, but I did not understand this.

Why? x is used only in the argument of so it does not really

matter whether it shared or not. But you may want to share

the result of f x -- at least if its evaluation is deterministic.

I think sharing of variables across different branches of a

non-deterministic choice should only be a matter of optimization.

An implementation *may* choose to share variables across

non-deterministic branches if it can prove that this does not affect

the results computed (though eventually the order in which they are

computed). On the other hand, within a particular branch of a

non-deterministic search, all occurrences of a variable should be

shared. Again, an implementation *may* choose to omit sharing within

a particular branch under the same condition that it does not affect

the results computed. An example for the latter could be simple

arithmetic operations, for which it might be more efficient to

recompute them rather than sharing their result.

Regards

Wolfgang

_______________________________________________

curry mailing list

curry_at_lists.RWTH-Aachen.DE

http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry

Received on Do Nov 01 2007 - 09:49:20 CET

*
This archive was generated by hypermail 2.3.0
: Mo Feb 06 2023 - 07:15:10 CET
*