tarau@ouareau.iro.umontreal.ca (Paul Tarau) (08/12/88)
When trying to find pure Prolog versions of specific 'all_solutions' predicates like 'all_permutations' I faced the following dilemma: For example, after all_solutions(X,member(X,Xs1),Xs2), when Xs1 may contain free variables, must Xs1 and Xs2 be the 'same' object, or Xs2 must be a fresh copy of Xs1? Then I looked at Quintus's 'bagof' and the library predicate 'findall': test1:- Xs1=[A,B,A], findall(X,member(X,Xs1),Xs2), Xs1==Xs2. test2:- Xs1=[A,B,A], bagof(X,member(X,Xs1),Xs2), Xs1==Xs2. As 'test1' fails and 'test2' succeeds, it seems that copying may be just a consequence of findall's 'database-hack' implementation and not a 'feature'. Have someone 'logical' reasons for one of these alternatives? Paul Tarau
ok@quintus.uucp (Richard A. O'Keefe) (08/14/88)
In article <628@mannix.iros1.UUCP> tarau@iros1.UUCP (Paul Tarau) writes: >When trying to find pure Prolog versions of specific 'all_solutions' >predicates like 'all_permutations' I faced the following dilemma: >For example, after > all_solutions(X, member(X,Xs1), Xs2), >when Xs1 may contain free variables, must Xs1 and Xs2 be the 'same' >object, or Xs2 must be a fresh copy of Xs1? >Then I looked at Quintus's 'bagof' and the library predicate 'findall': > >test1:- % THIS FAILS > Xs1 = [A,B,A], > findall(X, member(X,Xs1), Xs2), > Xs1 == Xs2. > >test2:- % THIS SUCCEEDS > Xs1 = [A,B,A], > bagof(X, member(X,Xs1), Xs2), > Xs1 == Xs2. >It seems that copying may be just a consequence of findall's >'database-hack' implementation and not a 'feature'. Unfortunately for this theory, I'm obliged to point out that setof/3 and bagof/3 are built on top of findall/3 (well, this is 99% true) and so employ exactly the same data-base hack (or exactly the same alternative mechanism, whatever that might be). Public-domain source code for findall/3, bagof/3, and setof/3 was sent to the Prolog Digest several years ago, and if you can get your hands on that you will find that after having created new copies of everything, bagof/3 takes the trouble to put the original variables back. (Actually, the public domain version didn't get this quite right, the bug is fixed in Quintus Prolog.) There isn't any "logical" reason for this, because (a) the only member of the {findall,bagof,setof}/3 family which has any pretensions to "logical" status is setof/3, and (b) setof/3 only really has a logical reading when all the solutions it returns are ground. (Consider the fact that setof(X, member(X, [_,_]), [A,B]) will bind A, B to two variables satisfying A @< B, but then you can do A=2, B=1 and presto! the result is found to have been in the wrong order.) The behaviour of findall/3 is the natural outcome of its method of definition, and it can actually be useful. For example, some Prolog systems (including Quintus Prolog) have a copy_term/2 predicate which returns a fresh copy of a term with new variables. Suppose you needed two new copies of a term X and didn't have such a built-in predicate. You could do findall(X, (true;true), [Copy1,Copy2]) and the chances are that this would be more efficient than anything you could have written yourself. (Yes, I know this is a hack. I did say that only setof/3 has any pretensions to "logical" status.) bagof/3 in early versions of DEC-10 Prolog acted more like findall/3. It was changed as a result of practical experience, the present version being found more "intuitive". findall/3 is by no means obsolete, but it has to be handled with care. It is better to use setof/3 (when it is appropriate). Read Lee Naish's writings about all-solutions predicates; great stuff.