Hi Sebastian,
Thanks for your reply. You make very good points. I would
favor using only set functions and leaving everything else
under the hood, the reason being that the semantics of set
functions is simple to explain and understand.
Returning a set (as opposed to a list) is certainly cleaner
and it should be the standard behavior. I also think that
there should be an operation that non-deterministically
returns some element of a non-empty set (and perhaps
concurrently the set without that element) much in the same
way in which there is a function that non-deterministically
returns some element of a non-empty list. This would make a
simple and manifest conversion.
Best,
Sergio
On Tue, 22 Jan 2013, at 09:42, Sebastian Fischer <sebf_at_informatik.uni-kiel.de> wrote:
> Hi Sergio,
>
> in my opinion, the most serious drawback of a construct like "allValues
> exp" for encapsulating choices is that it depends on evaluation order which
> choices are encapsulated. For example,
>
> allValues (0?1)
>
> evaluates to [0] ? [1] if we evaluate the argument of allValues before
> calling allValues, like with strict evaluation. In MCC, findall avoids this
> problem by using weak encapsulation:
>
> findall (p ? q) = findall p ? findall q
>
> regardless of evaluation order because only nondeterminism created in the
> body of the predicates p and q is encapsulated. My proposed variant of
> allValues (let's call it 'results' to avoid confusion) uses the same trick
> to only encapsulate nondeterminism created in the body of a passed
> operation:
>
> results (f ? g) = results f ? results g
>
> regardless of evaluation order, but for example
>
> results (\_ -> 0?1) = [0,1]
>
> Set functions (seemingly) provide another perspective on this problem. But,
> as far as encapsulated choices are concerned, they are equivalent to weak
> encapsulation as in MCC. Either can be expressed using the other:
>
> fSet x = findall (\y -> f x =:= y) -- = results (\_ -> f x)
>
> findall p = unpackSet p
>
> where unpack is defined in the Prelude as follows:
>
> unpack p | p x = x where x free
>
> The results operation can also be defined using set functions:
>
> results f = resultSet f
>
> where result is defined as follows:
>
> result f = f ()
>
> Maybe, results is less awkward if we generalize the type as follows:
>
> results :: (a -> b) -> [b]
>
> Then we can pass free variables instead of unit when expressing the other
> encapsulation functions using results.
>
> To summarize: regarding which choices are encapsulated, findall, results,
> and set functions all implement weak encapsulation independent of
> evaluation order, in contrast to allValues which must not be evaluated
> eagerly to encapsulate anything.
>
>
> On to some other, not so serious, drawbacks.
>
> So far, I avoided a discussion of the result type of encapsulation
> functions. All encapsulation functions returning lists have the problem
> that the order and multiplicity of results depends on evaluation order. For
> example
>
> findall (\x -> x =:= fst (1,2?3))
>
> yields [1] if the second component of the pair is not evaluated but would
> yield [1,1] if it would be evaluated as with eager evaluation. Regarding
> order of results, define
>
> foo x b = if b then (x,1) else (x,2)
>
> Then
>
> findall (y -> y =:= foo (1?2) (True?False))
>
> yields [(1,1),(2,1),(1,2),(2,2)] in a lazy language (which evaluates the
> boolean value first) but may yield [(1,1),(1,2),(2,1),(2,2)] in an eager
> language if arguments are evaluated from left to right.
>
> The SetFunctions module in PAKCS (or KiCS2) solves this problem with an
> abstract type Values that does not allow to observe order and
> multiplicities of results.
>
> Personally, I don't find evaluation order influencing the order and
> multiplicities of results as serious as evaluation order influencing which
> choices are encapsulated. In fact, I prefer lists as result over an
> abstract data type such as Values because of their convenience. For
> example, explaining the restrictions of the Values type (and the specific
> operations necessary to work with it) would have distracted from the points
> I was trying to make in my Crash Course, which is why I used findall and
> not set functions in my examples.
>
> The functions results and findall can be defined in KiCS2 based on set
> functions while allValues probably needs special compiler support. For
> pragmatic reasons I would like to see a (list based) definition of findall
> (and maybe results :: (a -> b) -> [a]) in KiCS2. This would make it
> possible to define Curry programs that use encapsulated search and still
> work in all Curry systems.
>
> Best regards,
> Sebastian
>
>
> On Tue, Jan 22, 2013 at 12:40 AM, Sergio Antoy <antoy_at_cs.pdx.edu> wrote:
>
> > Hi Sebastian,
> >
> > Nice work on the code samples.
> >
> > What is the most serious drawback (and maybe also all the others,
> > since we are this)?
> >
> > Thanks,
> > Sergio
> >
> > On Mon, 21 Jan 2013, at 19:37, Sebastian Fischer <
> > sebf_at_informatik.uni-kiel.de> wrote:
> >
> > > > Nowadays, non-deterministic
> > > > operations are much more elegant so that the typical use of
> > > > findall is in the form
> > > >
> > > > findall (\y -> exp =:= y)
> > > >
> > > > which looks awkward. I'd prefer "allValues exp", although
> > >
> > > we know that it also has its drawbacks.
> > >
> > >
> > > Yes, I would prefer "allValues (\_ -> exp)" which looks a little more
> > > awkward but avoids the most serious drawback, in my opinion. Providing
> > > findall or allValues is just a matter of convenience, because
> > >
> > > allValues f = findall (\x -> f () =:= x)
> > > findall p = allValues (\_ -> let x free in p x &> x)
> > >
> > > These definitions would work in all Curry systems while "allValues exp"
> > > would not work in MCC. Not sure about KiCS2.
> > >
> > > Best regards,
> > > Sebastian
> >
> > > _______________________________________________
> > > curry mailing list
> > > curry_at_lists.RWTH-Aachen.DE
> > > http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
> >
> >
> _______________________________________________
> curry mailing list
> curry_at_lists.RWTH-Aachen.DE
> http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Do Jan 24 2013 - 17:13:43 CET