A Prolog to Prolog

John F. Sowa

1. Features of Prolog

Programming languages designed by committees typically start with enormous collections of "features." Other languages, like Basic and Lisp, started with simple forms, but they have grown to a point where they look like languages designed by committees. Prolog's strength is not derived from a laundry list of features, but from its underlying structure based on logic. Some features have been added to Prolog for interfaces with the operating system, but the logical core is complete enough for a universal computing system. This section presents a quick overview of Prolog structures. Later sections will explore these structures with more detailed examples.

Nonprocedural Programming

Prolog has procedural and nonprocedural aspects. Instead of writing a procedure with an explicit sequence of steps, a Prolog programmer writes a declarative set of rules and facts that state relationships. Because of its declarative style, conventional flowcharts and coding techniques cannot be used with Prolog. Yet Prolog rules are executed by an underlying inference engine, which does impose an order of execution. Because of that implicit ordering, Prolog rules also have a procedural interpretation. Unlike the linear flow through conventional procedures, Prolog rules are executed by backtrack search. This method is very powerful for many problems in artificial intelligence, but it requires that programmers learn a new way of thinking.

Ten-year-old children have found Prolog an easy language to learn. But professional programmers with many years of experience often find it puzzling and confusing. What is puzzling about Prolog is its simplicity. It does not have the most frequently used features of the common procedural languages:

Assignment statements,
Go-to statements,
If-then-else statements, and
Do-loops, for-loops, and while-loops.

Without these features, standard flowcharts cannot be translated into Prolog. After many years of structured programming, people have learned to replace go-to statements with loops and if-then-else statements. But Prolog does not have those statements either. The most surprising feature of Prolog, however, is the absence of an assignment statement. Without it, there is no way to change the value of a variable. In IBM Prolog, there is an operator that looks like assignment, as in X:=X+1, but the result is false, since there is no value of X that could ever be equal to X+1. Before using Prolog effectively, a programmer has to forget the old procedural habits and learn a new declarative way of thinking.

After programmers recover from the initial shock of learning what Prolog does not have, they can begin to appreciate the features that it does have:

Predicates that express relationships between entities,
A method of defining predicates by asserting rules and facts,
A method of asking questions or starting computations by issuing goals,
A backtracking search procedure for evaluating goals,
Data structures that can simulate Pascal-like records or Lisp-like lists,
A pattern matcher that builds and analyzes the data structures, and
A set of built-in predicates for arithmetic, input/output, and system services.

These features provide a language that is universal in the sense that it can simulate a Turing machine—the most general digital computing device known. In principle, Prolog can compute anything that can be computed in any other programming language. But the way that it is done in Prolog is totally different from conventional languages. For complex problem solving, the Prolog approach is typically the most convenient.

Facts and Predicates

In Prolog, a fact is a statement that some entity has a particular property or that some relationship holds between two or more entities. Facts are expressed by applying a predicate to a list of arguments. For example, human(socrates) is a Prolog fact: the predicate is named human, and the argument is the constant socrates. This fact corresponds to the English sentence "Socrates is human." Following are other examples of facts stated in Prolog notation:

odd(5).
married(zeus, hera).
supply(acme, toothbrush, 100, 'July 14, 1989').

The fact odd(5) states that 5 is an odd number. The second fact says that Zeus and Hera are married; and the third says that Acme supplied 100 toothbrushes on July 14, 1989. The single quotes in 'July 14, 1989' are used to enclose a character string in IBM Prolog.

A constant or a predicate name can be chosen in many ways. The fact qz3x(gglfn5) is handled by the Prolog system in the same way as human(socrates). For readability, however, the names should reflect the intention of the human programmer. Following are some common naming conventions:

A predicate with one argument, in the form p(A), usually means that the entity &A has property or attribute p. The fact dog(snoopy) means "Snoopy is a dog."
A predicate with two arguments, in the form r(A,B), typically means that &A stands in relation &r to B. The fact child(sam,mary) means "Sam is a child of Mary."
For a predicate that does some computation, the input arguments are usually placed first, and the results are put at the end: sum(3,5,8) means "The sum of 3 and 5 is 8."
For a predicate that takes many arguments, the more important arguments are put first, and the less important ones later. For the fact "Acme supplied 100 toothbrushes on July 14, 1989," the most important argument is probably the supplier, next the type of item, next the quantity, and finally the date. Therefore one would write
```
supply(acme, toothbrush, 100, 'July 14, 1989')
```

Although these conventions are commonly followed, they do not always apply. Some predicates, like married(A,B), are symmetric, and either argument could be written first. For many computational predicates, any argument may be treated as the output and the other arguments as input: sum(X,5,8) computes a number X, which when added to 5 produces 8; in this case, the first argument X may be considered the output. The flexibility in treating any argument as either input or output makes many Prolog predicates reversible. This property will be used in a number of examples throughout this book.

Constants, Variables, and Rules

Variables start with an uppercase letter. Constants, however, are either enclosed in quotes, or they start with a lower case letter or a numeric digit. Following are the basic kinds of constants in IBM Prolog:

An atom is any sequence of characters enclosed in double quotes, such as "July 14, 1989" or "apple". For atoms that start with a lowercase letter and contain only letters and digits (no blanks or punctuation), the double quotes may be omitted: "apple" and apple are two identical atoms.
A character string is any sequence of characters enclosed in single quotes, such as 'July 14, 1989' or 'apple'. The single quotes can never be omitted.
Numbers may be either integers like 3796, floating point numbers like 3.14159 and 7.59e-10, or rational numbers like 22/7. For integers and rational numbers, the only limit on size is the amount of available storage; the system will keep allocating storage up to a limit of 16 megabytes per number. Rational numbers are written without blanks around the slash. With blanks, 3 / 4 is treated as 3 divided by 4. All three kinds of numbers may be intermixed in computable expressions, such as (3/4 + 2 + 1.9e-4) &asterisk; 5, which could be evaluated to produce 13.75095.

Atoms and character strings differ in the way they may be processed. Atoms are stored in a compact way that saves space, but there are no predicates that operate on their internal structure. Character strings take more storage space, but they can be processed by various string-handling predicates. A string '6xyz' can be converted to an atom A by the built-in predicate st_to_at('6xyz',A); this is a reversible predicate that can also be used to convert an atom "6xyz" to a string S as in st_to_at(S,"6xyz").

Besides variables like X or T1 that begin with an uppercase letter, Prolog also supports anonymous variables represented by just an asterisk &asterisk;. The asterisk is truly variable because it can have a different value every time it appears. For example, p(&asterisk;,&asterisk;) permits any values to occur in the two different argument places, such as p(3,99) or p(socrates,7); but p(X,X) requires that both arguments be the same, such as p(3,3) or p(socrates,socrates). An anonymous variable may be used anywhere that a named variable can occur; but each time it occurs, its previous value is ignored. For that reason, the asterisk is sometimes called a don't-care symbol because it shows that the value is not needed in future references.

Predicates may be defined in two ways: by a complete list of all the facts in which they occur; or by general rules that determine their truth or falsity. As an example, all family relationships are determined by lists of facts for three basic predicates: child(C,P) means that C is a child of P; male(M) means that M is male; female(F) means that F is female; and married(X,Y) means that X is married to Y. Following are examples of facts for the child predicate:

child(oidipous,iokaste).
child(oidipous,laios).
child(antigone,iokaste).
child(antigone,oidipous).
child(eteokles,iokaste).
child(eteokles,oidipous).
child(polyneikes,iokaste).
child(polyneikes,oidipous).

Following are some facts that define the male and female predicates:

male(laios).       male(oidipous).
male(eteokles).    male(polyneikes).
female(iokaste).   female(antigone).

The married predicate is symmetric: if X is married to Y, then Y is married to X. Therefore two facts must be stated for each marriage; one for each ordering of the arguments.

married(laios,iokaste).
married(iokaste,laios).
married(oidipous,iokaste).
married(iokaste,oidipous).

With these four predicates defined by lists of facts, all other family relations can be defined by rules. The easiest to define is parent, which is the inverse of child:

parent(P,C) <- child(C,P).

In this rule, which is an example of a conditional, the arrow <- may be read as the English word if. Translated into English, the rule says that &P is a parent of &C if C is a child of P. Unlike standard logic, which has implications pointing to the right, the conclusion in Prolog is written on the left. This way of writing Prolog rules makes it easier for a person to find the rules that define a predicate: when a predicate appears on the right side (the body of a rule), it is being used or called; but when it appears on the left side (the head of a rule), it is being defined. By scanning down the left margin of a listing, the Prolog programmer can quickly find all the rules that define a given predicate.

The predicates father and mother require a conjunction of two conditions: M is the mother of C if C is a child of M and &M is female. Likewise, F is the father of C if C is a child of F and F is male.

mother(M,C) <- child(C,M) & female(M).
father(F,C) <- child(C,F) & male(F).

The symbol & is the Boolean operator for conjunction; it may be read as the English word and. The reader should practice translating these rules into English sentences: the term mother(M,C) is read as "M is a mother of C"; the arrow is read "if"; and the & symbol is read "and." In the first rule above, C occurs twice. If C has a value at one place in a rule, then it must have exactly the same value at every other place. The scope of a variable in Prolog is limited to the rule in which it occurs; variables with the same name in different rules are treated as different variables. Therefore, the variable C in the first rule has no effect on the variable C in the second rule.

The next more complicated predicate is sibling: X is a sibling of Y if X is a child of some P, Y is a child of the same P, and X and Y are not the same person.

sibling(X,Y) <- child(X,P) & child(Y,P) & ^(X=Y).

The symbol = represents an operator that tests for equality, and the operator ^ represents negation. Both of the operators = and ^ have further properties that will be discussed in more detail later.

Rules may be defined in terms of predicates that are themselves defined by rules. The predicates sister and brother, for example, can be defined in terms of sibling:

sister(S,X) <- sibling(S,X) & female(S).
brother(B,X) <- sibling(B,X) & male(B).

A recursive rule is one that defines a predicate in terms of itself. An example is descendant: D is a descendant of A if either &D is a child of A or D is a child of a person P who is a descendant of A.

descendant(D,A) <- child(D,A)
                 | child(D,P) & descendant(P,A).

This rule introduces the symbol | for the Boolean disjunction or or operator. The & operator has higher precedence (tighter binding) than the | operator.

Strictly speaking, the | operator is not needed in Prolog, since every use of | can be eliminated by writing extra rules. The predicate descendant, for example, can be defined by two separate rules. The first says that D is a descendant of A if D is a child of A; the second says that D is a descendant of A if D is a child of P and P is a descendant of A:

descendant(D,A) <- child(D,A).
descendant(D,A) <- child(D,P) & descendant(P,A).

Both of these ways of defining descendant are about equally readable and equally efficient. There is not much reason for choosing one or the other. In some cases, however, the | operator can improve efficiency. Consider the definition of uncle. U is an uncle of N under either of the following two conditions:

By blood, N is a child of P, who is a sibling of U, and U is male;
By marriage, N is a child of P, who is a sibling of a person Q, who is married to U, and U is male.

That pair of conditions can be mapped into two Prolog rules:

uncle(U,N) <- child(N,P) & sibling(P,U) & male(U).
uncle(U,N) <- child(N,P) & sibling(P,Q) &
    married(Q,U) & male(U).

Since both of these rules have similar beginnings and endings, the | operator could be used to combine them in a single rule with the common parts factored out:

uncle(U,N) <- child(N,P)
    & (sibling(P,U) | sibling(P,Q) & married(Q,U))
    & male(U).

One further simplification is possible. The expression sibling(P,U) may be replaced by the equivalent expression sibling(P,Q) & Q=U. After making that substitution, the two occurrences of sibling(P,Q) could also be factored out:

uncle(U,N) <- child(N,P) & sibling(P,Q)
    & (Q=U | married(Q,U)) & male(U).

To understand this rule, read it as an English sentence: U is an uncle of N if N is a child of P, and P is a sibling of Q, and either Q is the same as U or Q is married to U, and U is male. Parentheses are needed around the phrase (Q=U | married(Q,U)) since | does not bind as tightly as &. This phrase in the factored form of the rule illustrates an interesting property of family trees: two people who are married to each other have equal status in defining relationships like aunt and uncle. This property holds for the English kinship terms, but it is not true of the kinship terms in many other languages and cultures.

Symmetric predicates like married must be defined by two facts for each pair of arguments. It is tempting to simplify the definition by asserting only one fact for each pair. Then the following rule might be used to handle the other case:

married(X,Y) <- married(Y,X).

This rule says that X is married to Y if Y is married to X. Unfortunately, this rule represents the most dangerous case of recursion: the predicate calls itself recursively without making a change to any of its arguments. If this rule is ever invoked, it could cause a recursive loop that would only stop if the system ran out of storage. The definition of descendant also used a recursive rule, but it used recursion more safely:

descendant(D,A) <- child(D,P) & descendant(P,A).

Before this rule calls itself recursively, it calls the child predicate to find the parent P of D. Therefore, each time descendant is called, its first argument has a person who is higher up in the tree. If there are no loops in the tree, it will eventually find the desired ancestor, or it will stop with some individual whose parents are unknown.

A good way to ensure that a predicate is symmetric is to define it in terms of some other asymmetric predicate. Consider the following rules and facts:

wife(iokaste,laios).
wife(iokaste,oidipous).
husband(X,Y) <- wife(Y,X).
married(X,Y) <- wife(X,Y) | wife(Y,X).

With these definitions, wife is considered a primitive predicate defined by a list of facts, and husband is defined as the inverse of wife. Then X is married to Y if either X is the wife of Y or Y is the wife of X. The husband predicate could equally well have been used as the primitive with wife and married defined in terms of husband.

All of the rules discussed so far are conditionals. Unconditional rules look like facts, but they contain variables. For example, a predicate related(X,Y) might indicate that X is related to Y. Since every person is related to himself or herself, the following unconditional rule would say so:

related(X,X).

In list processing, which will be discussed later in this chapter, there is a special list nil, called the empty list. One might define a predicate sublist(L1,L2), which would be true if the list L1 happened to be a sublist of the list L2. Then the following unconditional rule would state that nil is a sublist of every list (including itself):

sublist(nil,L).

Another predicate used in list processing is append(L1,L2,L3), which appends list L2 to the end of list L1 to form a new list L3. The following unconditional rule says that the result of appending nil to any list L is L unchanged:

append(nil,L,L).

The predicates for list processing are often defined by two rules: the first rule is an unconditional rule that states what happens to the empty list nil; and the second rule is a recursive rule that handles the general case of a nonempty list.

Goals and Backtracking

Facts and rules reside in a Prolog workspace, but no action takes place until a goal is entered. A simple goal looks like a fact or an unconditional rule. The difference lies in its use. For example, human(socrates) could be added to the workspace as a fact. But it could also be entered as a goal to ask the question "Is Socrates human?" In IBM Prolog, the default syntax requires goals to be preceded by the symbol <-. Therefore, the goal could be entered by typing <-human(socrates). Since facts are more commonly entered from a file and goals are more commonly typed at the keyboard, it is often convenient to omit the initial arrow for goals. Such conventions are determined by pragmas, which are special global variables that govern the default syntax and keyboard conventions. Appendix A discusses the pragmas, including <- pragma(allgoal,1), which allows the initial arrow to be omitted for goals.

Goals may also contain variables. The goal human(X) asks the system to find some human and bind its value to the variable X. Suppose the following facts had been asserted:

human(socrates).  human(cicero).  human(voltaire).
greek(socrates).  roman(cicero).  french(voltaire).

When the goal human(X) is entered, the system looks for the first fact that matches the goal, in this case human(socrates), and binds the value socrates to the variable X. The other possible values cicero and voltaire are ignored at first. Binding is similar to assignment in other programming languages: it causes a variable like X to acquire a value like socrates. Yet binding is not as permanent as assignment. It is possible to force Prolog to undo the binding by backtracking to find another value for X. For this example, if the user at the keyboard types the goal <-human(X), the response is human(socrates). To force backtracking, the user could then type a semicolon ; which would cause the system to redo the previous goal and find another binding for X. The second response would be human(cicero). Another semicolon would force the system to backtrack and generate the third response human(voltaire). One more semicolon would force another backtrack, but no more options would be left. Therefore, Prolog would report failure.

The semicolon is an operator that allows the user at the keyboard to force backtracking. But backtracking also occurs when any goal or subgoal happens to fail. Consider the compound goal (human(X) & roman(X)). This goal has two subgoals: human(X) and roman(X). To process the compound goal, the Prolog system takes the first subgoal human(X), finds some value for X, and then processes the second subgoal roman(X) with the new value of X. As before, the first value found for X is socrates. It then tries to match the second goal roman(socrates) to some fact in the workspace, but no fact matches. Therefore, the system backtracks to the first goal human(X). It unbinds the old value of X and binds the next value cicero. With this new value, the goal roman(cicero) matches one of the facts. Then both halves of the compound goal succeed, and the final value of X is cicero. Backtracking sounds complicated, but the Prolog system makes it efficient by keeping a stack of choice points. Whenever it finds a list of alternatives, it always takes the first one and puts a pointer to the next one on its stack of choice points. When a failure occurs, it takes the most recent choice point and continues from there. Since the stacks are optimized for fast retrieval of choice points, Prolog is an efficient language for processing alternatives with complex interactions.

The goal human(socrates) was used to verify the fact that Socrates is human. The goal human(X), however, was used to find some X that is human. These are examples of a verifier goal and a finder goal. There is one other kind of goal: a doer goal performs some operation that has a side effect; an example is write(X), which prints the current value of X on the screen. Following is a summary of these three kinds of goals:

Verifier goals ask whether a certain predicate is true.
Finder goals ask for values to be bound to one or more variables.
Doer goals ask the system to perform some operation.

A verifier is like a yes&endash;no question that asks whether a particular relationship is true or false. Verifiers have no unbound variables: child(sam,mary) asks whether Sam is a child of Mary; it succeeds if true and fails if false. A finder is like a who or what question in English. It asks the system to find a value for one or more unbound variables. The goal child(X,mary) asks who is a child of Mary; the answer is bound to the variable X. A doer goal is not used to ask a question, but to cause some side effect. It may invoke subgoals that are finders or verifiers, but it also invokes subgoals that may change the workspace or perform some input/output. Since doers have side effects, they are not part of pure Prolog.

To determine whether a goal is a finder or a verifier, the values of the variables at the moment the goal is invoked must be considered. For example, the goal (human(X) & roman(X)) has two subgoals, each with a single variable X. The first subgoal to be issued is human(X); this is a finder goal that seeks a value for X. Once X has been bound to a value, such as socrates, the next subgoal is issued as the verifier goal roman(socrates). Verifier goals cannot change a value of a variable. Instead, they may cause a failure to occur that causes Prolog to backtrack to a previous finder goal to seek a different value. In this case, the finder goal human(X) is issued once more to find the value cicero.

In pure Prolog, the order in which subgoals are issued has no effect on the final answer. The goal (roman(X) & human(X)) would find the same answer X=cicero. In this order, roman(X) is the finder goal, and human(X) is the verifier. Although the same answer is computed, this goal executes slightly faster, since the finder roman(X) finds the correct answer on the first try, and no backtracking is necessary. But before considering performance, the main concern is to write rules that are logically correct. The last section of this chapter discusses methods of reordering rules to improve performance.

Prolog Structures

Facts, goals, and rules are special cases of Prolog clauses. The most general clause is a statement of the form, .sk p8 .ce on head <- body. .ce off .sk p8 The head must be a single predication (a predicate symbol followed by a list of arguments). The body may be either one predication or a combination of predications separated by & for and and | for or. The negation symbol ^ may also be placed in the body of a clause. Either the head or the body of a clause may be missing. A clause with no head is a goal; a clause with no body is called a unit clause, since it only has one predication. A conditional rule has both a head and a body. Unit clauses are either facts or unconditional rules.

Prolog is a relational programming language, unlike Lisp, which is a functional programming language. In Lisp, as in most languages, functions take input values and compute results. In Prolog, however, only predicates (also known as relations) compute results. To see the difference, consider the Fortran .hw arith-me-tic statement X=A+B, which In Lisp, would be written,

(SETF X (+ A B))

In Lisp, Fortran, and most other programming languages, the operator + represents a function that takes the values of &A and &B as input and computes a result that is bound to the variable X. In Prolog, however, the goal X=A+B does not specify a numeric computation. Instead, the expression is represented as a little tree with + at the top and with the values of A and B as two branches hanging down from it. Then the = operator causes that tree structure to be bound to X.

Since Prolog expressions are not normally evaluated, a special operator is needed to force evaluation. In IBM Prolog, the evaluation operator is represented by the ? symbol. Consider the following two Prolog goals:

A = 5  &  B = 3  &  X = A + B.
A = 5  &  B = 3  &  X = ? A + B.

For the first goal, X has the unevaluated expression 5 + 3 as its value. For the second goal, the ? operator causes the expression to be evaluated to a single number 8, which is then bound to the variable X. In Lisp, the default is to evaluate expressions automatically, unless a quote is used to block evaluation. Prolog, however, leaves the expressions unevaluated unless the ? operator is used to evaluate them. Note: the ? operator has lower precedence than + , therefore ?A+B is equivalent to ?(A+B). To evaluate an expression and bind its value to a variable, IBM Prolog uses =? and some implementations use the notations := or is. For compatibility, IBM Prolog supports both := and is as synonyms for =?, but to use is one must switch IBM Prolog to the Edinburgh syntax — see page &caedin;.

Using function symbols to build trees is the normal way to represent complex data structures in Prolog. Functions are treated as undefined symbols that are carried around inside the arguments of predicates, unless they are explicitly evaluated by the ? operator. A term is a function symbol called an identifier followed by a list of arguments:

human(socrates)   f(g(Abc,2),100)   "+"(5,"+"(3,4))

The arguments may be constants, variables, or other functions applied to their arguments. Functions applied to arguments form trees, which may themselves consist of functions applied to other arguments. The term

s(np(cats),vp(v(like),np(mice)))

represents the tree

                          s
                        /   \
                       /     \
                      np     vp
                      |     /  \
                    cats   v    np
                           |    |
                         like  mice

Trees like this can represent the parsed form of an English sentence. Other trees can represent the records in programming languages like Pascal. Following is a definition for a Pascal record of type person:

type person = record
                name: string;
                address: string;
                date_of_birth: array[1..3] of integer;
                sex: boolean
              end

The person record has four subfields: name, address, date_of_birth, and sex, each represented by a separate variable. In Prolog, the equivalent data would be stored as a tree constructed from functions and their arguments. To emphasize the similarity with the Pascal record, the arguments may be written on separate lines:

person(Name,
       Address,
       Date_of_birth,
       Sex)

One difference between the Prolog functional form and the Pascal record is that Pascal requires every variable to have an explicit type declaration. The Prolog form simply lists the variables without specifying their types. In IBM Prolog, there are certain optional declarations; they may be included for better optimization in the compiled code, but they may be omitted for greater flexibility or ease of programming. Compiler considerations will be discussed further in Chapter 3 and Appendix A.

In the default notation, the function identifier is written first, followed by the arguments in parentheses. But Prolog also supports infix notation like A+B, suffix notation like N!, and prefix notation like -X, where the parentheses may be omitted. A function or predicate that is written in one of these forms is called an operator, but its effect is exactly the same as the default form. In fact, the internal representations of A+B+C and "+"("+"(A,B),C) are identical. One of the most important infix operators in Prolog is the dot operator, which is used to construct lists like Date.Month.Year.nil. This operator will be used extensively in the later sections on list processing.

Built-in Predicates

In pure Prolog, every predicate is defined by a list of rules and facts. In principle, pure Prolog is rich enough to define all computable functions without any built-in predicates at all. But in practice, built-in predicates are needed for three purposes: improved performance for arithmetic and string handling; ease of programming for certain kinds of operations; and access to external facilities, such as input/output services and the operating system.

In the family database, the primitive predicates are defined by collections of facts. Predicates with numeric values could also be defined by collections of facts, but it is more common to state a general rule that computes numeric values upon request. Consider the predicate fac(N,X), whose second argument X is the factorial of the first argument N. It could be defined by the following collection:

fac(0,1).          fac(1,1).
fac(2,2).          fac(3,6).
fac(4,24).         fac(5,120).
fac(6,720).        fac(7,5040).
fac(8,40320).      fac(9,362880).

This collection only defines fac for the inputs 0 to 9; it is undefined for all other inputs. A more complete way of defining it is to state one fact that gives the value of fac for input 0 and then to give a recursive rule that computes the result for all inputs greater than 0:

fac(0,1).
fac(N,X) <- fac(? N - 1, Y) & X := N &asterisk; Y.

The recursive rule states that the factorial of N is X if the factorial of N - 1 is Y and the product of N and Y is X. This rule uses the evaluation operators ? to compute N - 1 and := to compute N &asterisk; Y. For the goal <-fac(1,Z), the first fact would not match, and the recursive rule would be called. It would first evaluate 1 - 1 and issue the subgoal fac(0,Y). This subgoal would match fac(0,1) to make Y=1. Finally, it would compute N &asterisk; Y to produce 1, which is the value returned for X. Since IBM Prolog allows integers to grow arbitrarily long, it can evaluate a goal like fac(1200,X), where X would be an integer over 3,000 digits long.

The only built-in predicates used in this example so far are := and the evaluation operator ? for computable expressions. More built-in predicates can be used in testing for error conditions. If the first argument happened to be negative, the recursive rule would keep calling itself indefinitely. Eventually, the system would run out of space and print an error message, STACK OVERFLOW. To avoid that error, an extra rule may be inserted to trap negative inputs:

fac(0,1).
fac(N,X) <- lt(N,0) &
    write('Negative input to factorial').
fac(N,X) <- fac(? N - 1, Y) & X := N &asterisk; Y.

As before, the fact fac(0,1) matches goals where the first argument is 0. The second rule matches all other goals and uses the built-in predicate lt(N,0) to test whether N is less than 0. In the normal case, N is greater than 0; therefore, the second rule fails, and the third rule is invoked to compute fac recursively. If N happens to be less than 0, the second rule calls another built-in predicate write to print out the message "Negative input to factorial." After the call to write, the rule is finished, and the third rule is never invoked.

Instead of printing an error message when an input value is out of range, most Prolog predicates simply fail. Then the calling rule can decide what to do about the failure. The next definition of fac succeeds for nonnegative integers and fails for negative integers:

fac(0,1).
fac(N,X) <- lt(N,0) & / & fail.
fac(N,X) <- fac(? N - 1, Y) & X := N &asterisk; Y.

The second rule in this definition uses two more built-in predicates: the cut operator / and the fail predicate. If the test lt(N,0) succeeds, the cut operator throws away the choice point that leads to the third rule (the recursive one). Then the fail predicate forces an immediate failure. Since the cut had already thrown away the choice point, there is no pointer leading to the third rule. Therefore, there is no alternative left, and the fac predicate returns with failure. The cut operator is one of the nonlogical features of Prolog that disrupts the purely declarative style. It is often useful for handling error conditions, as in this example, but it is like the GO-TO in procedural languages: normally avoided, but valuable in emergencies.

Besides computational predicates for arithmetic and string handling, Prolog also has a set of nonlogical predicates. Unlike the computational predicates, which might be defined by logical rules, the nonlogical predicates perform services that cannot easily be specified in pure logic. There are three basic kinds of nonlogical predicates:

Execution control predicates change the way Prolog executes rules. The most common of these is the cut operator.
Workspace predicates change the Prolog workspace itself. They may add and delete rules and facts, turn on tracing and debugging, or reset certain global parameters.
System predicates interact with the operating system to do input and output or to execute some external system command.

Whereas predicates defined by pure Prolog can never change anything but data passed as arguments, the nonlogical predicates have side effects: they can change hidden data or structures that are not specified in the arguments. In the case of input/output, the side effects may occur on paper or display screens that are far removed from the computer itself.

The Inference Engine

Logic was designed for stating timeless truths. It is purely declarative, and has no procedural facilities at all. Prolog, however, makes logic executable: declaratively, predicates are either true or false; procedurally, goals either succeed or fail. The procedural effect results from the combination of logic with a special program called an inference engine. This program provides the sequencing that causes rules and facts to be invoked when needed. As an example, consider the following rule and fact:

mortal(X) <- human(X).
human(socrates).

Declaratively, the rule says that X is mortal if X is human; the fact states that Socrates is human. To show the procedural effect, suppose that Prolog were given the goal mortal(Z). This goal is matched to the left side of the rule, causing the two variables X and Z to be bound to each other. The system then issues the body of the rule, human(X), as a subgoal to be satisfied. This goal matches the fact human(socrates). Therefore the goal is satisfied by binding the value socrates to the variable X. Since the variables Z and X are cross-bound to each other, Z is also bound to the value socrates. Prolog finally responds to the original goal by typing the output,

<- mortal(socrates).

The Prolog inference engine has two basic procedures: a goal processor and a rule processor. In an interpreter, there will be actual code that performs each of these functions. A highly optimized compiler, however, may take shortcuts so that the two tasks are inextricably intertwined. But to simplify the discussion, assume an interpreted version of Prolog. A compiled version will have the same effect, even if it simplifies or eliminates some of the intermediate steps.

The goal processor and the rule processor call each other recursively: in executing a goal, the goal processor must invoke rules; in executing a rule, the rule processor issues the body of the rule as a new subgoal. Both processors use a pushdown stack of choice points to which backtracking returns in case of a failure. Whenever the goal processor reports a failure, the calling program (which could be either the goal processor or the rule processor) takes the most recent choice point from the stack and resumes execution. If a failure occurs when no choice points are left, the failure is reported to the user sitting at the screen. The stack of choice points is saved even when the original goal succeeds. If the user types a semicolon, the Prolog inference engine resumes execution from the most recent choice point.

The goal processor is the first to be invoked when the user enters a new goal. If the goal is a simple one like mortal(socrates), it immediately calls the rule processor to find some rule with a matching head. But in searching a database for Greek goddesses, the user might type a complex goal like (greek(X) & female(X) & ^mortal(X)). Before calling the rule processor, the goal processor must break down such complex goals into simple ones, each with a single predicate. Let G be the current goal:

If G is a conjunction (P & Q), first process P; if P succeeds, then process Q. If Q fails, check whether P left any choice points on the backtracking stack. If so, backtrack to the last choice point left by P. G succeeds only if both subgoals succeed (possibly after some backtracking from Q back to P).
If G is a disjunction (P | Q), first process P and place a choice point on the backtracking stack that points to Q. If P succeeds, then G succeeds, and Q is left as a choice point that might be tried later if something else happens to fail. If P fails, then Q is removed from the backtracking stack and processed. G succeeds if either P or Q succeeds.
If G is a negation ^P, then P is issued as the next subgoal. If P succeeds, G fails. If P fails, G succeeds.
If G is a simple goal, then call the rule processor to handle it. If the rule processor reports success, then G succeeds; otherwise, G fails.

The goal processor may call itself recursively many times when processing a complex goal. For the goal of finding Greek goddesses, it processes the first subgoal greek(X) and returns with some value for X, such as socrates. Then it issues the next subgoal female(socrates). Since this subgoal fails, the processor backtracks to greek(X) to find another value for X. If it returns with X=hera, the next subgoal female(hera) is processed. Since that succeeds, it next tries ^mortal(hera). To process the negation, the goal processor calls itself recursively to process mortal(hera). Since this subgoal fails, the negation succeeds. Finally all of the conjuncts have succeeded, and the goal processor returns successfully with X=hera. Now if the user at the keyboard types a semicolon, the inference engine resumes execution from the most recent choice point to find another Greek female immortal.

The rule processor is called from the goal processor, but it may in turn call the goal processor. It is invoked with a simple goal such as mortal(X). It then searches the list of rules and facts to find one with a matching head. Let G be the current goal with a predicate named N.

Match G to the head of each rule for N until one is found whose head matches. If no match is found, return with failure. If a match is found, place a pointer to the remaining list for N on the backtracking stack and continue processing the rule that matched.
If the matching rule is an unconditional rule or fact, there is no body to execute. Therefore the rule processor can immediately return with success.
If the matching rule is conditional, call the goal processor to execute the body (right hand side) of the rule. If the goal processor returns with success; then return with success for G. If the goal processor fails on the current rule, then take the list of remaining rules for N from the backtracking stack and continue searching for another one that matches G.
When all rules for N have been tried without success, return with failure.

In short, rules are tried in the order in which they are entered (typed or read into a workspace). The body of a rule is executed just as if it had been a goal typed at the keyboard. When the current rule fails, the rule processor abandons it and tries the next rule with the same predicate name.

Last Modified: