lee@mulga.oz (Lee Naish) (07/11/88)
In article <1630@kalliope.rice.edu> phil@rice.edu (William LeFebvre) writes: >I am trying to write a meta-evaluator for a >specific subset of Prolog programs that does breadth first evaluation I don't know what your application is, but many people use breadth first evaluation when they just need any fair search strategy (I know I have). As a general rule, a bounded depth first search with iterative deepening is *much* better than breadth first. With breadth first, you tend to have to copy large quantities of data. Typically, for each call, you must copy all matching clauses and for each clause (even those which dont match in a simple implementation), you must copy the current instance of the variables in the top level goal and the entire current goal (not just a single call). This copying takes lots of time and memory. Depth first evaluation does not need to copy goals or variables since it only works on one branch at a time. It also takes more advantage of Prolog operations such as backtracking. There are two potential problems with it. Firstly, the same solution may be returned several times (one for each iteration). Secondly, it will never fail (it keeps trying greater depths indefinitely). The following code avoids the first problem and can be modified to solve the second problem (by using a side effect). Lee Naish P.S. I wont claim this does anything sensible with negation or cut - they need a bit more work. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % bounded depth first iterative deepening search interpreter % (ie fair search strategy) % won't work with side effects but other sys preds ok % returns all solutions to Goal eventually % avoids duplicating solutions where Prolog wouldn't fair_solve(Goal) :- gen_depth(D, Delta), fair_solve(D, Delta, Goal). % meta interpreter with depth % bound (fail if bound gets to 0) % Doesn't return success unless depth is within Delta of bound % (to stop multiple answers being returned on successive % iterations with increasing depth) % % Should really have goal in first argument for indexing % (NU-Prolog will index on third arg due to when declaration). ?- fair_solve(_, _, G) when G. fair_solve(D, Delta, true) :- !, D < Delta. fair_solve(D, Delta, (A, B)) :- !, fair_solve(D, Delta, A), fair_solve(D, Delta, B). fair_solve(D, Delta, (A ; B)) :- !, ( fair_solve(D, Delta, A) ; fair_solve(D, Delta, B) ). % should do more system preds explicitly fair_solve(D, Delta, A) :- systemPredicate(A), !, call(A). fair_solve(D, Delta, A) :- D > 0, D1 is D - 1, clause(A, B), fair_solve(D1, Delta, B). % generate increasing depth bounds % and difference between them gen_depth(D, Delta) :- gen_depth(3, 100, D, Delta). % initial depth, big delta gen_depth(D, Delta, D, Delta). gen_depth(D0, _, D, Delta) :- Delta1 is D0 // 2 + 1, % anything > 0 would do D1 is D0 + Delta1, % next depth gen_depth(D1, Delta1, D, Delta).