Some Anatomy

Prolog programs consist of clauses. For example, the following is a valid Prolog program containing 3 clauses (1 per line in this example):

parent(fred, greta).
parent(greta, henry).
grandparent(X, Z):- parent(X, Y), parent(Y, Z).

All Prolog clauses are terms finishing with a full stop symbol.

Prolog clauses are normally of three types:

• facts declare things that are always true.
• rules declare things that are true depending on a given condition.
• questions to find out if a particular goal is true.

Anatomy of a fact:

• parent(fred, greta). is a fact.
• parent is a predicate name.
• fred is the first argument.
• greta is the second argument.
• Arguments in a term are separated by commas.
• parent, fred and greta are atoms.

Anatomy of a rule:

• grandparent(X, Z) :- parent(X, Y), parent(Y, Z). is a rule.
• Its head is grandparent(X, Z).
• Its body is parent(X, Y), parent(Y, Z).
• parent(X, Y) is the first subgoal of the rule.
• parent(Y, Z) is the second subgoal of the rule.
• Subgoals in the body of a rule are separated by commas.
• X, Y and Z are variables.
• Its declarative interpretation can be stated in two different ways:
  • For all X and Z, X is a grandparent of Z if there exists some Y such that X is a parent of Y and Y is a parent of Z.
  • For all X, Y and Z, if X is a parent of Y and Y is a parent of Z then X is a grandparent of Z.
• Its procedural interpretation can be stated as:
  • The goal grandparent(X, Z) succeeds with binding X1 for X and and binding Z1 for Z if first, the goal parent(X, Y) succeeds with bindings X1 and Y1 and then the goal parent(Y, Z) succeeds with bindings Y1 and Z1.

Running a Prolog program consists of supplying some question. This also is referred to as giving an initial goal or query. A goal succeeds if it is satisfiable from the set of clauses constituting ther Prolog program. A goal fails if it is unsatisfiable from the set of clauses constituting the Prolog program. For example:

• The query:

  ?- grandparent(fred, X).
  

  is satisfiable from the program at the top of the page, with X instantiated to henry.
• On the other hand, the query:

  ?- grandparent(fred, bob).
  

  is not satisfiable from the program at the top of the page because bob doesn't appear in that set of clauses.

Prolog programs can be recursive. That is, a rule with some predicate as its head can contain a reference to the same predicate in its body. Consider the following program:

/* Clause1 */ ancestor(A, B):- parent(A, B).
/* Clause2 */ ancestor(A, B):- parent(P, B), ancestor(A, P).
/* Clause3 */ parent(fred, greta).
/* Clause4 */ parent(greta, henry).

The Prolog interpreter can backtrack to find alternative solutions to a given goal. Backtracking can be forced by typing a semi-colon after Prolog finds the first solution to the query. For example, we get the following behaviour when running the program given above:

What you see on the screen (annotations between ** symbols) is:

| ?- ancestor(X, henry).  ** I give a query to Prolog **
 
     X=greta ;  ** It finds a solution and I type a semi-colon **

     X=fred    ** Another solution is found for the original query **
yes   ** Since I didn't type another semi-colon Prolog reports success **
| ?-  ** and prompts for another query **

An explanation of how Prolog obtains this observed behaviour is given by the following annotated sequence of events. Goal1 is the initial query.

Goal1:      ancestor(X, henry).
        ** Match head of Clause1 to Goal1 **
Clause1(a): ancestor(X, henry) if (Goal2) parent(X, henry).
        ** Attempt to satisfy Goal2 **
Goal2:      parent(X, henry).
        ** Match to Clause4 to Goal2 **
Clause4(a): parent(greta, henry).
        ** SUCCEED with X = greta **
        ** Asked to find another solution **
        ** so backtrack to look for alternative solution for Goal2 **
        ** No further matches for Goal2 **
        ** so backtrack to look for alternative solution for Goal1 **
        ** Match head of Clause2 to Goal1 **
Clause2(a): ancestor(X, henry) if (Goal3) parent(P, henry)
                              and (Goal4) ancestor(X, P).
        ** Attempt to satisfy Goal3 **
Goal3:      parent(P, henry).
        ** Match Clause4 to Goal3 **
Clause4(b): parent(greta, henry).
        ** so P is now bound to 'greta' **
        ** Attempt to satisfy Goal4 **
Goal4:      ancestor(X, greta).
        ** Match Clause 1 to Goal4 **
Clause1(b): ancestor(X, greta) if (Goal5) parent(X, greta).
        ** Attempt to satisfy Goal2 **
Goal5:      parent(X, greta).
        ** Match to Clause3 to Goal2 **
Clause3(a): parent(fred, greta).
        ** SUCCEED with X = fred **