Hi Wolfgang,
You raise some interesting and quite difficult questions and I am
afraid I have only some very partial answers.
> The encapsulated search was introduced into Curry in order to encapsulate
> non-deterministic computations and allow to use different search strategies.
> However, in the presence of sharing not all non-determinism can be
> encapsulated. Consider the following simple program:
>
> coin = 0
> coin = 1
>
> main = findall (\x -> x=:=y) where y = coin
>
> where findall computes and unpacks all solutions of a search
> goal with a depth first strategy. In a system based on pure term
> rewriting, evaluating the goal main would yield the list [0,1].
How would you define findall with "pure term rewriting"?
> In Curry we must not evaluate the non-local shared application for y inside
> the encapsulated search but must evaluate it in the global search space. This
> is similar to a non-local variable which must not be bound inside an
> encapsulated search. Thus, the non-determinism in the function coin
> ``escapes'' from the encapsulated search and we get two solutions for the
> goal main, namely [0] and [1].
This is what you should get. Intuitively, if you evaluate "coin"
in a program, you should get either 0 or 1, but not both.
Thus findall should give you either [0] or [1].
> A slight variation of the main function shows better why we must not evaluate
> non-local applications in an encapsulated search:
>
> main' = filter (/= y) (findall (\x -> x=:=y)) where y = coin
>
> The only sensible solution I can think of is two times the empty list.
I would prefer once (one time) only. This come from
main' = filter (/= y) (findall (\x -> x=:=y)) where y = 0
and likewise for 1.
> Maybe this was already obvious to you, but the report is totally ignorant
> about this. IMHO it should at least include a comment about this (writing
> down a semantics seems quite tricky and is impossible in the framework
> used by appendix D as there is no explicit notion of sharing).
>
> This problem can also creep in if you are used to higher-order programming.
> For instance the following program will not compute a list of all solutions
> for the function coin but -- like the initial example -- compute both
> solutions non-deterministically (except if you expect the compiler to
> perform some global sharing analysis and detect that the first argument of
> the function same is never going to be shared).
>
> coin = 0
> coin = 1
>
> main = findall (same coin)
Here I lost you. How (or where) do you define "same"?
I think that some difficulty would be eliminated by considering
two findalls, the usual one and another for non-deterministic
computations, say nd-findall. Thus
findall (\x -> x=:=y) where y = coin
evaluates, non-deterministically, to either [0] or [1], whereas
nd-findall (\x -> x=:=y) where y = coin
evaluates, deterministically, to [0,1].
Sergio
--------------------------------
Sergio Antoy
Dept. of Computer Science
Portland State University
P.O.Box 751
Portland, OR 97207
voice +1 (503) 725-4036
fax +1 (503) 725-3211
internet antoy_at_cs.pdx.edu
WWW
http://www.cs.pdx.edu/~antoy
--------------------------------
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Mi Jan 09 2002 - 08:55:08 CET