Previous Table of Contents Next


6.2.2.4. Recursive Predicates

Prolog does repeated computation by the usual method of declarative languages—namely, recursion. We can add the following clauses to the genealogy program:

   ancestor(X, Y) :- parent(X, Y).
   ancestor(X, Y) :- parent(X, Parent), ancestor(Parent, Y).

These clauses can be read as follows: If Y is a parent of X, then Y is an ancestor of X; if Parent is a parent of X and Y is an ancestor of Parent, then Y is an ancestor of X. Prolog can use these rules to find ancestors recursively—for instance, returning three ancestors of James V of Scotland for the query ancestor(james_v_of_scotland, X): james_iv_of_scotland, margaret_tudor, and henry_vii.

As with father, we can run this query in either direction, and in fact, it might be useful to define the following predicate:

   descendent(X, Y) :- ancestor(Y, X).

This rule says that Y is a descendent of X if X is an ancestor of Y. If we now enter the query descendent(henry_vii, Heir), we get the list of all Henry VII’s descendants—just about everyone mentioned in the knowledge base.

Incidentally, this example explains why the monarchs of Scotland became the monarchs of England too; all of Henry VIII’s descendants died out, so the monarchy passed to the descendants of Henry’s sister Margaret, who happened to have married the King of Scotland.

6.2.3. A Grammatical Summary

Let’s now summarize more rigorously the small subset of Prolog we have been working with:

  An identifier is a sequence of alphanumeric characters and underscores.
  A constant is an identifier beginning with a lowercase letter, a single-quoted sequence of characters, or an integer.
  A predicate name is an identifier beginning with a lowercase letter.
  A variable is an identifier beginning with an uppercase letter.
  A term is a constant or variable.
  An atom is an expression of the form p or p(t1, …, tn), where p is a predicate name and each ti is a term.
  A goal is an expression of the form a1, …, an, where each ai is an atom.
  A query is a goal terminated by a period.
  A fact is an atom terminated by a period.
  A rule is an expression of the form a :- g., where a is an atom and g is a goal.
  A clause is a fact or a rule.
  A program is a sequence of clauses.

This is only a subset of full Prolog, and as we go on, we will expand it.

6.2.4. Equality and Variables

Let’s expand our syntax of Prolog now to include another kind of goal. This section explores the equality predicate and how Prolog solves equality queries involving variables.

6.2.4.1. Properties of the Equality Predicate

An expression of the form s = t, where s and t are both terms, is called an equality goal. = is technically a binary predicate, but it appears in an infix position in order to conform to the usual practice in mathematics and logic.

How does Prolog evaluate equality queries? As we might expect, the query a = a just returns yes. Here, a is a constant, and we are merely asking whether it is equal to itself. If we type the query a = b, however, Prolog returns no; two constants that do not have the same name are always treated as unequal. Thus the queries a = 37 and ‘foo bar’ = 9 also fail. However, the query ‘archy’ = archy succeeds, indicating that putting single quotes around an identifier that is already a constant results in the same constant, as far as Prolog is concerned.

This behavior has a natural extension to variables. The query X = b returns one solution, namely X = b. What we might not expect is that the query b = X returns the same thing. Equality is a symmetric relation; when it handles equality queries, Prolog is just trying, as it always does, to find a term to substitute for X that makes the query true. When we substitute X by b in b = X, we get b = b: a true query.

Now, what do you think the following query should return?

   X = a, X = b.

If you answered no, you’re right. Although equality has somewhat the flavor of the assignment statement of an imperative programming language, a Prolog variable can only ever be “equal to” one term. If we try substituting X by a in X = a, X = b, for example, we get a = a, a = b, which is false because a = b is false; and if we try b, we get b = a, b = b, which is false because b = a is false. There is no substitution for X that makes the query true, so no is the appropriate answer.

6.2.4.2. Equalities with More Than One Variable

Queries involving equality and more than one variable are solved in a similar way, by Prolog attempting to find a satisfying substitution of values for all the variables. Consider the following four queries:

   X = a, Y = b.           % Query 1
   X = a, Y = X.           % Query 2
   X = a, Y = b, X = Y.    % Query 3
   X = Y.                  % Query 4

The first query returns X = a, Y = b as a solution; and the second returns X = a, Y = a. But the third query returns no because there is no substitution that satisfies the query; X and Y cannot be both equal to different constants and equal to each other. The fourth query does not put any constraint on the two variables other than that they are equal to each other; so the substitution that is returned is just X = Y itself. This indicates that if we replaced X by Y, it would produce the trivially true query Y = Y.


Previous Table of Contents Next