Re: Intended meaning

From: Wolfgang Lux <wlux_at_uni-muenster.de>
Date: Thu, 08 Nov 2007 11:55:09 +0100

Sergio Antoy wrote:

> Not exactly. The semantics of non-determinism we intend in Curry
> is such that computations are confluent (except for the order and
> timing in which non-deterministic alternatives are produced), but
> here I see the problem as an interaction between order of
> evaluation, sharing and non-deterministic choices. The meaning of
>
> (f x ? g x where x free)
> as
> (f x where x free) ? (g x where x free)
>
> makes sense. Unfortunately, the language syntactically allows the
> first form and I am afraid one cannot catch all the variations of
> this problem at compile time. Giving the intended semantics
> statically might be quite difficult.

I'm sorry Sergio, but I do not understand you problem here. IIUC,
you are saying that (I'm using let notation here to make things
syntactically sound)
   let x free in (f x ? g x)
does not make sense because you cannot evaluate f x and g x in
parallel for, say
   f 0 = success
   g 1 = success
since given either instantiation of x the other argument fails.
But then this is not a particular property of (?). For instance,
given
   let x free in const (f x) (g x)
you get the same failure when you evaluate both (f x) and (g x).
This shows that you should not naively evaluate arguments that
are not demanded by the program. And note that (?) does not
demand either of its arguments, since they are not used in *every*
possible reduction. (BTW, note that two branches of (?) are equal
to const and (flip const), respectively.)

What you can do, however, is using the fact that each of (?)'s
arguments is used in *one* non-deterministic branch of the
computation. So may perform a parallel reduction of the arguments,
but this *must* be done in an or-parallel manner, i.e., using
independent instances for the yet free and unevaluated variables
of the program. Hence, there is no difference between
   let x free in (f x ? g x)
and
   (let x free in f x) ? (let x free in g x)

Regards
Wolfgang

_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Thu Nov 08 2007 - 12:01:37 CET

This archive was generated by hypermail 2.3.0 : Wed Sep 18 2019 - 07:15:07 CEST