[comp.lang.prolog] "clause", breadth-first evaluation?

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).