Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!ames!pasteur!ucbvax!decwrl!labrea!sri-unix!quintus!ok
From: ok@quintus.UUCP (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: The Touchstone again
Message-ID: <879@cresswell.quintus.UUCP>
Date: 15 Apr 88 08:50:50 GMT
Organization: Quintus Computer Systems, Mountain View, CA
Lines: 41
Keywords: another strange findall

Just recently I came across yet another version of findall and I thought
I'd share it with you.  I've changed the names around a bit to disguise
the original, but I haven't changed the way it works.

:- dynamic
	stack_of_difference_lists/2.

findall(Term, Goal, _) :-
	asserta(stack_of_difference_lists(Tail,Tail)),
	call(Goal),
	add_solution(Term),
	fail.
findall(_, _, List) :-
	stack_of_difference_lists(List, []),
	retract(stack_of_difference_lists(_,_)),
	!.

add_solution(Term) :-
	stack_of_difference_lists(List, [Term|Tail]),
	retract(stack_of_difference_lists(_,_)),
	asserta(stack_of_difference_lists(List,Tail)),
	!.

Do I need to point out the bug?  One symptom is that the query

| ?- findall(X-Y, (
	member(X, [[1],[2,3]]),
	findall(L, member(L, X), [Y])
     ), Z).

should return the solution Z = [[1]-1], but instead it yields the
wrong answer Z = [[1]-1,[2,3]- ([1]-1)].

Mind you, it was clever of the author to use a difference list representation
in the data base, it must reduce the quadratic cost of this code by several
percent.  The Clocksin & Mellish method, with a separate assertion for each
solution found, is of course linear, not quadratic.  Delicious.

You'll recall that I call the way findall/3 or whatever is coded "the
Touchstone" to indicate that it is useful as a way of testing whether
you've got gold or pyrites.  Did it prove reliable as an indicator of
the quality of the rest of the code?  Too right!