Re: encapsulated search (Re: New PAKCS release (Version 1.8.0))

From: Wolfgang Lux <wlux_at_uni-muenster.de>
Date: Mon, 07 May 2007 09:50:35 +0200

Claus Reinke wrote:

> consider these definitions and their PAKCS results:
>
> coin = 0 ? 1
> allSolutions g = findall (\x->x=:=g)
>
> a = allSolutions coin ++ [coin] ++ allSolutions coin
>
> b = let x = coin
> in allSolutions x ++ [x] ++ allSolutions x
>
> -- Goal: a :: [Int]
> -- Result: [0,1,0,0,1] ?
>
> -- Goal: b :: [Int]
> -- Result: [0,1,0,0] ?
>
> 'a' gives the intended result, 'b' suffers from one of the issues
> described
> in the 2004 paper, as part of the argument against strong
> encapsulation.
>
> in contrast, weak encapsulation should at least give consistent
> results,
> but like the second 'allSolutions' call in b, it supposedly does
> not give
> full solution sets.

The (first) result for a and b is [0,0,0] with weak encapsulation.
However
this does not mean that a and b are equivalent under weak
encapsulation as
you will notice when asking for more solutions. In particular, a has
8 solutions
with weak encapsulation whereas b has only 2.

> but it seems we can avoid that issue by wrapping the
> non-determinism at the source, for transport into the capsule, where
> we unwrap it again, to make it part of the encapsulated search:
>
> coinW = wrap (0?1)
>
> c = let x = coinW
> in allSolutions (unwrap x) ++ [unwrap x] ++ allSolutions
> (unwrap x)
>
> wrap g f = f g
> unwrap cg = cg id
>
> -- Goal: c :: [Int]
> -- Result: [0,1,0,0,1] ?
>
> we obtain consistent results under strong encapsulation, in spite of
> sharing, and i would expect the same result under weak encapsulation?

No. With weak encapsulation c is equivalent to either a or b
(depending on
whether function declarations are eta-expanded or not), i.e., it has
either
eight or two solutions and the first of them is [0,0,0].

> am i missing something?

Probably call-time choice. The non-deterministic choice between 0 and 1
is tied to the call (0?1) and not the evaluation of (0?1) (wherever this
happens).

Wolfgang

PS: Rather than guessing the weak encapsulation semantics, you might try
to run your examples with the Münster Curry compiler, whose try
primitive
uses weak encapsulation.



_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Mon May 07 2007 - 11:55:29 CEST

This archive was generated by hypermail 2.3.0 : Mon Nov 18 2019 - 07:15:06 CET