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

Figure 11.6. The final version of back-chaining

est.pl

% est(K,Q) holds if query Q can be established from knowledge base K.
% This version performs Prolog back-chaining.
% It handles equality, negation, and variables.
est(_,[]). % No query atoms
est(K,[eq(X,X)|T]) :- est(K,T). % Equality.
est(K,[not(A)|T]) :- \+ est(K,[A]), est(K,T). % Negation.
est(K,[A|T]) :- member_copy([A|B],K), append(B,T,Q), est(K,Q).
% member_copy(X,L): X is an atomic element of L or a copy otherwise.
member_copy(X,L) :- member(X,L), X=[_].
member_copy(X,L) :- member(E,L), \+ E=[_], copy_term(E,X).

seen, copy_term behaves just like Prolog = except in the presence of (uninstantiated)
variables.
A final version of the est predicate that handles all the new elements (equality,
negation, variables) appears in figure 11.6. Here is how it works:

The first clause is as before;

The second clause handles a query whose first literal is an equality by unifying
the two arguments and then continuing with the rest of the query.

The third clause handles a query whose first literal is a negation by ensuring that
the unnegated literal fails and then continuing with the rest of the query.

The fourth clause handles a query whose first literal is an atom . It is as before
except that member_copy is used instead of member .
The member_copy predicate here behaves just like member when the first argument
happens to be a list with just one element (representing a clause that has no body).
Otherwise, member_copy uses copy_term . This has the effect of finding a matching
clause in the knowledge base but leaving its variables uninstantiated for later use.
(Assume here that variables only appear in clauses with bodies.)
The following queries illustrate the behavior of the new est predicate:
?- est([[p(a)],[p(b)],[q(X),p(X)]], [q(a),q(b)]).
Yes

?- est([[p(a)],[p(b)],[q(X),p(X)]], [q(Y),not(eq(Y,a))]).
Y=b
Yes