Problems with bagof/3

Appeared in Volume 8/4, November 1995

Keywords: bagof.

ludemann@netcom.com
Peter Ludemann
10th July 1995

In response to Passani Luca writing:

I thought the semantics of bagof/3 was clear to me by now, but:

make_list_of_products(List) :-
  bagof(Product, Name^(product(Product, Name, _)), List).

doesn't work.

Richard A. O'Keefe wrote:

Here's a tip: never put an anonymous variable in the generator argument of bagof/3 or setof/3.

I've made this same mistake enough times to have developed my own techniques (which might help you):

Avoid using existential quantifiers with bagof/setof.
Never put compound goals in bagof/setof.
Use setof/3 unless there's a good reason not to.

So, using rule 1, I would write your query as:

make_list_of_products(List) :-
  bagof(Product, is_product(Product), List).

is_product(Product) :- product(Product, _, _).

This technique works nicely, runs fast, and spares my supplies of Aspirin.

The reason for rule 2 is that many Prologs create awful code for something like:

fs_and_gs(L) :- bagof(X, (f(X),g(X)), L).

much better code is generated if you do:

fs_and_gs(L) :- bagof(X, f_and_g(X), L).
f_and_g(X) :- f(X), g(X).

Besides, the compound goals can be hard to read, with the extra parentheses.

The bad implementations evaluate (f(X),g(X)) as call(f(X),g(X)), invoking the interpreter, typically 10-times or more slower than using compiled code.

The reason for rule 3 is that setof/3 eliminates duplicates; the resulting list doesn't depend on the ordering of the clauses used to compute it. This forces me to be a bit more "logical" in my programming.

ok@goanna.cs.rmit.edu.au
Richard A. O'Keefe
17th July 1995

Peter Ludemann writes:
1. Avoid using existential quantifiers with bagof/setof.

You can get the same effect by rewriting your code to call a predicate that simply hasn't got those arguments. This means that the variables that would have been existentially quantified don't appear at all.

I actually did some benchmarking with a couple of implementations; I wanted to see if effectively compiling:

setof(Template, Generator, Set)

as:

<preprocess>
(  mark,
   Generator,
   save Template,
   fail
;  recover Results,
   parse Results getting Set and bindings for free variables
)

so that the Generator could be compiled in-line would improve things. The answer for all the tests I could get my hands on was no. If the interpreter is any good, the overhead of call/1 here will be swamped by the cost of saving the results and picking them up again (two copies are required, though if you are really cunning you can get the cost down to the equivalent of one copy) and especially the cost of sorting them.

However, I vehemently agree that having a simple goal makes the code a lot more readable.

Peter Ludemann writes:
The reason for rule 3 is that setof/3 eliminates duplicates; the resulting list doesn't depend on the ordering of the clauses used to compute it. This forces me to be a bit more "logical" in my programming.

I would also point out that the resulting set is represented in a way which makes it possible to do set operations cheaply. Don't think that you will save on sorting by using bagof/3 instead of setof/3: if there are any free variables bagof/3 still has to regroup the results somehow.

These rules are good advice.

fjh@munta.cs.mu.oz.au
Fergus Henderson
24th July 1995

In the current Mercury implementation, solutions/2 (which is our answer to setof/3, NU-Prolog's solutions/3, etc.) has a "zero-copy" implementation.

In this case, I expect that what you gain on the swings you lose on the round-abouts. With the current conservative garbage collector, we don't get cheap memory reclamation on backtracking. With a different garbage collector the trade-offs would change, and we might well adopt a different implementation of solutions/2.

etg10@cl.cam.ac.uk
Edmund Grimley-Evans
19th July 1995

Richard A. O'Keefe writes:
I would also point out that the resulting set is represented in a way which makes it possible to do set operations cheaply. Don't think that you will save on sorting by using bagof/3 instead of setof/3: if there are any free variables bagof/3 still has to regroup the results somehow.

Why then does the SICStus manual say (in the description of bagof/3) "This is exactly the same as setof/3 except that the list (or alternative lists) returned will not be ordered, and may contain duplicates. The effect of this relaxation is to save a call to sort/2, which is invoked by setof/3 to return an ordered list."?

By the way, I found myself defining:

setof1(Template, Pred, SetList) :-
  findall(Template, Pred, List),
  sort(List, SetList).

because I found it easier to have a goal that always succeeds exactly once.

Peter Ludemann
ludemann@netcom.com
19th July 1995

Since bagof/setof should fail if there's no solution (Richard O'Keefe has explained why; no need for me to repeat that), I usually program setof1/3 by:

setof1(Template, Pred, SetList) :-
 (   setof(Template, Pred, SetList)
 -> true
 ;   SetList = []
 ).

An exercise for the reader: what is the difference (if any) between

findall(Template, Pred, List) and bagof(Template, Pred^Pred, List)?

jensk@bbn.hp.com
Jens Kilian
20th July 1995

Edmund Grimley-Evans wrote:

The 'public domain bagof/setof' from the Edinburgh library sorts the solutions once to group them according to the instantiations of the free variables. setof/3 then sorts them another time.

As far as I know, the ISO Prolog standard defines bagof/setof in a way which eliminates the (first) sorting step, but which has quadratic complexity for grouping the solutions (if you write bagof/setof in Prolog).