# Re: Curry Crash Course

From: Sergio Antoy <antoy_at_cs.pdx.edu>
Date: Tue, 22 Jan 2013 16:31:47 -0800

Hi Sebastian,

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

This archive was generated by hypermail 2.3.0 : Do Jun 20 2024 - 07:15:12 CEST