Dear Colleagues!
The interesting discussion about encapsulated search we had at WFLP
in Aachen was reverberating in mind. The main criticism of MCC's
implementation of encapsulated search (rightly) is that it does not
allow encapsulating non-determinism in argument expressions. For
instance,
let x = coin in findall (\y -> y =:= x)
yields two results, viz., [0] and [1], because MCC takes a strict view
on call time choice even with respect to encapsulated search. Thus, the
example is evaluated like
let x = coin in x `seq` findall (\y -> y =:= x)
Yet, it turns out that it is quite straight forward to implement strong
encapsulation in MCC with the addition of just a single function
clone :: a -> a
The semantics of this function is such that it in
y = clone x
y is an identical copy x. Thus, y and x evaluate to exactly them same
results, but sharing (for applications, not for logic variables) is
lost. In particular, evaluating y does not force an evaluation of x.
For instance,
let x = coin; y = clone x in y `seq` x + y
evaluates to 0, 1, and 2. Nevertheless clone does preserve sharing
within its argument, i.e.,
let x = coin; y = clone (x + x) in y
has only solutions 0 and 2.
With the help of this function, one can implement the getSearchTree
function proposed by Bernd, Michael, and Frank.
data SearchTree a = Fail | Val a | Or [SearchTree a]
getSearchTree :: a -> IO (SearchTree a)
getSearchTree x = return (search (\y -> y =:= copy_goal x))
where search x = makeTree (try x)
makeTree [] = Fail
makeTree [g] = Val (unpack g)
makeTree (g1:g2:gs) = Or (map search (g1:g2:gs))
Note that getSearchTree is defined in the IO monad in order to avoid
the problems of strong encapsulation and sharing. This also matches
better the wish list in section 1.4 of the paper (though not obvious
from the examples). For those who were not in Aachen, the paper can
be found here:
http://www.informatik.uni-kiel.de/~mh/publications/papers/WFLP04.html
Thus, I tend to believe that MCC's weak encapsulation approach is
the right one for encapsulated search as it allows implementing
pruning strategies (which seems not possible directly with
getSearchTree),
and strong encapsulation and getSearchTree can be implemented on top
of it with help one auxiliary function (with a somewhat dubious
declarative semantics, though).
Regards
Wolfgang
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Mo Jun 14 2004 - 16:41:46 CEST