Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!usc!cs.utexas.edu!uunet!mcvax!hp4nl!swivax!jan
From: jan@swivax.UUCP (Jan Wielemaker)
Newsgroups: comp.lang.prolog
Subject: Bagof (considerations, implementation)
Message-ID: <1479@swisun.swivax.UUCP>
Date: 10 Jul 89 11:34:45 GMT
Reply-To: jan@swivax.UUCP ()
Organization: SWI, UvA, Amsterdam
Lines: 136

As  I  decided  to  reimplement  the  bag  predicates   for   SWI-Prolog
(findall/3,  bagof/3  and  setof/3) I tried to find the right semantics.
This article does not discuss the bag predicates from a logical point of
view, but from a  programmer/users  point  of  view.   Findall/3  is  no
problem.   A  number of difficulties arise with bagof and setof however.
First of all, what should happen on the following program:

    :- dynamic test/2.

    test(2, b) :-
	    asserta(test(1, a)).

    ?- bagof(A, test(A, B), As).

Both BIM and Quintus aggreed As = [2] and B = b.  Cprolog  1.5  did  the
same, but on backtracking gave this solution for a second time (a bug?).

This suggests all solutions can be recorded in the database in one  pass
and analysed afterwards, leading to the following structure:

    bagof(Gen, Goal, Bag) :-
	<find the free variables in Goal, not bound with the existence
	 operator ^/2>,
	<backtrack over Goal, saving the bindings of the free variables
	 and the binding of Gen in the database>,
        <analyse the result in the database>.

Now the main problem is what variable bindings  of  the  remaining  free
variables  in  Goal are treated equal.  Three alternatives come to mind:
using =/2, ==/2 and =@=/2 (=@=/2 has been proposed by someone (I  forgot
his  name,  could anyone mail the name to me, so I can reference him) to
test *structural equivalence*, which is stronger than  =/2,  but  weaker
than ==/2: a(A,A) =@= a(A,B) fails).

I used the following test database:

    foo(1, a).
    foo(2, b).
    foo(3, b).
    foo(4, _).
    foo(5, _).
    foo(6, c(_)).
    foo(7, c(_)).
    foo(8, d(A,A)).
    foo(9, d(_,_)).

Which resulted in the following answers:

Quintus Prolog Release 2.4 (Sun-3, SunOS 3.4)
Copyright (C) 1988, Quintus Computer Systems, Inc.  All rights reserved.

| ?- bagof(A, foo(A,B), As).

  B = _64,	    As = [4,5] ;
  B = a,	    As = [1] ;
  B = b,	    As = [2,3] ;
  B = c(_316),	    As = [7] ;
  B = c(_338),	    As = [6] ;
  B = d(_270,_271), As = [9] ;
  B = d(_293,_293), As = [8] ;

BIM_Prolog - release Sun compiler 2.4 1-Mar-1989 

Yes 
?- bagof(A, foo(A,B), As).

  _B = a,           _As = [1] ;
  _B = b,           _As = [2,3] ;
  _B = _69,         _As = [4,5] ;
  _B = c(_60),	    _As = [6,7] ;
  _B = d(_49,_49),  _As = [8] ;
  _B = d(_38,_39),  _As = [9] ;

C-Prolog 1.5
Copyright (C), University of Edinburgh

yes
?- bagof(A, foo(A,B), As).

  B = a,	     As = [5,4,1] ;
  B = b,             As = [2,3] ;
  B = c(_467),       As = [7,6] ;
  B = d(_438, _438), As = [9,8] 

To start with the last: Cprolog seems to use =/2, which is clearly wrong
as it combines the two variables with  'a',  which  happens  to  be  the
first.

BIM_Prolog seem to  use  =@=/2  (they  do  not  support  this  predicate
itself).

Quintus does very strange things.  First of all it seems  to  order  the
results  presented  on backtracking to the standard order.  I never knew
bagof/3 was supposed to do  ordering.   Second  (and  more  serious)  it
treats the two variables equal ([4,5]), but not the two variables nested
in c/1 ([6,7]).  What happens here???

Considerations

If we addopt the semantics of  Quintus  on  changing  active  predicates
(e.g.  the  change  will  not be visible for the current invokation) the
implementation schema proposed above is ok.

We cannot use ==/2 because Prolog requires us to store  the  results  of
backtracking  in  the  database.   This  implies  if  the  free variable
template holds variables they will never be merged because:

    ?-  A = B,
	assert(foo(A)),
	assert(foo(B)),
	retract(foo(C)),
	retract(foo(D)),
	C == D.

will fail.

From an implementation point of view I see  no  way  around  this.   The
following however is always true (for any A and B):

    test(A,B) :-
	A =@= B, !,
	assert(test(A)),
	assert(test(B)),
	retract(test(C)),
	retract(test(D)),
	C =@= D.
    test(_, _).

The =@=/2 predicate is the strongest condition that passes this test!

Conclusions

It seems no concensus exists on how to treat variables  in  bagof/setof.
My suggestion is either to standardise on the =@=/2 standard (as BIM) or
give  an  error  message.   I  decided  SWI-Prolog  sticks  to the =@=/2
solution.