jan@swivax.UUCP (Jan Wielemaker) (07/10/89)
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.