Implementing forwards inference in Prolog

In order to distinguish the inference rules that will be used by our forwards inference engine from those that Prolog itself accesses directly, we will introduce a bit of special syntax so that 'if' can stand as the forwards inference counterpart of Prolog's ':-' and 'and' as the counterpart of ','. This is simple to do with a couple of operator declarations:

Code:families.pl



?-op(400,xfx,if).

?-op(300,xfy,and).

Thus, instead of writing:

father(X,Y) :- parent(X,Y), male(X).

and letting Prolog do the inference for us (backwards), we will write:

father(X,Y) if parent(X,Y) and male(X).

and allow this to be interpreted by our forwards inference program. What we have done here is allow Prolog to accept inference rules written in exactly the language that we introduced in the previous section. Note that the 'and' operator associates to the right (just as Prolog's ',' conjunction operator does), so this:

sibling(X,Y) if parent(Z,X) and parent(Z,Y) and distinct(X,Y).

is to be understood as:

sibling(X,Y) if (parent(Z,X) and (parent(Z,Y) and (distinct(X,Y)))).

Here are some more example rules in this format, excerpted from the file families.pl:

brother(X,Y) if sibling(X,Y) and male(X).

child(X,Y) if parent(Y,X).

child(X,Z) if child(X,Y) and married(Y,Z).

child(X,Y) if daughter(X,Y).

child(X,Y) if son(X,Y).

daughter(X,Y) if female(X) and child(X,Y).

female(X) if daughter(X,Y).

female(X) if married(X,Y) and male(Y).

male(X) if husband(X,Y).

male(X) if son(X,Y).

married(X,Y) if married(Y,X).

married(X,Y) if husband(X,Y).

mother(X,Y) if parent(X,Y) and female(X).

parent(X,Y) if child(Y,X).

parent(X,Y) if parent(X,Z) and sibling(Y,Z).

sibling(X,Y) if sibling(Y,X).

sister(X,Y) if sibling(X,Y) and female(X).

son(X,Y) if male(X) and child(X,Y).

wife(X,Y) if female(X) and married(X,Y).

Code:forwards.pl

We will similarly represent simple facts (things which are unconditionally true) using the predicate 'fact'

fact(son(charles,elizabeth_ii)).

fact(supplies(morgan_bros,tyres)).



Given this format for inference rules and facts, we can now implement a simple

forwards inference system, whose main predicate is 'add'.

This predicate takes a simple proposition, which is assumed

to contain no variables, and adds it as a fact to the database.

If the presence of this new fact makes any inference rules apply in

new ways, then the conclusions of those rules are also added to the

database.

This may cause more rules to run, and so on.

If the theorem being added is already known to be a fact, nothing is done:










add(Fact) :-

   fact(Fact), !.









Otherwise, the theorem is asserted to be a fact, and new consequences

that stem from its addition to the database are found:








add(Fact) :-

   assert(fact(Fact)),

   find_new_consequences(Fact).









To find these new consequences, each inference rule in turn

(Theorem if Premises) is considered and an attempt is made to match

the new fact against one of

the premises (select(Fact, Premises, Remainder)).  If this succeeds,

then it is necessary to check

that the remaining premises are all also facts (all_facts(Remainder)),

and, if so, draw the relevant inference and add the new theorem the

database (add(Theorem)):








find_new_consequences(Fact) :-

   Theorem if Premises,

   select(Fact,Premises,Remainder),

   all_facts(Remainder),

   add(Theorem),

   fail.

find_new_consequences(Fact).









The 'fail' which ends the first clause is there to force Prolog to backtrack

over all the inference rules, whilst the second clause is there to

guarantee eventual successful termination, after all the inference rules have

been tried.



The predicate we have just defined depends crucially on a couple

of utility predicates, the first of which, 'select', matches a

fact against a conjoined list of premises and returns the remainder.

If the fact exhausts the list of premises, then it returns 'true':








select(Fact,Fact,true).









Or, if the fact matches the first conjunct, then it returns the

remaining conjuncts:








select(Fact,Fact and Facts,Facts).









If it does not match the first conjunct, then it tries to match against

the other premises, whilst adding the fact that did not match to

the remainder that will be returned:








select(Fact1,Fact2 and Facts1,Fact2 and Facts2) :-

                 select(Fact1,Facts1,Facts2).









The other utility predicate, 'all_facts', simply checks that every

purported fact in a conjunction of purported facts is really a fact.

Its definition follows a familiar recursive pattern.

If there are two or more facts, check the first, then the rest:








all_facts(Fact and Facts) :-

	fact(Fact),

	all_facts(Facts).









Otherwise, in the case where there is but a single fact, then

just look it up in the database:








all_facts(Fact) :-

	fact(Fact).









Finally, we need to stipulate that 'true' is a fact (so that 'all_facts(true)'

succeeds):








fact(true).









And, if we want, we can exploit the resources of Prolog so as to define

some useful predicates in an intuitively reasonable way, for example,

an identity predicate and its negation:








fact(equals(X,X)).

fact(distinct(X,Y)) :- X \\= Y.









In order to experiment with this program, it is convenient to employ

a loop that allows the user to add facts between each round of inferencing.

This is readily done as follows:








go :- read(Fact), add(Fact), go.









It is also helpful for experimentation to have a tracing facility that

enables one to see which inference rules are responsible for the

inferences drawn.  The program FORWARDS.PL in the appendix, whilst

essentially identical to the code above, incorporates such a facility.

Here, to illustrate it, is an example of a brief interaction with

the program.  The user input is prefaced by the prompt '|:', the rest

of the material being a trace of the inferences being drawn:








?- go.

|: daughter(mayumi,hans).

   |- child(mayumi, hans), from daughter(mayumi, hans).

   |- parent(hans, mayumi), from child(mayumi, hans).

   |- female(mayumi), from daughter(mayumi, hans).

|: son(wolfgang,mariko).

   |- child(wolfgang, mariko), from son(wolfgang, mariko).

   |- parent(mariko, wolfgang), from child(wolfgang, mariko).

   |- male(wolfgang), from son(wolfgang, mariko).

|: husband(hans,mariko).

   |- male(hans), from husband(hans, mariko).

   |- father(hans, mayumi), from parent(hans, mayumi) and male(hans).

   |- married(hans, mariko), from husband(hans, mariko).

   |- child(mayumi, mariko), from child(mayumi, hans)

      and married(hans, mariko).

   |- daughter(mayumi, mariko), from female(mayumi)

      and child(mayumi, mariko).

   |- parent(mariko, mayumi), from child(mayumi, mariko).

   |- sibling(mayumi, wolfgang), from parent(mariko, mayumi)

      and parent(mariko, wolfgang) and distinct(mayumi, wolfgang).

   |- sibling(wolfgang, mayumi), from sibling(mayumi, wolfgang).

   |- brother(wolfgang, mayumi), from sibling(wolfgang, mayumi)

      and male(wolfgang).

   |- parent(hans, wolfgang), from parent(hans, mayumi)

      and sibling(wolfgang, mayumi).

   |- child(wolfgang, hans), from parent(hans, wolfgang).

   |- son(wolfgang, hans), from male(wolfgang)

      and child(wolfgang, hans).

   |- father(hans, wolfgang), from parent(hans, wolfgang)

      and male(hans).

   |- sister(mayumi, wolfgang), from sibling(mayumi, wolfgang)

      and female(mayumi).

   |- married(mariko, hans), from married(hans, mariko).

   |- female(mariko), from married(mariko, hans) and male(hans).

   |- mother(mariko, wolfgang), from parent(mariko, wolfgang)

      and female(mariko).

   |- mother(mariko, mayumi), from parent(mariko, mayumi)

      and female(mariko).

   |- wife(mariko, hans), from female(mariko) and married(mariko, hans).









 Exercise 9.4





 Send us a comment. 
 Chapter: chapter-09-sh-1.4.html 
         
          
 
 [Contents] [Previous] [Next] 


This document was translated by troff2html v0.21 on October 22, 1996.