Re: Intended meaning

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 Thu Nov 01 2007 - 09:49:20 CET

This archive was generated by hypermail 2.3.0 : Mon Sep 16 2019 - 07:15:06 CEST