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

From: Sergio Antoy <antoy_at_cs.pdx.edu>

Date: Tue, 22 Jan 2013 16:31:47 -0800

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

Date: Tue, 22 Jan 2013 16:31:47 -0800

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:

_______________________________________________

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
*