- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

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

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.

How would you define findall with "pure term rewriting"?

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

I would prefer once (one time) only. This come from

main' = filter (/= y) (findall (\x -> x=:=y)) where y = 0

and likewise for 1.

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
: Mi Aug 05 2020 - 07:15:03 CEST
*