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:
parent(fred, greta).
is a fact.
parent
is a predicate name.
fred
is the first argument.
greta
is the second argument.
parent
, fred
and greta
are atoms.
Anatomy of a rule:
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
is a rule.
grandparent(X, Z)
.
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.
X
, Y
and Z
are variables.
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
.
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
.
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:
?- grandparent(fred, X).is satisfiable from the program at the top of the page, with
X
instantiated to henry
.
?- 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 **