ok@quintus (07/20/88)
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.