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

From: Michael Hanus <mh_at_informatik.uni-kiel.de>
Date: Fri, 11 Jan 2002 14:19:17 +0100 (MET)

Dear Wolfgang,

thank you for raising this interesting issue on the
encapsulation of search in Curry. I discussed it with Frank
and here are our conclusions and a proposal from this discussion.

The motivation of encapsulated search is to provide a possibility
to encapsulate potential non-deterministic computations in
a deterministic function. Clearly, this is a meta-construct
which cannot be described in the base language. Thus, there is
no clearly preferred intended semantics for such a construct
but we have several options.

The option which we had in mind with our initial proposal
is based on the idea that an encapsulated computation should
only compute results out of some local computations but should
not influence the environment, e.g., values of logical variables.
In the light of this motivation, we have three options for
processing your example

  coin = 0
  coin = 1

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

1. We do not evaluate y (=coin) inside the encapsulated search
   so that the search suspends.

2. We initiate the evaluation of y (=coin) inside the encapsulated
   search since its value is demanded. However, the evaluation is
   done outside the encapsulated search so that we get two results,
   namely [0] and [1].

3. The evaluation of y (=coin) is done inside the encapsulated
   search but does not influence the global binding of y, i.e.,
   the computation is not shared.

Option 1 has the disadvantage that we cannot really perform
encapsulated search but suspend in most cases.

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.
This means that most search operators are no longer applicable.

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

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).
This make also sense if the meaning of findall is a true local
computation. You might consider this as a contradiction
to the sharing of y, but encapsulated search is anywyay
a meta-construct where you have to give up some properties
of purely functional logic programming. On the positive side,
you can really encapsulate arbitrary non-deterministic
computations which is, in my opinion, the most important
aspect of the search operators.

Of course, this must be clarified in the Curry report and
I am open to further comments.

Best regards,

Michael

_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Fri Jan 11 2002 - 14:28:48 CET

This archive was generated by hypermail 2.3.0 : Mon Nov 18 2019 - 07:15:05 CET