Pereira%SRI-AI@sri-unix.UUCP (11/21/83)
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