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

From: FRANCISCO JAVIER LOPEZ FRAGUAS <fraguas_at_sip.ucm.es>

Date: Thu, 01 Nov 2007 08:12:08 +0100

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

Date: Thu, 01 Nov 2007 08:12:08 +0100

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

********************************

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

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