- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Wolfgang Lux <wlux_at_uni-muenster.de>

Date: Mon, 14 Jun 2004 15:21:16 +0200

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

Date: Mon, 14 Jun 2004 15:21:16 +0200

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

*
This archive was generated by hypermail 2.3.0
: Di Feb 07 2023 - 07:15:07 CET
*