A Simple Conjunction

Now to look at a goal which requires Prolog to solve two subgoals. Here is our set of facts and one rule.

We shall ask whether ``jean is happy''. We get this terminal interaction:

 
?-  happy(jean).

no

?-

 
happy(jean)

 
happy(Person)

We call this matching process unification. What happens here is that the logical variable Person gets bound to the atom jean. You could paraphrase ``bound'' as ``is temporarily identified with''. See figure 3.2 for what happens in more detail.

In this case the match produces a substitution, Person=jean, and two subgoals replace the current goal. The substitution of Person by jean is known as a unifier and often written Person/jean. The process of replacing a single goal by one or more subgoals ---with whatever substitutions are applicable--- is part of the resolution process.

To solve our problem, Prolog must set up two subgoals. But we must make sure that, since Person is a logical variable, that everywhere in the rule that Person occurs we will replace Person by jean.

We now have something equivalent to:

 
happy(jean):-

		      woman(jean),

		       wealthy(jean).

  
Figure 3.2: A Successful Match

So the two subgoals are:

 
woman(jean)

wealthy(jean)

Here we come to our next problem. In which order should Prolog try to solve these subgoals? Of course, in predicate logic, there should be no need to worry about the order. It makes no difference ---therefore we should not need to know how Prolog does the searching.

Prolog is not quite first order logic yet. So we will eventually need to know what goes on. The answer is that the standard way to choose the subgoal to work on first is again based on the way we read (in the west)! We try to solve the subgoal woman(jean) and then the subgoal wealthy(jean).

There is only one possible match for woman(jean): our subgoal is successful. However, we are not finished until we can find out if wealthy(jean).

There is a possible match but we cannot unify

 
wealthy(fred)

 
wealthy(jean)

So Prolog cannot solve our top level goal ---and reports this back to us. Things would be much more complicated if there were any other possible matches. Now to look at the (non-standard) AND/OR tree representation of the search space. Here it is:

Note that it becomes very clear that knowing that ``fred is a man'' is not going to be of any use. That is why man(fred) is in braces. From now, we will exclude such from our `search space'.

We can now see that the way Prolog searches the tree for AND choices is to zig zag from left to right across the page! This is a bit like how it processes the OR choices except that Prolog must satisfy all the AND choices at a node before going on.

Zig zagging from left to right is not the whole story for this goal. Once we reach wealthy(Person) with Person/jean and it fails we move back (backtracking) to the goal woman(Person) and break the binding for Person (because this is where we made the binding Person/jean). We now start going from left to right again (if you like, forwardtracking).