Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!security!genrad!decvax!harpo!floyd!clyde!akgua!psuvax!burdvax!presby!seismo!hao!hplabs!sri-unix!Pereira@SRI-AI
From: Pereira%SRI-AI@sri-unix.UUCP
Newsgroups: net.lang.prolog
Subject: Breadth-first Search
Message-ID: <14001@sri-arpa.UUCP>
Date: Sun, 20-Nov-83 22:35:52 EST
Article-I.D.: sri-arpa.14001
Posted: Sun Nov 20 22:35:52 1983
Date-Received: Tue, 29-Nov-83 06:12:37 EST
Lines: 46

Wayne Christopher asked about breadth-first search in Prolog, in
particular how to enumerate all expressions over some vocabulary
of symbols with the shortest expressions first. Here is a short
program in pure Prolog that does the job:

:- op(500,fy,succ).

genterm(T) :-
   size(S),
   genterm(T,S,0).

size(0).
size(succ N) :- size(N).

genterm(X,S0,S) :-
   variable_cost(S0,S).
genterm(C,S0,S) :- constant(C,S0,S).
genterm(T,S0,S) :-
   term(T,As,S0,S1),
   genargs(As,S1,S).

genargs([],S,S).
genargs([A|As],S0,S) :-
   genterm(A,S0,S1),
   genargs(As,S1,S).

% Sample data.
% Add a clause for variable_cost if terms with variables are needed.

constant(a,S,S).        % zero cost constant
constant(b,succ S,S).   % unit cost constant

term(f(X,Y),[X,Y],succ succ S,S).
term(g(X),[X],succ S,S).

The predicate genterm/1 is intended to be used as a generator
of terms to be tested by some other predicate(s). Each solution
of genterm/1 is a different term. Terms are generated in order
of complexity, where the complexity of each constant and function
symbol is given separately in a constant/3 or term/4 clause.
Actually, the first argument of term/4 need not be a single
functor applied to variable arguments, but can be any term,
provided that the variables in it that are to be filled by
other  generated terms are listed in the second argument.

-- Fernando Pereira