Previous | Table of Contents | Next |
6.2.2.4. Recursive Predicates
Prolog does repeated computation by the usual method of declarative languagesnamely, 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 recursivelyfor 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 VIIs descendantsjust 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 VIIIs descendants died out, so the monarchy passed to the descendants of Henrys sister Margaret, who happened to have married the King of Scotland.
Lets now summarize more rigorously the small subset of Prolog we have been working with:
This is only a subset of full Prolog, and as we go on, we will expand it.
Lets 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, youre 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 |