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

From: Claus Reinke <claus.reinke_at_talk21.com>
Date: Sun, 06 May 2007 00:35:14 +0100

browsing through the Curry report and PAKCS docs, it seems that the
IO-bound variants of encapsulated search have not replaced the Curry
ones, but have become part of a PAKCS library (AllSolutions)?

that means we can test my suggestions, using findAll.

> encap :: {ND}a -> ND a -- encapsulate an implicit search
> uncap :: ND a -> {ND} a -- non-deterministically extract results

i guess i'd still prefer separate sets of operators for non-local and
encapsulated non-determinism, but as long as we don't need to interpret
the non-determinism operators differently in their encapsulated form,
even a simple Church encoded unary constructor should do the trick
of avoiding early propagation of non-determinism by wrapping it in a
non-strict context (the wrap i mentioned in the other thread).

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. 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?

am i missing something?

claus

ps inlining the definition of 'coinW' in 'c' changes the result, which i
    find very counter-intuitive. is that a combination of function vs
    variable binding + PAKCS early evaluation of the parameter in
    the partial application of 'wrap'?

    d = let x = wrap (0?1)
        in allSolutions (unwrap x) ++ [unwrap x] ++ allSolutions (unwrap x)

    -- Goal: d :: [Int]
    -- Result: [0,1,0,0] ?


_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on So Mai 06 2007 - 17:56:00 CEST

This archive was generated by hypermail 2.3.0 : Do Feb 01 2024 - 07:15:07 CET