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

From: Sergio Antoy <antoy_at_cs.pdx.edu>
Date: Tue, 08 Jan 2002 20:36:20 -0800

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

This archive was generated by hypermail 2.3.0 : Do Dez 12 2019 - 07:15:06 CET