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 Fr Jan 11 2002 - 14:28:48 CET