Queries and Disjunctions

Informally, a query is a goal which is submitted to Prolog in order to determine whether this goal is true or false.

As, at top level, Prolog normally expects queries it prints the prompt:

 
?-

A very common syntax error for beginners is to press RETURN before ``.''. This is not a problem ---just type in the missing ``.'' followed by another RETURN.

We look at the case where we only want to solve one goal. Perhaps we would like to determine whether or not

 
woman(jane)

In this case we would type this in and see (what is actually typed is emboldened):

 
?-  woman(jane).

Now ?- woman(jane). is also a clause. Essentially, a clause with an empty head.

We now have to find out ``if jane is a woman''. To do this we must search through the facts and rules known by Prolog to see if we can find out whether this is so.

Note that we make the distinction between facts and rules ---not Prolog. For example, Prolog does not search through the facts before the rules. Here are some facts assumed to be known:

In order to solve this goal Prolog is confronted with a search problem which is trivial in this case. How should Prolog search through the set of (disjunctive) clauses to find that it is the case that ``jane is a woman''?

Such a question is irrelevant at the level of predicate calculus. We just do not want to know how things are done. It is sufficient that Prolog can find a solution. Nevertheless, Prolog is not pure first order predicate calculus so we think it important that you face up to this difference fairly early on.

The answer is simple. Prolog searches through the set of clauses in the same way that we read (in the west). That is, from top to bottom. First, Prolog examines

 
woman(jean).

 
woman(jane).

We introduce the term resolution table. We use this term to represent the process involved in matching the current goal with the head goal of a clause in the program database, finding whatever substitutions are implied by a successful match, and replacing the current goal with the relevant subgoals with any substitutions applied.

We illuminate this using a `window' onto the resolution process (the resolution table). If the match fails then no substitutions will apply and no new subgoals will replace the current goal.

The term substitution is connected with the concept of associating a variable with some other Prolog object. This is important because we are often interested in the objects with which a variable has been associated in order to show that a query can be satisfied.

  
Figure 3.1: A Failed Match

This failure is fairly obvious to us! Also, it is obvious that the next clause man(fred). doesn't match either ---because the query refers to a different relation (predicate) than man(fred). From now on we will never consider matching clauses whose predicate names (and arities) differ.

Prolog then comes to look at the third clause and it finds what we want. All we see (for the whole of our activity) is:

 
?-  woman(jane).

yes

?-

Now think about how the search space might appear using the AND/OR tree representation. The tree might look like:

We see that the search would zig zag across the page from left to right ---stopping when we find the solution.

Note that we will normally omit facts from the representation of this `search space'. In this case we would have a very uninteresting representation.