Prolog: Symbolic Programming or Programation Logique

Facts

We first discuss facts about objects. Suppose we want to tell Prolog the fact that John likes Mary. This fact consists of two objects, called Mary and John, and a relationship or predicate, called likes. In Prolog, we need to write facts in a standard form, like this:

likes(john, mary).

The following things are important:

• The names of all relationships and objects must begin with a lower-case letter. For example, likes, john, mary.
• The relationship is written first, and the objects are written separated by commas and enclosed in round brackets.
• The dot character . must come at the end of a fact. The dot is what some people also call a period or a full stop.

Questions

Once we have some facts, we can ask some questions about them. In Prolog, a question looks just like a fact, except that we put a special symbol before it. The special symbol is written as a question mark followed by a hyphen. Consider the question:

?- owns(mary, book).

If we interpret mary to be a person called Mary, and book to be some particular book, this question is asking Does Mary own the book?, or Is it a fact that Mary owns the book? We are not asking whether she owns all books, or books in general, because the first letter of book is lower case.

When a question is asked of a Prolog system, it will search through the database. It looks for facts that unify the fact in the question. Two facts unify if their predicates are the same (spelled the same way), and if their corresponding arguments each are the same. If Prolog finds a fact that unifies with the question, Prolog will respond yes. If no such fact exists in the database, Prolog will respond no.

Rules

In Prolog, rules are used when you want to say that a fact depends on a group of other facts. Rules are also used to express definitions. A rule is a general statement about objects and their relationships. For example, we can say that Fred is a bird if Fred is an animal and Fred has feathers, and we can also say that Bertram is a bird if Bertram is an animal and Bertram has feathers. So, we can allow a variable to stand for a different object in each different use of the rule.

In Prolog, a rule consists of a head and a body. The head and body are connected by the symbol :-, which is made up of a colon and a hyphen. The :- is pronounced if.

That John likes whoever likes wine is written in Prolog as:

likes(john, X) :- likes(X, wine).

Notice that rules also end with a dot (actually a period or full stop character). The head of this rule is likes(john, X). The head of the rule describes what fact the rule is intended to define. The body, in this case likes(X, wine), describes the conjunction of goals that must be satisfied, one after the other, for the head to be true. For example, we can make John more choosy about whom he likes, simply by adding more goals onto the body, separated by commas:

likes(john, X) :- likes(X, wine), likes(X, food).

or, in words, John likes anyone who likes wine and food. Or, suppose John likes any female who likes wine:

likes(john, X) :- female(X), likes(X, wine).

And so on.

Input, Output, and Input-Output Arguments to Predicates in Prolog

An argument may be either of them three and change its role according to the situation, for there is nothing in the syntax of prolog to indicate which.

Functors or Structures

A structure is written in Prolog by specifying its functor and its components. The functor names the general kind of structure, and corresponds to a datatype in an ordinary programming language. The components are enclosed in round brackets and separated by commas. The functor is written just before the opening round bracket. Consider the following fact, that John owns the book called Wuthering Heights, by Emily Bronte:

owns(john, book(wuthering_heights, bronte)).

Inside the owns fact we have a structure by the name of book, which has two components, a title and an author. Since the book structure appears inside the fact as one of the fact's arguments, it is acting as an object, taking part in a relationship. If we like, we can also have another structure for the author's name, because there were three Bronte writers we wish to distinguish:

owns(john, book(wuthering_heights, author(emily, bronte))).

Structures may participate in the process of question-answering using variables. For example, we may ask if John owns any book by any of the Bronte sisters:

?- owns(john, book(X, author(Y, bronte))).

And so on.

If you have guessed that the syntax for structures is the same as for Prolog facts, you are correct. A predicate (used in facts and rules) is actually the functor of a structure. The arguments of a fact or rule are actually the components of a structure. There are many advantages to representing Prolog programs themselves as structures. It is not important to know why just now, but do keep in mind that all parts of Prolog, even Prolog programs themselves, are made up of constants, variables, and structures.

Horn Clauses

In mathematical logic and logic programming, a Horn clause is a logical formula of a particular rule-like form which gives it useful properties for use in logic programming, formal specification, and model theory. Horn clauses are named for the logician Alfred Horn, who first pointed out their significance in 1951.

The Wikipedia

In logic programming, a Horn clause is an implication from a conjunction of none, one or several goals.

Jess will come if it is sunny AND her car starts, AND her mother is not ill.

This might be coded in prolog like this:

come(jess) :- sunny, start(car(jess)), not ill(mother(jess)).

A Simple Database of Prolog Facts and Rules

This is a simple database to establish if two people are friends:

friends(X,Y) :- likes(X,Z), likes(Y,Z).
likes(john,gin).
likes(peter,gin).
likes(andy,beer).

% database:
has_met(a,b).
has_met(a,c).
% rules:
has_met(X,Y) :- has_met(Y,X).

% forward 'has_met' data base:
has_met_fwd(a,b).
has_met_fwd(a,c).
has_met(X,Y) :- has_met_fwd(X,Y) ; has_met_fwd(Y,X).

% forward 'has_met' data base:
has_met_fwd(a,b).
has_met_fwd(a,c).
% rules:
has_met(X,Y) :- has_met_fwd(X,Y).
has_met(X,Y) :- has_met_fwd(Y,X).

| ?- has_met(X,a).
X = b ? ;
X = c
yes

% database:
tr(a,b).
tr(b,c).
tr(c,d).
tr(bb,c).
tr(d,e).
tr(e,f).
% rules:
transitive(X,Y) :-           tr(X,Y).
transitive(X,Z) :-           tr(X,Y), transitive(Y,Z).

| ?- transitive(X,f).
X = e ? ;
X = a ? ;
X = b ? ;
X = c ? ;
X = bb ? ;
X = d ? ;
no

            
...
            
            
...
            
            
...
          

Lists in Prolog

Writing a list to standard output is a nice exercise for understanding both lists and recursive control:

writelist([]).
writelist([H|T]) :- write(H),nl,writelist(T).

member(X,[X|_]).
member(X,[_|T] :- member(X,T).

append([], X, X).
append([A|B], C, [A|D]) :- append(B, C, D).

| ?- append(X,Y,[a,b,c]).
X = []
Y = [a,b,c] ? ;
X = [a]
Y = [b,c] ? a % here the user presses a to compute all remaining solutions
X = [a,b]
Y = [c]
X = [a,b,c]
Y = []
no

The Use of Cut to Prevent Backtracking in Prolog

Sometimes it is desirable to selectively turn off backtracking. Prolog provides a predicate that performs this function. It is called the cut, represented by an exclamation mark (!).

The cut effectively tells Prolog to freeze all the decisions after it occurs in a predicate. That is, if required to backtrack, Prolog will automatically fail without trying other alternatives.

The following database and query seems to fail:

related(X,Y) :- related(X,Z), related(Z,Y).
related(phil, roxanne).
related(roxanne, carol).
related(carol, alex).

Followed by the query:

related(phil,carol).

Performance is the main reason to use the cut. This separates the logical purists from the pragmatists. Various arguments can also be made as to its effect on code readability and maintainability. It is often called the goto of logic programming.

You will most often use the cut when you know that at a certain point in a given predicate, Prolog has either found the only answer, or if it hasn't, then there is no answer. In this case you insert a cut in the predicate at that point.

Similarly, you will use it when you want to force a predicate to fail in a certain situation, and you don't want it to look any further.

Some Examples of the Use of Cuts

The following program defines the minimum predicate with cuts:

minimum(X, Y, X) :- X =< Y, !.
minimum(X,Y,Y) :- X > Y, !.

...

repeat

The built-in predicate repeat is provided as an extra way to generate multiple solutions through backtracking. Although it is built-in, it can be thought of as behaving as though defined as follows:

repeat.
repeat :- repeat.

What is the effect of this if we put repeat as a goal in one of our rules? First of all, the goal will succeed, because of the fact which is the first clause of repeat. Secondly, if backtracking reaches this point again, Prolog will be able to try an alternative: the rule that is provided as the second clause of repeat. When it uses this rule, another goal repeat is generated. Since this matches the first fact, we have succeeded again. If backtracking reaches here again, Prolog will again use the rule where it used the fact before. To satisfy the extra goal generated, it will again pick the fact as the first option. And so on. In fact, the goal repeat will be able to succeed infinitely many times on backtracking. Note the importance of the order of the clauses here. (What would happen if the fact appeared after the rule?).

Why is it useful to generate goals that will always succeed again on backtracking? The reason is that they allow one to build — from rules that have no choices in them — rules that do have choices. And we can make them generate different values each time.

Loops with repeat/0

Furthermore, a clause body with a repeat/O followed by fail/O will go back and forth forever. This is one way to write an endless loop in Prolog.

A repeat/O followed by some intermediate goals followed by a test condition will loop until the test condition is satisfied. It is equivalent to a do until in other languages.

command_loop :-
  repeat,
  write('Enter command (end to exit): '),
  read(X),
  write(X), nl,
  X = end.

Forcing Evaluation with Operator is

An important difference between unification-based computing and the use of more traditional languages is that unification performs syntactic matches (with appropriate parameter substitution) on structures. It does not evaluate expressions.

Prolog provides an operator, is, that performs arithmetic evaluation. It evaluates the expression on its right-hand side and attempts to unify the result with the object on its left. Thus,

X is Y + Z

unifies X with the value of Y added to Z. Because it performs arythmetic evaluation:

• If Y and Z do not have values (are not bound at execution time) evaluation of the is causes a run-time error. Therefore
• X is Y + Z cannot (as one might think with a declarative programming language) assign a value to Y when X and Z are bound.
• Programs must use is to evaluate expressions containing arithmetic operators, +, -, *, /, and mod.

Finally, as in the predicate calculus, variables in prolog may have one and only one binding. Once given a value, through local assignment or unification, they can never take on a new value, except through a backtrack in the and/or search space of the current interpretation. Thus, is does not function like a traditional assignment operator; an expression such as X is X + 1 will always fail.

Equality and Unification

There really is no equivalent of the assignment in prolog, and you should not use the dynamic database for this purpose.

One noteworthy built-in predicate is equality, which is an infix operator written as =. When an attempt is made to satisfy the goal

?- X = Y.

(pronounced X equals Y), Prolog attempts to unify X and Y, and the goal succeeds if they unify. We can think of this act as trying to make X and Y equal. The equality predicate works as though it were defined by the following fact:

X = X.

?- X == Y.
no
?- X == X.
X = _23
?- X=Y, X==Y.
X = _23, Y = _23
?- append([A|B], C) == append(X, Y).
no
?- append([A|B], C) == append([A|B], C).
A = _23, B = _24, C = _25

Arithmetic in Prolog

Arithmetic can be used for calculating. For example, if we know the population and ground area of a country, we can calculate the population density of the country. The population density tells us how crowded the country would be if all the people were evenly spread throughout the country. Consider the following database about the population and area of various countries in 1976. We will use the predicate population to represent the relationship between a country and its population. Nowadays, the populations of countries are generally quite large numbers. So, we will represent population figures in millions: population(X, Y) means the population of country X is about Y million people. The predicate area will denote the relationship between a country and its area (in millions of square miles). The numbers given here are not exact, but they will do for the purpose of demonstrating arithmetic:

population(usa, 203).
population(india, 548).
population(china, 800).
population(brazil, 108).
area(usa, 3).
area(india, 1).
area(china, 4).
area(brazil, 3).

Now to find the population density of a country, we must use the rule that the density is the population divided by the area. This can be represented as the predicate density, where the goal density(X,Y) succeeds for country X having Y as the population density of that country. A Prolog rule for this is:

density(C, Y) :-
  population(C, P),
  area(C, A),
  Y is P / A.

We need to use built-in infix predicator is to cause evaluation and then unification.

Standard Arithmetic Operators in Prolog

Depending on what computer you use, various arithmetic operators can be used

• X + Y: the sum of X and Y
• X - Y: the difference of X and Y
• X * Y: the product of X and Y
• X / Y: the quotient of X divided by Y
• X // Y: the integer quotient of X divided by Y
• X mod Y: the remainder of X divided by Y

Numerical Comparison Operators in Prolog

Given two numbers, we can tell whether one number is equal to the other, or less than the other, or greater than the other. Prolog provides certain built-in predicates for comparing numbers. Actually these predicates evaluate terms that are treated as arithmetic expressions. The arguments could be variables instantiated to integers, or they could be integers written as constants, or they could be more general expressions. Here we will use these predicates just for comparing numbers, but later we'll use them in general arithmetic expressions. Note that we are allowed to write them as infix operators:

• X =:= Y: X and Y stand for the same number
• X =\= Y: X and Y stand for different numbers
• X < Y: X is less than Y
• X > Y: X is greater than Y
• X =< Y: X is less than or equal to Y
• X >= Y: X is greater than or equal to Y

Note that the less than or equal to symbol is not written as <= as in many programming languages. This is done so that the Prolog programmer is free to use the <= atom, which looks like an arrow, for other purposes.

Comparing Arbitrary Terms

They start with character @: @<, @>, @>=, and @=<.

Here are the principles that determine whether one term is considered less than another:

• All uninstantiated variables are less than all floating-point numbers, which are less than all integers, which are less than all atoms, which are less than all structures.
• For two non-sharing uninstantiated variables, one will be less than the other (which one is less may be different in different Prolog implementations). A floating point number is less than another floating point number or an integer is less than anothe integer in the expected way.
• One atom is less than another if it would come earlier than it in the normal dictionary ordering. To be precise, the ordering depends on the character codes, but these are usually ordered as one would expect, at least for alphabetic characters.
• One structure is less than another if its functor has a lower arity. If two structures have the same arity, one is less than the other if its functor is less than the other (using the ordering for atoms). If two structures have the same arity and functor, they are ordered by considering the arguments in turn – for the first corresponding arguments that differ, the order of the structures is the order of the relevant arguments.

Declaring Operators with Predicate op/3

In Prolog, if we wish to declare that an operator with a given position, precedence class, and associativity is to be recognised when terms are read and written, we use the built-in predicate op. If Name is the desired operator (the atom that we want to be an operator), Prec the precedence class (an integer within the appropriate range), and Spec the position/associativity specifier (one of the above atoms), then the operator is declared by providing the following goal:

?- op(Prec, Spec, Name).

As an example of declaring operators, the following is a list of the most important operators that are already defined in Standard Prolog:

?- op( 1200, xfx, ':-' ).
?- op( 1200, fx, '?-' ).
?- op( 1200, fx, ':-' ).
?- op( 1100, xfy, ';' ).
?- op( 1000, xfy, ',' ).
?- op( 900, fy, '\+' ).
?- op( 700, xfx, '=').
?- op( 700, xfx,\=).
?- op( 700, xfx, '==' ).
?- op( 700, xfx, \== ).
?- op( 700, xfx, '=..' ).
?- op( 700, xfx, '<' ).
?- op( 700, xfx, '>' ).
?- op( 700, xfx, '=<' ).
?- op( 700, xfx, '>=' ).
?- op( 700, xfx, '@<' ).
?- op( 700, xfx, '@=<' ).
?- op( 700, xfx, '@>' ).
?- op( 700, xfx, '@>=' ).
?- op( 700, xfx, 'is' ).
?- op( 500, yfx, '+' ).
?- op( 500, yfx, '-' ).
?- op( 400, yfx, '*' ).
?- op( 400, yfx, '//' ).
?- op( 400, yfx, '/' ).
?- op( 400, yfx, 'mod' ).
?- op( 200, fy, '-').

...

An operator declared yfx is left associative. Similarly, an operator declared xfy is right associative.

Note that the meanings of x and y (in terms of what other operators can appear unbracketed in the relevant position) are the same in all the other cases as well. This means that, for instance, the sequence

not not a

is legal syntactically if not is declared as fy, but is illegal if it is declared fx.

...

Prolog Input and Output

Here are some predicates for reading from the input stream and writing to the output stream:

Handling Files

The following predicates open and close files, get file handles, and set current input and output streams.

Satisfying a goal of the form clause(X, Y) causes X and Y to be matched with the head and body of an existing clause (for a public predicate) in the database. When an attempt is made to satisfy the goal, X must be instantiated enough so that the main predicate of the clause is known. If there are no clauses for the predicate, the goal just fails. If there is more than one clause that matches, Prolog will choose the first one. In this case, if an attempt is made to re-satisfy the goal, the other matching clauses will be chosen, one at a time.

Notice that, although clause always has an argument for the body of a clause, not every clause actually has a body. If a clause does not have a body, it is considered to have the dummy body true. We have been calling such clauses facts. By providing X's and Y's that are more or less instantiated, you can look for either all the clauses for a given predicate and number of arguments, or all the ones that match some pattern.

The predicate functor is defined in such a way that functor(T,F,N) means, T is a structure with functor [name] F and arity (number of arguments) N. It can be used in basically two ways. In the first way, T is already instantiated. The goal fails if T is not an atom or a structure. If T is an atom or structure, F is matched with the functor and N is matched with the integer giving the arity (number of arguments) of the functor. Note that in this context, an atom is considered to be like a structure with arity 0.

Here are some examples of goals involving functor:

?- functor(f(a, b, g(Z)), F, N).
Z = _23, F = f, N = 3
?- functor(a + b, F, N).
F = +, N = 2
?- functor([a, b, c], F, N).
F = ., N = 2
?- functor(apple, F, N).
F = apple, N = 0
?- functor([a, b, c], '.', 3).
no
?- functor([a, b, c], a, Z).
no

There is a second use to functor. This occurs when the first argument of the goal (T) is uninstantiated. In this case, both of the others must be instantiated: specifying a functor and a number of arguments respectively. A goal of this form will always succeed, and as a result T will become instantiated to a structure with the functor and number of arguments provided. So this is a way of constructing arbitrary structures, given a specification in terms of a functor [name] and its number of arguments. The arguments of such a structure constructed by functor are uninstantiated variables. Hence the structure will match any other structure with the same functor and number of arguments.

Copying an Existing Structure with function/3

A common use of functor to create a structure is when we wish to make a copy of an existing structure with new variables as the arguments of the principal functor. We can encapsulate this use in the definition of a predicate copy, as follows:

copy(Old, New) :- functor(Old, F, N), functor(New, F, N).

Here, two functor goals occur adjacently. If the copy goal has the first argument instantiated and the second uninstantiated, then the following will happen. The first functor goal will involve the first possible use of the predicate (because the first argument will be instantiated). Hence F and N will become instantiated to the functor and number of arguments of this existing structure. The second functor goal uses the predicate in the second way. This time the first argument is uninstantiated, and the information in F and N is used to construct the structure New. This is a structure involving the same functor and number of arguments as Old, but with variables as its components. Thus we would get interactions like:

?- copy(sentence(np(n(john)), v(eats)), X).
X = sentence(_23, _24)

Accessing Arguments in a Structure Through arg(N,T,A)

The predicate arg must always be used with its first two arguments instantiated. It is used to access a particular argument of a structure. The first argument of arg specifies which argument is required. The second specifies the structure that the argument is to be found inside. Prolog finds the appropriate argument and then tries to match it with the third argument. Thus arg(N, T, A) succeeds if the Nth argument of T is A. Let us look at some goals involving arg.

?- arg(2, related(john, mother(jane)), X).
X = mother(jane)
?- arg(1, a+(b+c), X).
X=a
?- arg(2, [a,b,c], X).
X = [b,c]
?- arg(1, a+(b+c), b).
no

Sometimes we will want to use functor and arg when the possible structures are known. This is because there may be so many arguments that it is inconvenient to specify them every time. Consider an example where we use structures to represent books. We might have a component for the title, the author, the publisher, the date of publication, and so on. Let us say that the resulting structures have fourteen components. We might write the following useful definitions:

is_a_book(book(_,_,_,_,_,_,_,_,_,_,_,_,_,_)).
title(book(T,_,_,_,_,_,_,_,_,_,_,_,_,_), T).
author(book(_,A,_,_,_,_,_,_,_,_,_,_,_,_), A).

In fact, we can write these much more compactly as:

is_a_book(X) :- functor(X, book, 14).
title(X, T) :- is_a_book(X), arg(1, X, T).
author(X, A) :- is_a_book(X), arg(2, X, T).

The predicates functor and arg provide one way of creating and accessing arguments of arbitrary structures. The predicate =.. (pronounced univ for historical reasons) provides an alternative way, which is useful if you want to obtain the arguments of a structure all together, or if you want to construct a structure, given a list of arguments.

The goal X =.. L means, L is the list consisting of the functor of X followed by the arguments of X.

Such a goal can be used in two ways, in the same way that a functor goal can. If X is instantiated, Prolog constructs the appropriate list and tries to match it with L. Alternatively, if X is uninstantiated, the list will be used to construct an appropriate structure for X to stand for. In this case, the head of L must be an atom (it will become the functor of X). Here are some examples of =.. goals:

?- foo(a,b,c) =.. X.
X = [foo,a,b,c]
?- [a,b,c,d] =.. L.
L = ['.',a,[b,c,d]].
?- (a+b) =.. L.
L = [+,a,b].
?- (a+b) =.. [+,X,Y].
X = a, Y = b.
?- [a,b,c,d] =.. [X|Y].
X = '.', Y = [a,[b,c,d]]
?- X =.. [a,b,c,d].
X = a(b,c,d)

It is assumed that X is instantiated to a term that can be interpreted as a goal. The call(X) goal succeeds if an attempt to satisfy X succeeds. The call(X) goal fails if an attempt to satisfy X fails. At first sight, this predicate may seem redundant, because one might ask why the argument of call shouldn't simply appear by itself as a goal?

For instance, the goal

..., call(member(a, X)),...

can always be replaced by

..., member(a, X),...

However, if we are constructing goals by using the =.. predicate or functor and arg, then it is possible to call goals that have a functor that is unknown at the time you type in your program.

Assuming that P, X, and Y are instantiated to a functor and arguments appropriately, call can be used as follows:

..., Z =.. [P,X,Y], call(Z),...

Negating with \+ X

The \+ predicate (pronounced not) is declared as a prefix operator. It is assumed that X is instantiated to a term that can be interpreted as a goal. The \+ X goal succeeds if an attempt to satisfy X fails. The \+ X goal fails if an attempt to satisfy X succeeds. In this way, \+ is rather like call, except that the success or failure of the argument, interpreted as a goal, is reversed.

Adding and Removing Rules

You use assert, asserta, assertz and retract to add and remove rules. They will only work on the definitions of predicates which have been declared dynamic . The intention again is to prevent accidental unplanned changing of definitions. A predicate foo/4 can be declared as dynamic by including the following in the relevant program file (before the definition of foo/4 or, if there is no definition, before the code that uses asserta etc.):

:- dynamic foo/4.

Several predicates can be declared as dynamic on one line by separating them with commas, e.g:

:- dynamic foo/4, baz/3.

Warning: These commands are deprecated because they create and remove global structures, introduce side effects and may cause other problems associated with poorly structured programs.

Working with Characters

The following two predicates compose and decompose an atom into its characters.

?- atom_chars(apple, X).
X = [a,p,p,l,e]
?- atom_chars(X, [a,p,p,l,e]).
X = apple

?- atom_chars(X, ['1' ,'2', '3']).

?- number_chars(123.5, X).
X = ['1', '2', '3', '.', '5']
?- number_chars(X, ['1', '2', '3']).
X = 123

Tail Recursion

There are actually two kinds of recursive routines. In a true recursive routine, each level must wait for the information from the lower levels in order to return an answer. This means that Prolog must build a stack with a new entry for each level.

This is in contrast to iteration, which is more common in conventional languages. Each pass through the iteration updates the variables and there is no need for building a stack.

There is a type of recursion called tail recursion that, while written recursively, behaves iteratively. In general, if the recursive call is the last call, and there are no computations based on the information from the lower levels, then a good Prolog interpreter can implement the predicate iteratively, without growing the stack.

One classic example of tail recursion is the factorial predicate. First we'll write it using normal recursion. Note that the variable FF, which is returned from the lower level, is used in the top level.

factorial_1 (1,1).
factorial_1 (N,F):-
  N > 1,
  NN is N - 1,
  factorial_1 (NN,FF),
  F is N * FF.

It works as expected.

?- factorial_1 (5,X).
x = 120

By introducing a new second argument to keep track of the result so far, we can rewrite factorial tail-recursively. The new argument is initially set to 1. Each recursive call builds on the second argument. When the boundary condition is reached, the third argument is bound to the second argument.

factorial_2(1,F,F).
factorial_2(N, T, F) :-
  N >1,
  TT is N * T,
  NN is N - 1,
  factorial_2(N N, TT, F).

It gives the same results as the previous version, but because the recursive call is the last call in the second clause, its arguments are not needed at each level.

7- factorial_2(5,1,X).
x = 120

By introducing a new second argument which will accumulate the partial answer through levels of recursion, we can rewrite reverse. It turns out that the partial answer is already reversed when it reaches the boundary condition.

reverse{[], Rev, Rev).
reverse([HIT], Temp, Rev) :-
  reverse(T ,[H ITemp], Rev).

We can now try the second reverse.

?- reverse([ants, mice, zebras], [], X).
X = [zebras, mice, ants]

Recursion-Based Graph Search

We next introduce the 3 x 3 knight's tour problem, create a predicate calculus based representation of problem states, and a recursive search of its state space. The chess knight can move on a restricted board as on any regular chessboard: two squares one direction (horizontally or vertically) and one in the other (vertically or horizontally). Thus, the knight can go from square 1 to either square 6 or 8 or from square 9 to either 2 or 4. We ask if the knight can generate a sequence on legal moves from one square to another on this restricted chessboard, from square 1 to 9, for example. The knight's moves are represented in Prolog using move facts.

The path predicate defines an algorithm for a path between its two arguments, the present state, X, and the goal that it wants to achieve, Y. To do this it first tests whether it is where it wants to be, path(Z, Z), and if not, looks for a state, W, to move to.

The Prolog search defined by path is a recursive, depth-first, left-to-right, tree walk. As shown before, assert is a built-in Prolog predicate that always succeeds and has the side effect of placing its argument in the database of specifications. The been predicate is used to record each state as it is visited and then not(been(X)) determines, with each new state found whether that state has been previously visited, thus avoiding looping within the search space.

path(Z, Z).
path(X, Y) :-
  move(X, W), not(been(W)), assert(been(W)),
  path(W, Y).

This use of the been predicate violates good programming practice in that it uses global side-effects to control search. been(3), when asserted into the database, is a fact available to any other predicate and, as such, has global extension. We created been to modify the program execution.

A more sophisticated method for control of search is to create a list that keeps track of visited states. We create this list and make it the third argument of the path predicate. As each new state is encountered, the member predicate checks whether or not it is already a visited state. If the state is not a member of the list we put it on this list in the order in which it was encountered, the most recent state encountered the head of the list. If the new state is on the list of already visited states, the path predicate backtracks looking for new non-visited states. This approach remedies the problems of using global been(W). The following clauses implement depth-first left-to right graph search with backtracking.

path(Z, Z, L).
path(X, Y, L) :-
  move(X, Z), not(member(Z, L)),
  path(Z, Y, [Z|L]).

Abstract Data Types in Prolog

Programming, in almost any environment, is enhanced by creating procedural abstractions and by hiding information. Because the set, stack, queue, and priority queue data structures are important support constructs for graph search algorithms, a major component of AI problem solving, we build them in Prolog in the present section.>

Since lists, recursion, and pattern matching are the primary tools for building and searching graph structures, they are the pieces with which we build our ADTs. All list handling and recursive processing that define the ADT are hidden within the ADT abstraction, quite different than the normal static data structure.

reverse_print_stack(S) :-
  empty_stack(S).
reverse_print_stack(S) :-
  stack(E, Rest, S),
  reverse_print_stack(Rest),
  write(E), nl.

insert_pq(State, [ ], [State]) :- !.
insert_pq(State, [H | Tail], [State, H | Tail]) :-
  precedes(State, H).
insert_pq(State, [H | T], [H | Tnew]) :-
  insert_pq(State, T, Tnew).
precedes(X, Y) :- X < Y. % < depends on problem

insert_list_pq([ ], L, L).
insert_list_pq([State | Tail], L, New_L) :-
  insert_pq(State, L, L2),
  insert_list_pq(Tail, L2, New_L).

empty_set([ ]).
member_set(E, S) :-
  member(E, S).
delete_if_in_set(E, [ ], [ ]).
delete_if_in_set(E, [E | T], T) :- !.
delete_if_in_set(E, [H | T], [H | T_new]) :-
  delete_if_in_set(E, T, T_new), !.
add_if_not_in_set(X, S, S) :-
  member(X, S), !.
add_if_not_in_set(X, S, [X | S]).
union([ ], S, S).
union([H | T], S, S_new) :-
  union(T, S, S2),
add_if_not_in_set(H, S2, S_new),!.
subset([], _).
subset([H | T], S) :-
  member_set(H, S),
subset(T, S).
intersection([], _, []).
intersection([H | T], S, [H | S_new]) :-
  member_set(H, S),
  intersection(T, S, S_new), !.
intersection([_ | T], S, S_new) :-
  intersection(T, S, S_new), !.
set_difference([ ], _, [ ]).
set_difference([H | T], S, T_new) :-
  member_set(H, S),
  set_difference(T, S, T_new), !.
set_difference([H | T], S, [H | T_new]) :-
  set_difference(T, S, T_new), !.
equal_set(S1, S2) :-
  subset(S1, S2),
  subset(S2, S1).

Depth-, Breadth-, and Best-First Search Using the Production System Design Pattern

path(Z, Z, L).
path(X, Y, L) :-
  move(X, Z), not(member(Z, L)),
  path(Z, Y, [Z | L]).

go(Start, Goal) :-
  empty_stack(Empty_open),
  stack([Start, nil], Empty_open, Open_stack),
  empty_set(Closed_set),
  path(Open_stack, Closed_set, Goal).

path(Open_stack, _, _) :-
  empty_stack(Open_stack),
  write(’No solution found with these rules’).
path(Open_stack, Closed_set, Goal) :-
  stack([State, Parent], _, Open_stack),
  State = Goal,
  write(`A Solution is Found!’), nl,
  printsolution([State, Parent], Closed_set).
path(Open_stack, Closed_set, Goal) :-
  stack([State, Parent], Rest_open_stack, Open_stack),
  get_children(State, Rest_open_stack, Closed_set, Children),
  add_list_to_stack(Children, Rest_open_stack, New_open_stack),
  union([[State, Parent]], Closed_set, New_closed_set),
  path(New_open_stack, New_closed_set, Goal), !.
get_children(State, Rest_open_stack, Closed_set, Children) :-
  bagof(Child, moves(State, Rest_open_stack, Closed_set, Child), Children).
moves(State, Rest_open_stack, Closed_set, [Next, State]) :-
  move(State, Next),
  not(unsafe(Next)), % test depends on problem
  not(member_stack([Next,_], Rest_open_stack)),
  not(member_set([Next,_], Closed_set)).

move(Present_state, Next_state) :- ... % test rules
move(Present_state, Next_state) :- ...
...

printsolution([State, nil], _) :- write(State), nl.
printsolution([State, Parent], Closed_set) :-
  member_set([Parent, Grandparent], Closed_set),
  printsolution([Parent, Grandparent], Closed_set),
  write(State), nl.

member_set([State, Parent], [[State, Parent]|_]).
member_set(X, [_|T]) :- member_set(X, T).

go(Start, Goal) :-
  empty_queue(Empty_open_queue),
  enqueue([Start, nil], Empty_open_queue, Open_queue),
  empty_set(Closed_set),
  path(Open_queue, Closed_set, Goal).

path(Open_queue, _, _) :-
  empty_queue(Open_queue),
  write(’Graph searched, no solution found.’).
path(Open_queue, Closed_set, Goal) :-
  dequeue([State, Parent], Open_queue, _),
  State = Goal,
  write(’Solution path is: ‘), nl,
  printsolution([State, Parent], Closed_set).
path(Open_queue, Closed_set, Goal) :-
  dequeue([State, Parent], Open_queue, Rest_open_queue),
  get_children(State, Rest_open_queue, Closed_set, Children),
  add_list_to_queue(Children, Rest_open_queue, New_open_queue),
  union([[State, Parent]], Closed_set, New_closed_set),
  path(New_open_queue, New_closed_set, Goal), !.
get_children(State, Rest_open_queue, Closed_set, Children) :-
  bagof(Child, moves(State, Rest_open_queue, Closed_set, Child), Children).
moves(State, Rest_open_queue, Closed_set, [Next, State]) :-
  move(State, Next),
  not(unsafe(Next)), %test depends on problem
  not(member_queue([Next,_], Rest_open_queue)),
  not(member_set([Next,_], Closed_set)).

go(Start, Goal) :-
  empty_set(Closed_set),
  empty_pq(Open),
  heuristic(Start, Goal, H),
  insert_pq([Start, nil, 0, H, H], Open, Open_pq),
  path(Open_pq, Closed_set, Goal).

path(Open_pq, _,_) :-
  empty_pq(Open_pq),
  write(’Graph searched, no solution found.’).

path(Open_pq, Closed_set, Goal) :-
  dequeue_pq([State, Parent, _, _, _], Open_pq,_),
  State = Goal,
  write(’The solution path is: ‘), nl,
  printsolution([State, Parent, _, _, _], Closed_set).
path(Open_pq, Closed_set, Goal) :-
  dequeue_pq([State, Parent, D, H, S], Open_pq, Rest_open_pq),
  get_children([State, Parent, D, H, S], Rest_open_pq, Closed_set, Children, Goal),
  insert_list_pq(Children, Rest_open_pq, New_open_pq),
  union([[State, Parent, D, H, S]], Closed_set, New_closed_set),
  path(New_open_pq, New_closed_set, Goal), !.

get_children([State,_,D,_, _],Rest_open_pq, Closed_set,Children,Goal) :-
bagof(Child, moves([State, _, D, _, _],
Rest_open_pq, Closed_set, Child,Goal),
Children).
moves([State, _, Depth, _, _], Rest_open_pq, Closed_set,[Next,State,New_D,H,S], Goal) :-
move(State, Next),
not(unsafe(Next)),
% application specific
not(member_pq([Next, _, _, _, _],Rest_open_pq)),
not(member_set([Next, _, _, _, _],Closed_set)),
New_D is Depth + 1,
heuristic(Next, Goal, H), % application specific
S is New_D + H.

printsolution([State, nil, _, _, _], _) :-
  write(State), nl.
printsolution([State, Parent, _, _, _], Closed_set):-
  member_set([Parent, Grandparent, _, _, _], Closed_set),
  printsolution([Parent, Grandparent, _, _, _], Closed_set),
  write(State), nl.

Special or Advanced Topics in Prolog

grandparent(X,Z) :- parent(X,Y), parent(Y,Z),
grandparent(X,Z) :- parent(Y,Z), parent(X,Y).

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

befriend(fred, tom).
friend(X,Y) :- befriend(X,Y).
friend(X,Y) :- befriend(Y,X).

Binding to C

The nature of this interaction with Prolog dictates the nature of a C to Prolog interface. It too must be able to either execute compiled Prolog code, or query a loaded Prolog program. In this sense, the interface from C to Prolog will look more like a database API than procedural interlanguage calls.

The Hello World program illustrates the Prolog to C direction of the interface as well. Note that the write statement has nothing to do with logic, pattern- matching, or search; it simply performs I/O. Prolog provides a number of special predicates, such as write, which are used primarily for their side effects. It is in this area that Prolog is weaker than C.

The Prolog programmer must rely on whatever special predicates a particular vendor provides with an implementation. So, for example, if a particular Prolog implementation doesn't supply the tools for accessing Windows, then it can't be used to implement Windows applications. This is where Prolog to C connections come in. They let a programmer define as many extended predicates, such as write, as desired, to allow Prolog code access to any services accessable from C. This fundamental architecture of Prolog shapes the design of an interface between it and C. The calls from C to Prolog reflect the database nature of Prolog. The calls from Prolog to C reflect the procedural nature of C.

Prolog Applications

eats(X):- ask(eats, X).
feet(X):- ask(feet, X).
wings(X):- ask(wings, X).
neck(X):- ask(neck, X).
color(X):- ask(color, X).

ask(Attr, Val):-
write(Attr:Val),
write('? '),
read(yes).

?- bird(X).
nostrils : external_tubular? yes.
live : at_sea? yes.
bill : hooked? yes.
size : large? yes.
wings : long_narrow? yes.
color : white? yes.
X = laysan_albatross

ask(A, V):-
  known(yes, A, V), % succeed if true
  !. % stop looking
ask(A, V):-
  known(_, A, V), % fail if false
  !,
  fail.
ask(A, V):-
  write(A:V), % ask user
  write('? : '),
  read(Y), % get the answer
  asserta(known(Y, A, V)), % remember it
  Y == yes. % succeed or fail

multivalued(voice).
multivalued(feed).

ask(A, V):-
not multivalued(A),
known(yes, A, V2),
V \== V2,
!,
fail.

size(X):-
  menuask(size, X, [large, plump, medium, small]).
flight(X):-
  menuask(flight, X, [ponderous, agile, flap_glide]).

menuask(A, V, MenuList) :-
  write('What is the value for'), write(A), write('?'), nl,
  write(MenuList), nl,
  read(X),
  check_val(X, A, V, MenuList),
  asserta( known(yes, A, X) ),
  X == V.
check_val(X, A, V, MenuList) :-
  member(X, MenuList),
  !.
check_val(X, A, V, MenuList) :-
  write(X), write(' is not a legal value, try again.'), nl,
  menuask(A, V, MenuList).

inv(0,1).
inv(1, 0).
nand(O, 0, 1).
nand(O, 1, 1).
nand(1, 0, 1).
nand(1, 1,0).

circ1(A, B, C, D, E) :-
  nand(A, B, T1),
  nor(C, 0, T2),
  nand(T1, T2, E).