Wolfgang wrote:
>Michael Hanus wrote:
>
>> Sergio Antoy wrote:
>>> [...]
>>> Is there a clear reason why x should NOT be shared across the
>>> arguments of (?), but must be in any other situation?
>>
>> Intuitively, sharing must be kept as long as the different
>> subexpressions belong to one expression. Thus, x is shared
>> in (1+x ? zero x) as long as you don't evaluate the (?).
>> However, if you evaluate (?), the complete expression
>> is reduced to the left OR right expression so that
>> the connection between both have been dropped.
>
>I think there is some sort of confusion here between sharing
>and non-deterministic search. Of course the variable in
>1+x ? zero x is shared between both arguments of (?). However,
>a variable *must* not be shared between different branches of
>a non-deterministic choice -- unless one can prove that the
>variable is bound to the same value in all branches (which is
>trivially the case when the variable is bound to a head normal
>form). Thus at the time when (?) is evaluated it creates two
>different search branches with independent instances x1 and
>x2 of the variable x. In the first branch one reduces
> 1+x1 ? zero x1 ~~> 1+x1 ~~> suspension
>and in the second one reduces
> 1+x2 ? zero x2 ~~> zero x2 ~~> {x2=0} success
>
>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.
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. 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.
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.
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.
Cheers,
Sergio
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Mi Okt 31 2007 - 18:47:10 CET