Let me introduce a new example in relation with this discussion:
consider the program
f 0 = 0
g 1 = 1
I think that a Curry (or Toy) programmer would expect
that the expression f 0 ? g 0 would reduce to 0 (and not more values)
and that the expression f 1 ? g 1 would be reduced to 1 (and not more values).
independently of wether the implementation uses backtraking or not.
Now, consider the expression
f x ? g x where x free
Curry or Toy programmers expect answers covering the ground reductions above.
That is: one answer giving x/0 and the value 0, and another giving x/1 and 1.
I wonder what should be obtained in Sergio's proposal.
Best,
Paco
PS: I cannot react during some days.
----- Mensaje original -----
De: Wolfgang Lux <wlux_at_uni-muenster.de>
Fecha: Miércoles, Octubre 31, 2007 7:11 pm
Asunto: Re: [curry] Intended meaning
A: antoy_at_cs.pdx.edu
CC: mh_at_informatik.uni-kiel.de, curry_at_lists.RWTH-Aachen.DE
> 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
>
********************************
Francisco J. Lopez Fraguas
Dep. Sistemas Informaticos y Computacion
Fac. Informatica U. Complutense Madrid
Prof. Jose Garcia Santesmases s/n
28040 Madrid
Spain
fraguas_at_sip.ucm.es
Tel: +34 91 3947630
Fax: +34 91 3947529
********************************
_______________________________________________
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:24 CET