Previous Table of Contents Next


6.2.7. Complex Terms in Heads of Clauses

So far, although we have been working with queries with a mixture of constant and variable arguments, all the clauses we have seen have had either all constants or all variables in the heads. In fact, clauses—both rules and facts—can have a mixture of constants and variables in the heads as well. In this section, we will see how to derive such clauses from the simpler clauses I have been writing. The transformed clauses are usually much more concise and contain fewer equality goals in the bodies.

In the body of a predicate, whenever we see a variable being equated to another term, we can transform the clause by replacing all occurrences of the variable by the term and eliminating that equality.2 After all, if two things are equal, we should be able to replace one with the other anywhere. For instance, consider the clause


2Strictly speaking, this applies only to clauses without cuts, a feature we will get to later. For the kinds of clauses we have been looking at so far, it holds true.
   member(List, X) :-
     List = [Head|Tail],
     member(Tail, X).

We can take List in this clause, replace it everywhere in the clause by [Head|Tail], and eliminate the equality, resulting in

   member([Head|Tail], X) :-
     member(Tail, X).

Similarly, in the first clause defining member, namely

   member(List, X) :-
    List = [Head|Tail],
    X = Head.

we can replace List by [Head|Tail] in the same manner, resulting in

   member([Head|Tail], X) :-
    X = Head.

We can further replace X with Head and eliminate that equality; here, because we have eliminated the last part of the body, the rule turns into a fact:

   member([Head|Tail], Head).

It is in fact a fact; for any list of the form [Head|Tail], Head is a member of the list.

Thus the new definition of member that we derive from these clauses is simply

   member([Head|Tail], Head).
   member([Head|Tail], X) :-
    member(Tail, X).

We can read this new definition as follows: “Head is a member of the list [Head|Tail], and X is a member of the list [Head|Tail] if it is a member of the list Tail.” It’s a bit harder for a beginning Prolog programmer to see that this definition is also complete and correct, but we will get the hang of these definitions quickly. This is the standard definition of member that we are likely to find in other books (aside from the choice of variable names).

We can perform similar operations on the definition of append and derive the three-line definition

   append([], List2, List2).
   append([H|T], List2, [H|Temp]) :-
    append(T, List2, Temp).

This is also the standard definition of append and can be read as follows: “The result of appending the empty list and List2 is just List2, and the result of appending [H|T] and List2 is [H|Temp] if the result of appending T and List2 is Temp.”

When we want to write our own predicates, we may find it useful to start out with an equality-style definition and then later massage it into the more concise format. Conversely, if we find a definition that we read hard to understand, it may be helpful to go backward to the equality-style definition.

6.2.8. How Prolog Does It

How does Prolog find the solutions it finds? The answer is with a fairly straightforward depth-first search algorithm. This algorithm can be considered to be the execution model of a Prolog program. This section explores this execution model.

The Prolog algorithm is given a query and systematically works its way through the query, guessing at which substitutions make the query true. The guesses are not arbitrary but are based on the facts and rules in the program in the order in which Prolog finds them. Every time Prolog comes up against an equality that cannot be satisfied, it knows it has guessed wrong some time in the past and backtracks to make another guess.

A simplified version of this algorithm, written in imperative-functional pseudocode, can be found in Figures 6.1 and 6.2. These figures have to do with three functions, each of which takes a goal as an argument.


FIGURE 6.1.  A simplified version of Prolog’s search algorithm: the functions solve and solve_clause.


FIGURE 6.2.  The algorithm for solve_eq called by solve.

Recall that a goal is any sequence of atoms (a_1, ..., a_n); for the purposes of these algorithms, it can also be the empty sequence of atoms, written (). The three functions are

  solve(G), which takes a goal G and returns either the token exit or the token redo. exit is intended to mean that the system has reported on an answer and the user has been satisfied with it; redo means the system should backtrack and try again, either because it has reached an unsatisfiable equality or because the user has requested it to backtrack with a semicolon at a solutions prompt.
  solve_clause(a, C, G), which takes an atom a, a clause C, and a goal G and tries to find a satisfying substitution for the goal (a, G) by using only clause C with a. It returns the same things as solve.
  solve_eq(s, t, G), which tries to find a satisfying substitution for the goal s=t, G. It also returns the same things as solve.

When a query Q is given to Prolog, it behaves as if it has called the function solve on the query. Note that solve may call the specialized functions solve_clause or solve_eq, both of which may call solve recursively. It is also worth noting that the comma separating atoms is essentially an associative operator so that the goal ((p, q), r) is treated the same way as (p, q, r).


Previous Table of Contents Next