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:

• 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).
```
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: Standard Programming Style Up: Getting Started Previous: Getting Started

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