Previous | Table of Contents | Next |
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, clausesboth rules and factscan 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. Its 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.
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 Prologs 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
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 |