Re: Encapsulated search does not encapsulate (all) non-determinism

From: Wolfgang Lux <lux_at_wi.uni-muenster.de>
Date: Fri, 11 Jan 2002 17:32:05 +0100

Hello Michael,

> As a consequence, option 3 seems the only reasonable possibility
> if we want to keep the original motivation for encapsulated search.
> With option 3, the informal meaning of (findall \x->c) is:
>
> "Make a local evaluation of c which does not influence the global
> environment and return all bindings for x w.r.t. this evaluation."
>
> Therefore, the local evaluation of c is NOT shared with its
> environment. You can also understand this by textually copying
> the current binding of c into the findall and evaluate this copy
> (note that the textual copy still refers to the same logical variables
> if these are present in c).

this was also my first idea (and also my first implementation). But as the
-- a little bit contrived -- example from my last mail to Sergio shows, the
result of the computation would then depend on the order of evaluation.

> At least, this avoids the problems of the first two options.
> You gave another example:
>
> > main' = filter (/= y) (findall (\x -> x=:=y)) where y = coin
>
> and wrote:
>
> > The only sensible solution I can think of is two times the empty list.
>
> In our proposal above, the solutions are [1] and [0] (this
> non-determinism came from the evaluation of the first occurrence of y).

But only as long as y is not evaluated by some other computation before the
encapsulated search is invoked. As this is not the case for the example above
and the example from my to Sergio was a little bit contrived, here is a
better example:

  main'' = y == head (findall (\x -> x=:=y)) where y = coin

Under the semantics of option 3 the result of this goal will be either
True for both y=0 and y=1 (in the global space) or True for y=0 and False for
y=1 depending on which argument of the equality is evaluated first. Even if
we force the evaluation order to strict from left to right (the report
doesn't IIRC) it would be strange to have main'' and

  main''' = head (findall (\x -> x=:=y)) == y where y = coin

compute different results. Therefore I don't think that option 3 is
reasonable.

Wolfgang


--
Wolfgang Lux				  Phone: +49-251-83-38263
Institut fuer Wirtschaftinformatik	    FAX: +49-251-83-38259
Universitaet Muenster		      Email: wlux_at_uni-muenster.de
Received on Fri Jan 11 2002 - 18:15:23 CET

This archive was generated by hypermail 2.3.0 : Thu Sep 19 2019 - 07:15:05 CEST