lee@munnari.OZ (Lee Naish) (06/07/84)
I didn't pay much attention to the recent discussion about breadth
first traversals and that news has been removed from our system. However,
I believe the original question concerned the BF traversal of the SLD (proof)
tree for a given goal. The advantage of BF is that it will find all solutions
eventually (depth first can get lost down an infinite branch). I have just
been working on an algorithm which needs a fair search strategy for SLD trees
so, as a first step, I wrote the following program. It has been breifly tested
on MU-Prolog and C-Prolog.
{decvax,vax135}!mulga!lee
% Breadth first search of the SLD tree of a goal.
% Returns all solutions.
% The main data structure is a list of 'buds' (starts of branches
% which have not been explored). Each one has an instance of the
% initial goal and the current goal for that branch. A difference
% list (X-Y) is used to implement a queue of buds.
% Lee Naish 6/6/84
?- op(400, xfx, :). % used for initial_goal:current_goal
?- op(490, xfy, '.'). % so W:X.Y-Z is ((W:X).Y)-Z
% return all solutions to G, using bf
solve(G, Solns) :-
bf(G:G.X-X, Solns).
% do bf search of SLD tree
bf(X-Y, []) :-
X == Y, % d-list of buds is empty
!.
bf(G:true.X-Y, G.S) :- % found solution - put it on list
!,
bf(X-Y, S).
bf(G:(B1,B).X-Y, S) :-
!,
clauses(B1, Cl),
newbuds(G, B1, B, Cl, Y-Z),
bf(X-Z, S).
bf(G:B.X-Y, S) :-
clauses(B, Cl),
newbuds(G, B, true, Cl, Y-Z),
bf(X-Z, S).
% expand a bud into a d-list of new buds
newbuds(_, _, _, [], X-X).
newbuds(G, B1, B, (H:-T).C, CG:B2.X-Y) :-
copy(G:(B1,B), CG:(H,CB)), % copy so branches dont interfere
cappend(T, CB, B2), % with each other
newbuds(G, B1, B, C, X-Y).
% copy a term
copy(X, Y) :-
assert(tmp(X)),
retract(tmp(Y)),
!.
% get list of clauses for call
clauses(true, [(true:-true)]) :- !.
clauses((X;Y), [(X;Y:-X), (X;Y:-Y)]) :- !.
% handle other system preds here
clauses(H, Cl) :-
all((H:-T), clause(H, T), Cl).
% append for conjunctions (with ',')
cappend(A, true, A) :-
!.
cappend(true, A, A) :-
!.
cappend((A,B), C, (A,D)) :-
!,
cappend(B, C, D).
cappend(A, B, (A,B)).
?- lib all. % all solutions predicate from library
% (could also use bagof)Lee%Ucb-Vax@munnari.UUCP (06/07/84)
I didn't pay much attention to the recent discussion about breadth first traversals and that news has been removed from our system. However, I believe the original question concerned the BF traversal of the SLD (proof) tree for a given goal. The advantage of BF is that it will find all solutions eventually (depth first can get lost down an infinite branch). I have just been working on an algorithm which needs a fair search strategy for SLD trees so, as a first step, I wrote the following program. It has been briefly tested on MU-Prolog and C-Prolog. % Breadth first search of the SLD tree of a goal. % Returns all solutions. % The main data structure is a list of 'buds' (starts of % branches which have not been explored). Each one has ***Sender closed connection*** === Network Mail from host su-score.arpa on Mon Jun 11 02:40:55 ===
Lee%Ucb-Vax@munnari.UUCP (06/07/84)
I didn't pay much attention to the recent discussion about breadth first traversals and that news has been removed from our system. However, I believe the original question concerned the BF traversal of the SLD (proof) tree for a given goal. The advantage of BF is that it will find all solutions eventually (depth first can get lost down an infinite branch). I have just been working on an algorithm which needs a fair search strategy for SLD trees so, as a first step, I wrote the following program. It has been ***Sender closed connection*** === Network Mail from host su-score.arpa on Mon Jun 11 03:01:57 ===
Lee%Ucb-Vax@munnari.UUCP (06/07/84)
I didn't pay much attention to the recent discussion about
breadth first traversals and that news has been removed
from our system. However, I believe the original question
concerned the BF traversal of the SLD (proof) tree for a
given goal. The advantage of BF is that it will find all
solutions eventually (depth first can get lost down an
infinite branch). I have just been working on an algorithm
which needs a fair search strategy for SLD trees so, as a
first step, I wrote the following program. It has been
briefly tested on MU-Prolog and C-Prolog.
% Breadth first search of the SLD tree of a goal.
% Returns all solutions.
% The main data structure is a list of 'buds' (starts of
% branches which have not been explored). Each one has
% an instance of the initial goal and the current goal
% for that branch. A difference list (X-Y) is used to
% implement a queue of buds.
% -- Lee Naish 6/6/84
?- op(400, xfx, :). % used for initial_goal:current_goal
?- op(490, xfy, '.'. % so W:X.Y-Z is ((W:X).Y)-Z
% return all solutions to G, using bf
solve(G, Solns) :-
bf(G:G.X-X, Solns).
% do bf search of SLD tree
bf(X-Y, []) :-
X == Y, % d-list of buds is empty
!.
bf(G:true.X-Y, G.S) :- % found solution - put it on list
!,
bf(X-Y, S).
bf(G:(B1,B).X-Y, S) :-
!,
clauses(B1, Cl),
newbuds(G, B1, B, Cl, Y-Z),
bf(X-Z, S).
bf(G:B.X-Y, S) :-
clauses(B, Cl),
newbuds(G, B, true, Cl, Y-Z),
bf(X-Z, S).
% expand a bud into a d-list of new buds
newbuds(_, _, _, [], X-X).
newbuds(G, B1, B, (H:-T).C, CG:B2.X-Y) :-
copy(G:(B1,B), CG:(H,CB)), % copy so branches dont
cappend(T, CB, B2), % interfere with each other
newbuds(G, B1, B, C, X-Y).
% copy a term
copy(X, Y) :-
assert(tmp(X)),
retract(tmp(Y)),
!.
% get list of clauses for call
clauses(true, [(true:-true)]) :- !.
clauses((X;Y), [(X;Y:-X), (X;Y:-Y)]) :- !.
% handle other system preds here
clauses(H, Cl) :-
all((H:-T), clause(H, T), Cl).
% append for conjunctions (with ',')
cappend(A, true, A) :-
!.
cappend(true, A, A) :-
!.
cappend((A,B), C, (A,D)) :-
!,
cappend(B, C, D).
cappend(A, B, (A,B)).
?- lib all. % all solutions predicate from library
% (could also use bagof)