🚀 go-pugleaf

Someone recently mentioned that he was writing a breadth-first interpreter
in Prolog, and Lee Naish suggested that iterative deepening might be a
better idea.  I'd like to endorse that.  I thought it would be interesting
to compare iterative deepening and breadth-first on a toy example.  For
the "Advanced Prolog Course" we gave recently at Quintus I wrote a little
package (it's trivial, really it is) that takes rules to be processed by
iterative deepening and turns them into Prolog.  So the example is
	tree(X+Y) <- tree(X), tree(Y).
	tree(a) <- true.
	tree(b) <- true.
which expand_term/2 turns into
	tree(A+B, N0, N) :- N0 > 0, N1 is N0-1,
		tree(A, N1, N2),
		tree(B, N2, N).
	tree(a, N0, N) :- N0 > 0, N is N0-1.
	tree(b, N0, N) :- N0 > 0, N is N0-1.
which is compiled as usual.  There is an "interface" routine
id_call/1 which adds the appropriate arguments and generates
an increasing sequence of depth bounds.

For the breadth-first version, I used the obvious interpreter:

%   solve(Goal)
%   enumerates solutions for Goal in the usual fashion, but finds them
%   by breadth-first interpretation of the clauses in rule/3.

solve(Goal) :-
	prove([[Goal|[](Goal)]|Tail], Tail, Goal).

prove([Conj|Conjs], Tail, Orig) :-
	nonvar(Conj),			% don't run off the end!
	prove(Conj, Conjs, Tail, Orig).

prove([](Goal), _, _, Goal).		% report answer
prove([](_), Conjs, Tail, Orig) :-	% look for another answer
	prove(Conjs, Tail, Orig).
prove([Goal|Goals], Conjs, Tail, Orig) :-
	findall(NewConj, rule(Goal,NewConj,Goals), NewConjs),
	append(NewConjs, NewTail, Tail),
	prove(Conjs, NewTail, Orig).

with the example clauses written as

rule(tree(X+Y), [tree(X),tree(Y)|Gs], Gs).
rule(tree(a),   Gs, Gs).
rule(tree(b),   Gs, Gs).

On quite small examples, solve(tree(X)) ran about 75 times slower than 
id_call(tree(X)), and this figure worsened fairly rapidly for larger trees.
findall/3 is a library predicate in the version of Quintus Prolog I was
using, so this figure could be improved somewhat, but the fundamental
problem remains:  breadth first search has to copy (as in findall/3) the
entire conjunction NewConj in order to rename variables apart, and the
harder the problem, the harder each step becomes.