Hi Sergio,
I agree that using sets is the more principled approach.
There seems to be a tension that has not been mentioned yet in the
discussion. Lists support the implementation of other evaluation-order
dependent constructs such as committed choice. I could not define the
function `once` in Evaluator.lcurry with the "pure" interface on sets that
you describe (and is provided by the Values type in the SetFunctions
module). Values can be turned into a list by sorting them but it seems
counter productive to sort all values in order to commit to one and sorting
does not terminate for infinite lists.
Maybe we should aim for a pure approach (like set functions) on one hand
and a more powerful approach that allows more control (like commited choice
or heuristics such as findbest based on try) on the other.
Or maybe committed choice is all we need to add? Is it possible to make try
evaluation-order independent by using sets instead of lists and then use it
to implement an evaluation order independent variant of findbest? Maybe
not, because findbest itself performs commited choice if there is more than
one best solution. On the other hand, findbest could instead yield an
arbitrary best solution (i.e. all of them) nondeterministically and
programmers can then use committed choice to commit to one.
Best regards,
Sebastian
On Wed, Jan 23, 2013 at 1:31 AM, Sergio Antoy <antoy_at_cs.pdx.edu> wrote:
> 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:45 CET