dave8@mva.cs.liv.ac.uk (07/25/89)
With reference to >> Article 261 of comp.lang.prolog: >> From: jan@swivax.UUCP (Jan Wielemaker) >> Newsgroups: comp.lang.prolog >> Subject: Bagof (considerations, implementation) >> Date: 10 Jul 89 11:34:45 GMT >> Reply-To: jan@swivax.UUCP () >> Organization: SWI, UvA, Amsterdam There does appear to have been, as yet, been any response to this rather interesting news item regarding "bagof", some of which is quoted below, so I shall make a few observations. >> 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?). I'm also not sure what SHOULD happen here, but .. our version of C-Prolog 1.5a behaves as per Quintus and BIM. >> 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>. If you look at the C-Prolog code for findall/bagof/setof (it's in Prolog) this is precisely the structure you find. >> 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??? But what ARE the semantics? --------------------------- What SHOULD be in the bag in the case when B = a ? B = b ? B = c(_A) ? B = d(_A, _A) ? B = d(_A, _B) ? Answer [1,4,5] [2,3,4,5] [4,5,6,7] [4,5,8,9] [4,5,9] respectively, because foo(1, a). foo(2, b). foo(4, _). foo(4, _). foo(4, _). foo(4, _). foo(3, b). foo(5, _). foo(5, _). foo(5, _). foo(5, _). foo(4, _). foo(6, c(_)). foo(8, d(A, A)). foo(9, d(_, _)). foo(5, _). foo(7, c(_)). foo(9, d(_, _)). each satisfy ?- foo(A, a). foo(A, b). foo(A, c(_A)). foo(A, d(_A, _A). foo(A, d(_A, _B). Not forgetting that for B = _A the bag should contain [4,5] because foo(4, _) and foo(5, _) each satisfy foo(A, _A). In the fifth case above, "8" does not appear in the bag [4,5,9] when B = d(_A, _B) because this would immediately constrain B to be d(_A, _A); similarly, in the case when B = _A, none other than "4" and "5" appear in the bag, for the same reason. I would expect Prolog, therefore, to return the following bags (not necessarily in the order given). _B = a, _As = [1,4,5] ; _B = b, _As = [2,3,4,5] ; _B = c(_A) _As = [4,5,6,7] ; _B = d(_A, _A) _As = [4,5,8,9] ; _B = d(_A, _B) _As = [4,5,9] ; _B = _A _As = [4,5] ; Dave Sherratt.