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

From: Wolfgang Lux <lux_at_wi.uni-muenster.de>
Date: Mon, 14 Jan 2002 13:32:49 +0100

Hello Michael,

following up my previous mail, I should also note that I don't think option
2 is that problematic as you say. However, one has to be careful about the
definition of search strategies.

> Option 2 has the disadvantage that we cannot really encapsulate
> non-deterministic computations if the goals are defined outside
> and passed by pattern variables into a search goal. For instance,
> consider the following definition of "negation as failure":
>
> naf c = (findall \_->c) =:= []
>
> Since the constraint c is passed into the findall via the
> binding of the non-local variable c, its evaluation will always
> cause a global non-deterministic splitting of the computation space.

It is true, that *this* definition will not work under option 2. But then I
think it is bold to assume that negation-as-failure could be implemented in
that way! What really can be done with the encapsulated search in Curry is to
ask whether there exists no solution for a predicate p, i.e. \not\exists x.p(x).
But this means, p has to have an argument. Therefore, the only way
negation-as-failure can be implemented in Curry is by defining a function
like:

  noSolution g = findall g =:= []

And if you want to see whether g is not satisfied for some value x,
you can use the following function:

  notSatisfiedFor g x = findall (\y -> x=:=y & g y) =:= []

> This means that most search operators are no longer applicable.

I'm not convinced. Do you have any other examples? The only problem I see
at the moment is to implement committed choice (at least in the way it is
specified in the appendix of the Curry report).

Regards
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 Tue Jan 15 2002 - 06:46:15 CET

This archive was generated by hypermail 2.3.0 : Fri Sep 20 2019 - 07:15:05 CEST