Case Study: Other Ways of Thinking - Thinking as Computation - page 246

Figure 11.4. A forward-chaining procedure

estfc.pl

% estfc(K,Q) holds if query Q can be established from knowledge base K.
% The method is forward-chaining.
estfc(K,Q) :- allsolved(K,Q).
estfc(K,Q) :- nkb(K,K1), estfc(K1,Q).
allsolved(_,[]).
allsolved(K,[A|Q]) :- solved(K,A), allsolved(K,Q).
solved(K,A) :- member([A],K).
nkb(K,[[A]|K]) :- member([A|B],K), \+ solved(K,A), allsolved(K,B).

1. If all the query atoms are solved, the procedure returns success .

2. Otherwise, look for a clause in the knowledge base whose head is not solved but

whose body consists of atoms that are all solved.
a. If none is found, the procedure returns failure .

b. If one is found, extend the knowledge base to include the head as a new atomic

clause in the KB, and go back to step 1.

A Prolog program that realizes this procedure is shown in figure 11.4.
Whenever the predicates est and estbf return an answer, the predicate estfc will
return the same answer. Here is a trace of a query:
Call: (6) estfc([[a],[b],[u,p,b],[p,a]], [u])
Call: (7) estfc([[p],[a],[b],[u,p,b],[p,a]], [u])
Call: (8) estfc([[u],[p],[a],[b],[u,p,b],[p,a]], [u])
Exit: (8) estfc([[u],[p],[a],[b],[u,p,b],[p,a]], [u])
Exit: (7) estfc([[p],[a],[b],[u,p,b],[p,a]], [u])
Exit: (6) estfc([[a],[b],[u,p,b],[p,a]], [u])

Note that in the recursive calls to estfc , the KB first grows to include p (since the
atom in its body, a , is already solved), and then u (since the atoms in its body, p and
b , are then solved). At this point, the resulting new KB contains atomic clauses for all
the atoms in the query, and so the query is established.
Unlike the predicates est and estbf , the forward-chaining estfc procedure will
never get stuck in a loop. To see this, note that each time estfc is used recursively, it
is on a new KB that includes an additional solved atom. Once all the atoms mentioned
in the KB have been considered, nkb must then fail, and the procedure terminates.