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
Received on Di Jan 22 2013 - 17:19:01 CET