next up previous
Next: Standard Programming Style Up: Getting Started Previous: Getting Started

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:

Anatomy of a fact:

Anatomy of a rule:

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:

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).
Here the second clause of the predicate ancestor is recursive because it has ancestor(A, B) as its head and ancestor(A, P) as the second subgoal in its body.

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 **

next up previous
Next: Standard Programming Style Up: Getting Started Previous: Getting Started

Dave Stuart Robertson
Tue Jul 7 10:44:26 BST 1998