Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uunet!mcsun!unido!fauern!tumuc!lan!grosse
From: grosse@lan.informatik.tu-muenchen.dbp.de (Malte Grosse)
Newsgroups: comp.lang.prolog
Subject: Re: bagof & setof (& findall)
Summary: call or call_as_subgoal, findall broken?
Message-ID: <2273@infovax.lan.informatik.tu-muenchen.dbp.de>
Date: 30 Nov 89 09:47:31 GMT
References: <2783@munnari.oz.au> <2177@infovax.lna....>
Reply-To: grosse@lan.informatik.tu-muenchen.dbp.de (Malte Grosse)
Organization: Inst. fuer Informatik, TU Muenchen, W. Germany
Lines: 188


In article <2783@munnari.oz.au> Richard O'Keefe writes:

>
>Sorry, I seem to have missed your posting.  There is a public-domain
>implementation of setof/3 and bagof/3 adapted from the DEC-10 Prolog
>system; it includes a predicate free_variables/4.  See below.
>
It was not my posting, it was from Mazda
	mazda%shako.sk.tsukuba.ac.jp@cunyvm.cuny.edu

>> 	- is
>> 		    bagof(X, (Y^fact1(X,Y,Z),Z^fact2(X,Z)), L)
>> 	  [equivalent] to
>> 		    bagof(X, Y^Z^(fact1(X,Y,Z),fact2(X,Z)), L)
>> 	  (I assume it as well)
>
>Neither in the public-domain version, nor in the "quick and dirty" versions
>mentioned above, nor in logic would this be true.  If we took logic seriously,
>the first would be equivalent to
>		bagof(X, (Y1^fact1(X,Y,Z), Z1^fact2(X,Z)), L)

assuming you mean:
		bagof(X, (Y1^fact1(X,Y1,Z),Z1^fact2(X,Z1)),L)

but this cuts off the coreference of 'Z' to fact1. Is this alright?
It is the logical way ok, but this is not the way PROLOG works.

>and the second would be equivalent to
>		bagof(X, Y1^Z1(fact1(X,Y1,Z1), fact2(X,Z1)), L)
>
>Note that the answer is different for the first question because pushing
>the quantifiers Y, Z further out does not result in bogus capture of free
>variables.  Here it does.
>

>> 	- is
>> 		    bagof(X,Y^(fact(X,Y),!),L)
>> 	  the same as
>> 		    bagof(X,(fact(X,Y),!),L)
>
>no way.  The second one will return a binding for Y.  The first one
>won't.  Why should a cut change anything?
>
>> 	  the same as
>> 		    fact(X,_),L=[X],!
>
>Again, no.  The rule is that setof/3 and bagof/3 find bindings for the
>FREE variables, and a variable is only free if it appears NEITHER within
>the scope of an existential quantifier (the point you seem to be missing
>in an earlier question is the "within the scope" bit) NOR within the
>template (the first argument).  So provided X does not occur in L already,
>bagof(X, ..., L) will not instantiate X.  But the query
>		fact(X, _), !, L = [X]
>*will* instantiate X.  
>


You are right, I have not thought about the instantiation of X and Y.
I was looking at the result of the list L.
		bagof(X,Y^(fact(X,Y),!),L).
is the same as
		findall(X,(fact(X,Y),!),L).
But this will fail according to the !,fail structure, 
(depending on the implementation)
which is coming into findall.
--> see my comments on this

To my opinion this findall should give for 'L' the same as 
fact(_1,_),L=[_1],!,
which I tried to express.

>> 	- [what] does
>> 		    bagof(X, (Y^fact1(X,Y,Z);Z^fact2(X,Z)), L)
>> 	  [transform] to?
>> 	  to
>> 		    bagof(X, Y^Z^(fact1(X,Y,Z);fact2(X,Z)), L)
>>  	  or to
>> 		    bagof(X, Y^Znew^(fact1(X,Y,Z);fact2(X,Znew)), L)
>
>There are again at least three answers:
>
>(a) the logical answer.
>    Think of W^(...W...) as (exists W)(...W...).
>    (Y^fact1(X, Y, Z) ; Z^fact2(X, Z))
>    thus stands for the logical formula
>    (exists Y)fact1(X, Y, Z) or (exists Z)fact2(X, Z)
>    which, by renaming bound variables, is equivalent to
>    (exists %1)fact1(X, %1, Z) or (exists %2)fact2(X, %2)
>
>    Neither of your suggested translations matches the logical reading.

I think my third translation is equivalent. But anyway I do agree.


>...
>where
>	findall(Template, Goal, List) :-
>		(   push special marker on stack,
>		    call(Goal),
>		    push Template instance on stack,
>		    fail
>		;   collect Template instances from stack as List
>		).
>
>findall/3 is completely blind to the structure of the Goal.  bagof/3 cares
>only to the extent that it influences the scan for existential quantifiers.
>The POINT of findall/3 and bagof/3 is to find ALL the solutions, not to
>cut off at some bizarre place.
>

Exactly! But with this realisation it can cause serious problems! 
I have the opinion that 'call' should be 'call_as_subgoal'
which is: 

call_as_subgoal(X):-call(X).

Because this remains stable in case there is a cut in the goal;
your version - which is maybe the version of us all (?!?)-
will finally fail findall and remains the stack changed!

*** I have just found in a CProlog manual under call(X):
"... the goal call(X) is executed exactly as if that term appeared textually
in place of the call(X), except that any CUT occuring in X will remove
only those choice points in X. ..."
***

It depends now how your 'call' is implemented. Our findall is broken,
maybe because of another implementation of 'call'. In Clocksin&Mellish
it is just a replacement.

This was the reason of my second question, although I did not 
take into consideration that the FREEVARIABLES should stay
uninstantiated.

********************************* session follows *********************

?- listing.

yes
?- asserta(we(7)).

yes
?- listing.
we(7).


yes
?- findall(Q,we(Q),L).

Q	= _636
L	= [7];

no
?- listing.
we(7).


yes
?- findall(Q,(we(Q),!),L).

no
?- listing.
$found(7,_716).
$found(_712,$).

we(7).


yes

************************************* end of session *****************

I really like to hear from others how their bagof or findall is behaving
in these cases. 

Malte

please reply to:
	grosse%lan.informatik.tu-muenchen.dbp.de@relay.cs.net
---------------------------------------------------------------------------

TTTTTTT  U      U  M       M       	  TECHNICAL UNIVERSITY OF MUNICH
   T	 U      U  MM     MM	   	  INSTITUT FUER INFORMATIK
   T     U      U  M M   M M 	   	  ORLEANSSTRASSE 34
   T     U      U  M  M M  M	   D-8000 MUENCHEN 80
   T     U      U  M   M   M 
   T      UUUUUU   M       M 	   	  WEST-GERMANY