OKeefe.R.A.@EDXA@sri-unix.UUCP (10/07/83)
From: Richard HPS (on ERCC DEC-10) <OKeefe.R.A.@EDXA>
I have just received the manual for yet another Prolog interpreter.
It is one of the closest to DEC-10 Prolog, and its differences are
well-motivated. So why am I furious?
Because the manual lists a predicate bagof/3, and almost the only
thing which is clear from the 2-line description is that it is no
such thing. It is findall. (Indeed the description calls it
findall.) I do not claim that the author of the program is
deliberately committing fraud. I cannot know whether it was he
himself who wrote the manual, or whether another "improved" it
before it reached me.
findall is a special case of bagof. bagof and setof are described
in the paper "Higher-Order Extensions to Prolog, are they Needed?"
by David Warren and the current DEC-10 Prolog manual by David Bowen,
both available from DAI Edinburgh (see almost any issue of SigArt
to find out how to get them). The big question is "what happens to
unbound variables in the generator".
The classic example is
likes(bill, baroque).
likes(bill, jazz).
likes(fred, jazz).
likes(fred, rock).
?- findall(X, likes(X,Y), Likers).
=> X = _0
Y = _1
Likers = [bill,bill,fred,fred]
?- bagof(X, likes(X,Y), Likers).
=> X = _0
Y = baroque
Likers = [bill] ;
X = _0
Y = jazz
Likers = [bill,fred] ;
X = _0
Y = rock
Likers = [fred]
If you want the findall interpretation, you can use the
"existential quantifier" ^ and write
?- bagof(X, Y^likes(X,Y), Likers).
and get the same answer as findall (in fact if all the
otherwise unbound variables are existentially quantified
bagof performs exactly the same steps as findall).
bagof can be used to simulate findall, but findall cannot be
directly used to simulate bagof. You have to collect all
the variables into your list, group together the solutions
which imatch on the universally quantified variables (in
this case Y) -- this is why DEC-10 Prolog and C-Polog have
the predicate keysort/2 -- and backtrack through the matched
segments. This can be, and is, done in Prolog. You have to
be a bit careful with some of the boundary cases, and with
strange things turning up in the generator, but anyone who
is capable of writing say a subsumption checker (not using
numbervars) is capable of writing a correct version of bagof
and setof. The main difference between bagof and setof is
which sorting routine they use. There are fewer easier
predicates to write than a merge sort, and merge sort seems
to be the most efficient possible sorting routine in Prolog.
setof is particularly important for data-base work. The main
reason I am sure that the bagof described in the manual for
this otherwise excellent Prolog is not bagof is that once you
have written the REAL bagof (admittedly not a trivial 10-line
thing like findall) you're 99% of the way to setof, and the
manual doesn't mention it.
I'm fairly confident that if I had bought a copy of the interpreter,
stating in my order that I wanted it because of bagof, that I
would be able to prove fraud in court. I am not in fact accusing
the author of this system of having any fraudulent intent, nor am
I alleging that he is incapable of implementing the real bagof
(and there's the tragedy, why didn't he), nor am I alleging that
the interpreter is not value for money. I'm just saying, in
rather strong language:
- calling "findall" "bagof" is seriously misleading
- it is unhelpful to people who have read Clocksin &
Mellish [as they'll look for "findall" and not know
about "bagof"]
- it is positively damaging to people who want to use
the real thing [as they may not at first realise why
their correct and accepted program doesn't work, and
will then be unable to replace bagof with the correct
definition without hacking the interpreter]
- it is unnecessary
So please, Prolog implementors, DON'T DO IT !