More PROLOG

Copyright 1995, 1999 by Donald R. Tveter
http://www.dontveter.com drt@christianliving.net, don@dontveter.com
Commercial Use Prohibited

Chapter 12
PROLOG

12.1  More Useful Features of PROLOG

In this section we will look at some of the extra features that PROLOG has that PROLOG programmers will find necessary and useful.

12.1.1  consult and listing

The first of the practical features of PROLOG to look at are the consult and listing ``predicates". Consult and listing (and many other predicates) are effectively commands to do something. The consult command lets users read facts and rules off of a file and into the interpreter. A typical command would be:

   ?- consult(data).
where data is the name of the file to read from. The argument could also be an instantiated variable. Sometimes files will have names that do not meet the requirements of a PROLOG constant, for instance, there is the file with the name, data.23. Consulting this file requires placing the file name in single quotes:
   ?- consult('data.23').
There is another notation for consulting one or more files in a single command. It looks just like a list of constants:
   ?- [data,'data.23','data.24'].
To see all the facts and rules PROLOG has use the listing command:
   ?- listing.
If this produces too much information to be convenient, the facts and rules for some particular predicate, such as ``likes" can be listed using:
   ?- listing(likes).

12.1.2  The Anonymous Variable

Also, we have made mention of the anonymous variable, _, that can be used for pattern matching but which never gets set to any value. This variable can be useful in circumstances when you have to match patterns that contain more details than you really need to know about. For instance, suppose you had some data about Cubs games in the following format:

   game(1,april,7,cubs,4,mets,1).
   game(2,april,8,cubs,1,mets,4).
   game(3,april,9,cubs,7,cardinals,9).
   game(4,april,10,cubs,4,cardinals,3).
   game(5,april,11,cubs,1,astros,8).
In this predicate game, the first item is the game number, the second item is the month in which the game was played, the third item is the day of the month, the fourth item gives one team name (always the cubs), the fifth item is the number of runs the Cubs scored, the sixth item is the name of the other team involved in the game and the seventh item is the number of runs this other team scored. Suppose your problem is to count up the number of games the Cubs won. In this case, you only need to instantiate variables to the the two scores. You can write:
   game(_,_,_,_,Cubruns,_,Opponentruns)
This saves you from having to think up names for unused variables and it informs a reader of the program that the fields with an underscore are not relevant to the problem.

12.1.3  assert, asserta, assertz and retract

In section 4.2 we mentioned that there are procedures, assert and retract to add and subtract entries from the database. Assert actually puts the new clause at the end of the database. In addition, assertz does the same thing, and there is also an asserta that places clauses at the beginning of the database.

12.1.4  Implementing Global Variables with assert and retract

In section 4.2 we said that there are not any naturally occurring global variables in PROLOG, however now we will go and demonstrate two ways of simulating global variables. To illustrate the methods we will use a small PROLOG program that counts how many games the Cubs won using data like that shown above. The first method involves using assert and retract. The basic plan we use here will be to simulate a loop that selects a game and checks to see if the Cubs won. Initially, we have to set the number of games the Cubs won to 0. This is easily done like so:

   assert(havewon(0)).
Later as the program runs thru the list of games, this statement will have to be updated every time it finds the Cubs won a game. The rules for the entire problem are:
   count :- assert(havewon(0)),
            count2.
   count2 :- game(_,_,_,_,Cubruns,_,Opponentruns),
             Cubruns > Opponentruns,
             retract(havewon(Totalsofar)),
             Newtotal is Totalsofar + 1,
             assert(havewon(Newtotal)),
             fail.
   count2 :- write('The Cubs won '),
             havewon(Totalwon),
             retract(havewon(Totalwon)),
             write(Totalwon),
             write(' games.'),
             nl.
To get the number of games the Cubs won, call count. Count asserts that the number of games won is 0 and then count2 is called where games are selected and the scores are checked. In count2 select a game, then check if the Cubs won and if so then the havewon count needs to be updated. To do this, retract is used to remove the havewon entry and at the same time Totalsofar is instantiated to the number of games won. One is now added to this number and placed in the variable, Newtotal. Now we assert, havewon(Newtotal). The final test in the rule, is fail, a built-in predicate that always fails and this forces the interpreter to back up and look for alternatives. The first step PROLOG finds where an alternate solution is possible is the step that looks for another game so the next game is found and the process is repeated over and over until no more games can be found. When it runs out of games to try, the interpreter moves on to the second definition of count2 where it simply prints the answer. The number of games the Cubs have won is then retracted to keep it from possibly getting in the way of other questions.

12.1.5  recorda, recordz, recorded and erase

The second method of simulating global variables is to use the record predicates, recorda, recordz and recorded, however, not all PROLOGs have these predicates. With these predicates the system has access to a second database of facts that is structured slightly differently. The basic arguments to recorda (or recordz or recorded) are:

   recorda(Key,Term,Reference)
Key is just some kind of indexing feature for the Term that is stored away and Reference is a system generated identifying code. For the problem we are working on, we could choose the Key to be, ``havewon" and Term to be ``0". A call to recorda with these parameters together with the PROLOG output is shown below:
  ?- recorda(havewon,0,R).
  R = $record(802636)
To retrieve the stored information, the recorded predicate is used like so:
  ?- recorded(havewon,X,R).
giving:
  X = 0,
  R = $record(802636)
While recorda places entries at the top of the internal database, recordz places them at the end of the internal database. In addition, to erase a record, the erase predicate is called with the proper reference value:
   ?- recorded(havewon,0,R), erase(R).
It should be pretty clear that to find out the number of games that the Cubs won, the previous PROLOG program can just be adapted to use recorda, recorded and erase instead of assert and retract:
   count :- recorda(havewon,0,R),
            count2.
   count2 :- game(_,_,_,_,Cubruns,_,Opponentruns),
             Cubruns > Opponentruns,
             recorded(havewon,Totalsofar,R1),
             erase(R1),
             Newtotal is Totalsofar + 1,
             recorda(havewon,Newtotal,R2),
             fail.
   count2 :- write('The Cubs won '),
             recorded(havewon,Totalwon,R),
             erase(R),
             write(Totalwon),
             write(' games.'),
             nl.

From time to time, either method of simulating global variables can be useful but in general the iterative approach shown here for finding solutions is awkward to impossible on larger problems and PROLOG programmers need to get used to using recursive programming methods.

12.1.6  Structuring Data with Functors

PROLOG has a data structuring facility that uses functors , to create structures . Structures are much like records in Pascal. A predicate with arguments is in fact a structure that the interpreter will evaluate to true or false. For an example of structure use, here are some definitions that give the contents of some compact disks, where ``cd", ``conductor", ``orchestra", ``contains", ``composer" and ``title" are all functors:

   cd(1,conductor(mehta), orchestra('los angeles'),
        contains(composer(strauss, richard),
                 title('alpine symphony'))).
   cd(2,conductor(slatkin), orchestra('st louis'),
        contains(composer(copland), title('billy the kid')))
   cd(3,conductor(abbado), orchestra(chicago),
        contains(composer(tchaikovsky), title('symphony no 5'))).
Now to look up pieces of music in the database by Richard Strauss, we can ask PROLOG:
   ?- cd(_,_,contains(composer(strauss,richard),title(X))).
Note that in this case if we just tried to look up the composer, as strauss with only one field, it would fail because the number of arguments for the functor, composer, would not match:
   ?- cd(_,_,contains(composer(strauss),title(X))).
For another example, suppose we know the title of a work and we want to know who the composer is. We could ask PROLOG:
   ?- cd(_,_,_,contains(X,title('alpine symphony'))).
Then PROLOG will report, X = composer(strauss,richard). Internally, structures like ``contains" are trees as shown in figure 12.1.

In section 4.2 we said that arithmetic expressions are actually stored internally in a structure format. The infix expression:

   (A + 1) * (B + 2)
becomes internally:
   *(+(A,1),+(B,2))
Naturally, this is also a tree structure as shown in figure 12.2.

Lists are also defined using the functor, ``." pronounced ``dot". For a list containing just the symbol a, it is written out as:

   .(a,[]),
where [] corresponds to a special constant called the empty list. The above structure corresponds to the tree on the left in figure 12.3. The list containing the symbols a, b and c is:
   .(a,.(b,.(c,[]))),
and its tree structure is shown on the right in figure 12.3.

Of course, PROLOG allows a shorthand notation for lists, where the elements of a list can simply be enclosed in square brackets and separated by commas:
   [a,b,c] 
Lists within lists are allowed and one such list, together with its tree structure is shown in figure 12.4. Recall that the ``|" operator can be used to split a list into a head and a tail. Actually if you look at the tree that represents the list, the head of the list represents the expression below and to the left of a dot while the expression below and to the right represents the tail of the list.

12.1.7  Relational Operators

PROLOG also has a set of relational operators available for comparing numbers and terms. These are the straightforward ones:
>
for greater than,
<
for less than,
= <
for equal or less than
> =
for greater than or equal.
On the other hand, there are several different equality and inequality tests available. In PROLOG, the equal sign (=) sets PROLOG off on an attempt to match the two sides of an expression and make them equal. So, if X and Y are uninstantiated variables, then the following ``comparisons" produce, yes:

   ?- X = 5.
   ?- X = Y.
   ?- X + Y = a + b.
In the first case, X will be instantiated to 5, in the second case, X and Y will share and in the third case, X will be instantiated to a and Y will be instantiated to b. The following ``comparisons" produce no:
   ?- 4 = 5.
   ?- 5 + 3 = a + 3.
Some PROLOGs have the relational inequality operator, \=, that succeeds when = fails. The operator, == tests to see if two terms are equal without trying to match both sides. Below are some comparisons and their results:
   ?- X == 5.              no
   ?- a(b,c) == a(b,c).    yes
   ?- a(B,C) == a(b,c).    no
   ?- X == Y.              no
   ?- X = Y, X == Y.       yes
In the last case, X and Y are first made equal, so naturally, X == Y succeeds. The opposite of == is \==. Here are some comparisons and their results:
   ?- X \== 5.             yes
   ?- a(b,c) \== a(b,c).   no
   ?- a(B,C) \== a(b,c).   yes
   ?- X \== Y.             yes
   ?- X = Y, X \== Y.      no
To invert results, C-PROLOG has a not predicate and C-PROLOG and UNH PROLOG both have a not operator, \\+ that inverts results. These questions then, all come out, no:
   ?- not(X = 5).             ?- \+ X = 5.
   ?- not(X = Y).             ?- \+ X = Y.
   ?- not(X + Y = a + b).     ?- \+ (X + Y = a + b).
while the following all come out yes:
   ?- not(4 = 5).             ?- \\+ 4 = 5.
   ?- not(5 + 3 = a + 3).     ?- \\+ (5 + 3 = a + 3).
PROLOG also provides two other operators for doing numerical comparisons that don't attempt to make the two sides match. The operator, =:= compares numeric values looking for equality and the operator, =\= compares numeric values looking for inequality. The following tests succeed:
   ?- 1 =:= 1.
   ?- 1 =\= 2.
while these tests fail:
   ?- X =:= 5.
   ?- X =\= 5.

12.1.8  Other Operators

The usual built-in arithmetic operators are +, -, *, /, mod and some implementations may have the integer division operator, div. Many PROLOGs also have predicates available to evaluate trigonometric and exponential functions. Some PROLOGs give users the ability to define new operators.

12.1.9  The Cut

There is an important pseudo-goal in PROLOG, called the cut that is represented by an exclamation point (!). The cut is designed to prevent back-tracking by the PROLOG interpreter. It has a couple of practical uses and it can sometimes be used to increase the efficiency of PROLOG programs. A very simple use of the cut can be seen in the following PROLOG rule:

   g :- a, b, c, !, d, e, f.
When PROLOG comes across this rule it of course tries to prove each goal in order. However, if PROLOG should happen to prove c, the pseudo-goal, !, automatically succeeds but it also forms a barrier that prevents backtracking to the left of the cut. PROLOG can roam about the right side of the cut, back-tracking as necessary, but if all the alternatives there fail and PROLOG tries to backtrack to the left of the cut, the whole process fails. Here is a short program using this rule:
   a :- assert(d).
   b :- assert(e).
   b :- assert(f(1)).
   c.
   g(X) :- a, b, c, !, d, e, f(X).
   g(X) :- print('will not reach here with a cut'), nl.
If we ask PROLOG to evaluate g(Y), PROLOG will report, ``no". It starts by looking at the first g(X) rule. It calls a, which asserts d is true. It calls b which asserts e is true. It finds c is true and then passes the cut. It then finds d and e are true but it will not find f(X) is true. Without the cut, PROLOG would back up and try the second definition of b and that second definition would assert what is necessary for f(X) to succeed. With the cut present, the first g(X) rule simply fails and you would expect that PROLOG would simply go on to the second g(X) rule and succeed but in fact it does not go on to the second rule. When the first rule for g(X) failed, the existence of the cut in the first rule caused all other rules with the g predicate to also fail, so the second g rule isn't even tried.

This feature of the cut that causes all rules with the same predicate at the head of the rule to fail can be put to good use. Here it is used in a definition of factorial:

   /* 1 */   factorial(N,M) :- N < 0, !, fail.
   /* 2 */   factorial(0,1).
   /* 3 */   factorial(N,M) :- X is N-1,
                               factorial(X,Y),
                               M is N * Y.
Rule number 1 is designed to trap any request for the factorial of a negative number. If the user tries this, PROLOG will not attempt to find another way to satisfy the factorial predicate. In addition, someone might ask PROLOG for the factorial of a legitimate number, like, 3. After PROLOG responds with the answer, 6, a mischievous user could go ahead and type a ; that would set PROLOG off on an effort to find a second solution that just simply doesn't exist. Again, the cut in statement 1 prevents this.

12.2  Input, Output and Other Useful Predicates

In this section we will look at ways to do input and output of terms and characters as well as at some related predicates.

12.2.1  Reading

A term is either a number, a constant or a structure built up out of a functor with arguments. There is a built-in predicate, read, to read terms. It requires that the term be followed by a period. If the call to read is: read(X), then terms such as the following can be read:

   99.
   97.1.
   hello.
   'Fort Laramie'.
   likes(john,mary).
   likes(X,yankees) :- likes(X,lemonade).
This last term really isn't any problem because PROLOG regards the :- symbol as just another operator and the rule as just another structure. The default is to do reads from the terminal input file. It is possible to read from another file by using the predicate, see, as in the following example where terms will be read from the file, f:
   ?- see(f), read(X), read(Y), read(Z),
              print(X), tab(4),
              print(Y), tab(4),
              print(Z), nl,
              seen.
In the above example, the first three terms on the file, f, will be read. The first term read will be printed, then 4 blanks will be printed, then the second term will be printed, then four blanks, then the third term and then the end of line. Notice that tab(N) writes out N blanks and does not move to column N, as might be expected. The function of the seen predicate is to reestablish the terminal input file as the default file to read from. If you try to read beyond the last term on the file, the variable will first come back with the value, end_of_file and if another read beyond this is attempted the request being processed will fail.

12.2.2  Printing

When it comes to printing terms, the predicates write and print are identical and they each output a single term. If a term contains operators, then write and print both write out the term by transforming its internal structured representation to infix notation. For instance, write(+(a,b)) produces:

   a + b
To force terms to be printed as they are in their internal structured representation, the predicate, display can be used, thus, display(+(a,b)) produces:
   +(a,b)
When it comes to backtracking across the predicates, read, write, print, tab, display and nl, PROLOG will not try to re-satisfy them. For instance, it might occur to you to try to read and write all the terms in a file using the following scheme:
   ?- see(f), read(X), print(X), X = end_of_file, seen.
The first item in the file will be read and printed. If this first item is not the end of file constant, PROLOG will start backtracking but it will not try to do another read. To read and write every term in a file a recursive solution is necessary.

Ordinarily, write, print, tab, display and nl apply to the standard terminal output file. To switch to another file, the predicate, tell, is called. Its argument should be instantiated to the name of the file to print on. To end output to the file and return to writing to the standard terminal file, the predicate, told, is called. An example of this where output goes to the file, f, would be:

   ?- tell(f), print('Hello World'), nl, told.

12.2.3  Reading and Writing Characters

PROLOG also has predicates for reading and writing individual characters. The predicate, put, will write out a single character. Unfortunately, the argument has to be the integer representing the ASCII character, so, to print ``hello" using put you have to say:

   ?- put(104), put(101), put(108), put(108), put(111).
Of course this is rather inconvenient, if it is just a matter of printing hello, it is better to use print or write:
   ?- print(hello).
Another feature of PROLOG is that it will consider a string of characters enclosed in double quotes to be a list of integers representing the characters. Therefore, if we enclose hello in double quotes it is the same as the list:
   [104, 101, 108, 108, 111].
With a list of characters it is easy to devise a recursive procedure to print them all out:
   putstring([]) :- !.
   putstring([A | Rest]) :- put(A), putstring(Rest).
Using this scheme we could get PROLOG to print out hello, just by typing:
   putstring("hello").
Of course, this approach isn't all that convenient compared to just using print to output the equivalent constant.

Characters are read using get and get0. When called with an uninstantiated variable, get will instantiate that variable to the next printing character in the input stream. Printing characters are those that will show up on the terminal screen so control characters will be skipped over. Get0, on the other hand, will return the very next character no matter what it is. Unfortunately, there is no way to look ahead to see the next character without reading it, as is the case in Pascal with its file buffer variable. Neither is there a predicate that will ``un-get" a character as in C. PROLOG programmers, can however, create their own predicates to do these things.

12.2.4  Reading Sentences

To illustrate character reading plus some other useful PROLOG predicates, we will work on building a very small interpreter that will take three word sentences from the keyboard. The sentences will be either a statement of fact, ending in a period, or a question, ending in a question mark. Some examples of the type of input the program will take are the following:

   john loves mary.
   mary loves fred.
   john loves baseball.
   john loves mary?
   mary loves baseball?
For a statement of fact, the fact will be be added to the database. For a question, the question will be passed on to the PROLOG interpreter to determine whether it is true or not.

To start with, we need a predicate that will scan the input looking for the first character that is not a blank. The following two statements define, scan, a predicate that will do this:

   /*  1 */ scan(C,C) :- C =\\= 32, !.
   /*  2 */ scan(C,C2) :- get0(C1), scan(C1,C2).
To use scan we have to supply it with a character (first argument), which it checks to see if it is a blank (ASCII 32) or not. If it is not a blank then it returns the character (second argument) otherwise scan will read a character using get0 and pass that character on to another call of scan. The process continues until a non-blank is found. To get the process started, scan will of course have to be supplied with an initial character as in:
   ?- get0(X), scan(X,Y).

Now that we have the procedure scan that can find the first letter of a word, we will work on accumulating all the characters in the word in a list. Every word will be terminated by either a blank, a period or a question mark. When we find a blank we will do nothing special. When we find a period or a question mark, we will need to assert that end_of_sentence is true and in addition, for a question mark, we will assert that question is true. Here are the PROLOG rules to accomplish this:

   /*  3 */ rw(W) :- get0(X), scan(X,A), rest(A,W).
   /*  4 */ rest(32,[]).
   /*  5 */ rest(46,[]) :- assert(end_of_sentence).
   /*  6 */ rest(63,[]) :- assert(end_of_sentence),
                           assert(question).
   /*  7 */ rest(C, [C | R]) :- get0(X), rest(X,R).
The basic predicate to call is rw, for read word. The call, rw(X) will produce a prompt for input. If we type in: ``hello.", then PROLOG reports:
   X = [104, 101, 108, 108, 111].
The way rw works is quite straightforward. First, get a character to start the problem and call scan to possibly read characters until a non-blank is found. When this first letter, A, has been found, it is passed on to the predicate, rest. Rest will accumulate the rest of the letters in the word and return W, the complete list of characters in the word, W. Rest is also straightforward. Its first argument is the character to examine. Rules 4, 5 and 6 check for an end of word indication, either a blank (32), a period (46) or question mark (63). All three of these rules return [ ] to finish off the list of characters and these rules also stop the recursion. If the character is not any of these word ending characters then go on to rule 7, where another character is read, added to the list and rest is called again.

The next problem is to read a whole sentence. In our particular case, we could resort to just reading three words, but for the sake of generality, we will assume that there can be an arbitrary number of words in each sentence. The predicate to do this is rs, for read sentence. The solution follows the typical recursive pattern. Rs reads one word, then calls up rs again to read the rest of the words, and so on until rs finds it can retract the end_of_sentence fact that was asserted by rest. The rules are:

   /*  8 */ rs([]) :- retract(end_of_sentence).
   /*  9 */ rs([W|R]) :- rw(W), rs(R).
Rs is called with a single argument, as in:
   ?- rs(S).
If the user types in:
   john loves mary.
rs produces:
   S = [[106,111,104,110],[108,111,118,101,115],[109,97,114,121]]
With the sentence in this form we will go ahead and convert each list of characters to a single atom. The built-in PROLOG predicate, name, does this. As an example of how name works we will take the list of characters for john and convert it to an atom like so:
  ?- name(X,[106,111,104,110]).
  X = john
It is also possible to take an atom and convert it into a list of integers as in:
  ?- name(hello,X).
  X = [104,101,108,108,111]
With this capability, it is easy to convert a list of lists of characters into a list of atoms. The predicate to do this will be called mkatoms. Its first argument will be the list of lists of characters and its second argument will be the list of atoms:
   /* 10 */ mkatoms([],[]).
   /* 11 */ mkatoms([A|B], [Namea|Namerest]) :- name(Namea,A),
                                                mkatoms(B,Namerest).
In this example, we use rs and mkatoms and type in, ``john loves mary.":
   ?- rs(S), mkatoms(S,L).
giving:
   S = [[106,111,104,110],[108,111,118,101,115],[109,97,114,121]],
   L = [john,loves,mary]

The next step in turning a list, like L, above, into a fact that can be asserted is to reverse the first two items in the list. Reversing the first two items can be done like so:

   ?- Y = [john,loves,mary], Y = [A,B,C], Z = [B,A,C].
The first clause merely sets a value for Y, then Y is then matched against the pattern, [A,B,C], giving:
   A = john,
   B = loves,
   C = mary
and finally, Z is set equal to the list, [B,A,C], giving:
   Z = [loves,john,mary]
From here we can use the built-in operator that consists of an equal sign followed by two dots, =.. and pronounced ``univ" to produce an ordinary PROLOG term. An example of the use of =.. is:
   ?- P =.. [loves,john,mary].
which gives:
   P = loves(john,mary).
Of course, =.. will happily take a PROLOG term and turn it into a list of atoms, as in:
   ?- likes(matt,mets) =.. L.
giving:
   L = [likes,matt,mets]
Now we can read a sentence, rearrange the words and convert it to a term. The predicate, interpret, shown below does this:
   /* 12 */ interpret :- rs(X),
                         mkatoms(X,Y),
                         Y = [A,B,C],
                         Z =..\ [B,A,C],
                         interpret2(Z).
Notice that interpret passes the term, Z, on to interpret2. The clauses for interpret2 will examine the data base and see if the sentence is a question to be answered or a fact to be added to the data base. The definition for interpret2 is:
   /* 13 */ interpret2(Z) :- question,
                             call(Z),
                             retract(question),
                             print('absolutely!'),
                             nl.
   /* 14 */ interpret2(Z) :- retract(question),
                             print('no way!'),
                             nl.
   /* 15 */ interpret2(Z) :- assert(Z),
                             print('ok!'),
                             nl.
In rule 13, PROLOG checks to see if question is true. If it is, the call predicate will pass the term, Z, on to the PROLOG interpreter. If this call succeeds the rest of rule 13 will retract question and print out the response 'absolutely!'. In this case, that will be the end of the call to interpret as well. The call predicate may fail, however, in this case PROLOG will back-track from the call and be forced to go on to rule 14. Rule 14 will try to retract question and if it can, this means that the call in 13 failed and so rule 14 prints out 'no way!'. On the other hand, if 14 fails, Z must have been a statement of fact and PROLOG will move on to rule 15 and enter the fact into the data base.

This whole arrangement requires the user to type in, ``interpret.", every time a fact is entered or a question is asked. Of course it would be easy to devise a predicate to repeatedly call interpret until some special sentence like, ``halt." is entered. Figure 12.5 lists the whole program.

12.3  Programming Examples

In this section we will look at a few extra examples of PROLOG programs involving the manipulation of lists.

12.3.1  Tree Searching and Substitution

The first example to look at will be a tree search procedure with the predicate named, ts. The first argument is the tree to search and the second argument is the item to search for. Its definition looks just like the recursive versions that can be programmed in conventional languages:

   /* ts1 */   ts([],Item) :- fail.
   /* ts2 */   ts(Tree,Item) :- Tree == Item.
   /* ts3 */   ts([First|Rest],Item) :- ts(First,Item).
   /* ts4 */   ts([First|Rest],Item) :- ts(Rest,Item).
A sample call to ts would be:
   ts([*, [+,a,b], [+,c,d]], [+,a,b]).
As to how ts works, rule ts1 says that the item can't be found in an empty list, so return failure. Rule ts2 tests to see if the tree it has been given is the entire item. Rule ts3 looks for the item within the first part of the tree and rule ts4 looks for the item within the rest of the tree.

When an item is found within a tree it is often necessary to substitute another expression for it. For example we may want to go through a tree and substitute 3 for every occurrence of x. In the subst predicate defined below the first parameter gives the tree to search and the second item is the expression to be replaced. The third item is the replacement for the second expression and the fourth argument is a new tree in which the replacements have been done. Here is the definition of subst:

   /* s1 */   subst([],Old,New,[]).
   /* s2 */   subst(Tree,Old,New,New) :- Tree == Old.
   /* s3 */   subst(Tree,Old,New,Tree) :- atomic(Tree).
   /* s4 */   subst([First|Rest],Old,New,[Newfirst|Newrest]) :-
                    subst(First,Old,New,Newfirst),
                    subst(Rest,Old,New,Newrest).
Rule s1 states that if the tree to search is empty, the resulting tree is also empty. Rule s2 tests to see if the whole tree is equal to the pattern we want to replace and if it is, the resulting tree is the new expression. Rule s3 catches a tree that consists of a single atom and sends back that atom. The predicate, atomic, in that rule tests for single atoms. If none of these rules succeeds, then we apply subst to the first part of the tree to produce a new first part and then apply subst to the rest of the tree to produce a new rest of the tree. The answer to send back is a new tree with the new first part on the left and a new rest part on the right.

12.3.2  Append

One of the most important list manipulation predicates a PROLOG programmer needs is the append predicate that appends, or concatenates two lists together. It has other interesting capabilities as well. The definition of append is quite short:

   append([],L,L).
   append([A|L1],L2,[A|L3]) :- append(L1,L2,L3).
This definition of append means that if you concatenate together the first argument with the second argument you produce the third argument. For example:
   ?- append([a,b,c],[1,2,3],L).
gives:
   L = [a,b,c,1,2,3]
The method of operation follows the usual pattern of recursive definitions. The second of the two rules is designed to split off from the first argument one item for each recursive call until it becomes the empty list. In the above example, in the first call, a will be split off and it will go on the front of the third argument. The rest of the third argument is undefined at this point. To define it, the append predicate is called again, minus the a on the front of the first argument. This call will put b on the front of the third argument and the third call will put c on the front of the third argument. Finally, when the first argument becomes the empty list, the first rule applies and the result becomes the second argument. At this point, the third argument in the first call of append (when a was broken off) is completely instantiated.

Append can be used to do more than run lists together. First, we can give a value for the first and third argument and PROLOG will find the value of the second argument as in this example where:

   ?- append([a,b,c],L,[a,b,c,1,2,3]).
gives:
   L = [1,2,3]
Second, if we give the second and third argument, PROLOG will find a value for the first argument:
   ?- append(L,[1,2,3],[a,b,c,1,2,3]).
gives:
   L = [a,b,c]
Finally, if only the third argument is instantiated, PROLOG can go and find all the different ways that the first and second arguments can be instantiated to produce the third:
   ?- append(X,Y,[a,b,c,1,2,3]).
   X = [],
   Y = [a,b,c,1,2,3];
   X = [a],
   Y = [b,c,1,2,3];
   X = [a,b],
   Y = [c,1,2,3];
   X = [a,b,c],
   Y = [1,2,3];
   X = [a,b,c,1],
   Y = [2,3];
   X = [a,b,c,1,2],
   Y = [3];
   X = [a,b,c,1,2,3],
   Y = [];

We will look at how this last task is accomplished since it is a little messier than other PROLOG problems we have tried. PROLOG starts by matching against the first rule giving this solution:

   append([],[a,b,c,1,2,3],[a,b,c,1,2,3]).
When we ask for more by typing a semi-colon, PROLOG moves on to the second rule where PROLOG notices that X can match the list, [A|L1], Y can match the list, L2 and [a,b,c,1,2,3] matches [A|L3] with A then becoming, a, and L3 then becoming [b,c,1,2,3]. We can make the matches more apparent by writing the two terms one above the other like so:
   append(   X,     Y, [a , b,c,1,2,3]).
   append([A | L1],L2, [A | b,c,1,2,2]).
If the tail of rule 2 can be made to succeed, a new solution will be found. The tail becomes the problem:
  (1) append(L1,L2,[b,c,1,2,3]).
This matches with rule 1 giving L1 = [ ], L2 = [b,c,1,2,3]. PROLOG can now give the solution:
   append([a],[b,c,1,2,3],[b,c,1,2,3]).
If the user asks for another one, PROLOG will be using the call above labeled (1). Asking PROLOG for more can be regarded as a user created failure of rule 1, so PROLOG moves on to rule 2. PROLOG finds it can match (1) like so:
   (1) append(   L1,    L2, [b | c,1,2,3]).
   (2) append([A | L1], L2, [A | c,1,2,3]).
Here in the line labeled (2), remember that the L1 and L2 are entirely new variables in another call and are not the same as the L1 and L2 in the line labeled (1). Since the heads can be made to match, PROLOG goes off on the new problem:
   append(L1,L2,[c,1,2,3]).
Of course, this matches the first rule and PROLOG can report the next solution:
   append([a,b],[c,1,2,3],[a,b,c,1,2,3]).
This whole cycle can continue until it becomes impossible to break off another item in rule 2. This kind of scheme whereby a PROLOG predicate can have different combinations of its variables instantiated and still find solutions for the other uninstantiated variables has been referred to as ``reversible programming".

12.3.3  Quicksort

Sorting is a major preoccupation of Computer Science and so it is interesting to see some sorting algorithms done in PROLOG. These algorithms can be remarkably compact. The first one we want to look at will be quicksort. We will work on this problem from the top down. The first step is to state that the quicksorted version of the empty list is the empty list:

   /* qs1 */   qs([],[]).

If the list to be sorted is not empty, then we will take the first number in the list, call it K, and use it to partition the rest of the list into a left part where all the numbers are less than K and a right part where all the numbers are greater than or equal to K. We simply sort these two pieces and put together a new list with the sorted left portion followed by K, followed by the sorted right portion. To put the pieces together we can use append. The rule to do all this is quite straightforward:

   /* qs2 */   qs([K|Rest],Sorted) :-
                  partition(K,Rest,Left,Right),
                  qs(Left,Sortedleft),
                  qs(Right,Sortedright),
                  append(Sortedleft,[K|Sortedright],Sorted).
For example, if we want to quicksort the list, [19, 5, 23, 17, 89, 0, 101], partitioning will produce:
Left = [5, 17, 0]       Right = [23, 89, 101]
Quicksorting each will give:
Left = [0, 5, 17]       Right = [23, 89, 101]
In doing the call to append, we attach 19 to the front of the right list giving:
Sorted = [0, 5, 17, 19, 23, 89, 101]

We are now left with the problem of defining the partition predicate. As usual, we will break off the first number from the list and deal with it. If it is less than K it will be put on the front of the Left list by this rule:

   /* qs3 */   partition(K,[A|Rest],[A|Left],Right) :-
                  A < K,
                  partition(K,Rest,Left,Right).
otherwise, the following rule will put it on the right side:
   /* qs4 */   partition(K,[A|Rest],Left,[A|Right]) :-
                  A >= K,
                  partition(K,Rest,Left,Right).
Actually, if the rules labeled qs3 and qs4 are in order, the test, ``A > = K" isn't even needed. Again, as usual, when there are no more elements to break off the list, we stop the recursion this time using:
   /* qs5 */   partition(K,[],[],[]).

12.3.4  The Selection Sort

The second sort we will look at will be the selection sort. Recall that the principles of selection sorting are that the list is searched to find the largest (or smallest) number in the list, the number is removed from the original list and then this number is placed at the beginning (or the end) of another list. In this version, we will work on finding the largest number and place it at the beginning of the sorted list, giving a list in descending order of values. Again, sorting an empty list is quite easy:

   /* ss1 */  ss([],[]).
but sorting larger lists requires more effort. To do this we take the whole list and split it into a tentative maximum value, Tmax and R, the rest of the list. We find the maximum value, Max, in the whole list, [Tmax|R] and call the list without Max, L. We perform the sorting of L and the result will be the list, Sorted. The final answer for the completely sorted original list will be Max followed by Sorted. In PROLOG, this is:
   /* ss2 */  ss([Tmax|R],[Max|Sorted]) :-
                 max([Tmax|R],Tmax,Max,L),
                 ss(L,Sorted).
The remaining problem is to find the largest number in the list and remove it. Finding the largest number is straightforward. The solution is to break one number at a time off the list and work with it. If it is larger than Tmax, then send off this new larger value to the next call, otherwise simply pass on the current largest value. Rule ss4, below, sends down a new larger number and rule ss5 sends down the current largest value. Rule ss3 catches the case where there aren't any more values to test. In this case, the actual maximum value becomes the tentative maximum value. Here is the definition of the max predicate:
   /* ss3 */  max([],Max,Max,[]).
   /* ss4 */  max([A|R],Tmax,Max,Back) :- A > Tmax,
                                          max(R,A,Max,B),
                                          remake(A,Max,B,Back).
   /* ss5 */  max([A|R],Tmax,Max,Back) :- max(R,Tmax,Max,B),
                                          remake(A,Max,B,Back).
As outlined above, max finds the largest value on the way ``down", now, on the way ``up", max constructs a new list that does not contain the largest value. Rule ss3 supplies the initial list, the empty list, to send back up. Suppose on return from ss3, PROLOG finds itself in rule ss4 with B equal to the empty list. The predicate, remake is called to compare the selected number, A, in this call with Max to see if it should be added to the list that will be sent back. The current list is supplied to the predicate remake as the third argument. If A = Max then rule ss6 (below) sends out in the fourth argument the same list as the list going in otherwise rule ss7 sends back the number added onto the list:
   /* ss6 */  remake(A,Max,Back,Back) :- A =:= Max.
   /* ss7 */  remake(A,Max,Back,[A|Back]).
Notice that this arrangement will not be able to correctly handle lists with duplicate entries. So the call:
   ?- ss([1,1,2,3],X),   produces:   X = [3,2,1].
We leave it as an exercise to modify the program to handle duplicate values.

12.4  Exercises


12.1.
Draw tree structures for the following trees:

   [a,b,[c,d]]
   [[a,b,[c,d]]]
   [[a,[b,c],d]]
   [[a,b,[c,d],[e,f],[g]]]


12.2.
Determine if the call, h(X) will succeed given the facts and rules:

   a :- assert(d).
   b :- assert(e).
   b :- assert(f(1)).
   c.
   i.
   i :- assert(f(2)).
   j.
   g(X) :- a, b, c, !, d, e, f(X).
   g(X) :- print('will not reach here with a cut'), nl.
   h(X) :- i, g(X), j.


12.3.
Program a recursive predicate to read and print all the terms in a file.


12.4.
Binary search trees have the useful property that at a parent node, every number to the left of the node is less than the value at the parent node and every number to the right of the node is greater than the value at the parent node.

a)Write a PROLOG program that will search a binary search tree for a given number. Naturally you will take advantage of the order within the tree to do the search quickly.

b)Write a PROLOG program to insert numbers into a binary search tree. You may want to store the tree in the database and retrieve it when necessary.

c)Write a PROLOG program to delete a number from a binary search tree.


12.5.
Here is a definition for bubblesort, where the first argument is the unsorted list and the second argument is the sorted list:

   bubsort(U,S) :- append(X,[A,B|Y],U),
                   A > B,
                   append(X,[B,A|Y],N),
                   bubsort(N,S).
   bubsort(L,L).
Explain how this PROLOG program works. Suppose when PROLOG returns a sorted list the user types a ``;" to make PROLOG look for an alternate answer. What happens?


12.6.
Find one or more ways to modify the selection sort given in section 12.3 so that it won't lose duplicate entries.


12.7.
Program mergesort.


12.8.
The univ operator, =.., takes a structure and turns it into a list as in the following example:

   ?- +(a,b) =.. L.
   L = [+, a, b]
However, univ will only convert the top level structure to a list. It will convert *(3,exp(x)) to [*,3,exp(x)] and not to [*,3,[exp,x]]. Write a PROLOG function that will take a structured expression and turn it into a list that does not contain any structures, but only more lists that represent embedded structures. For instance, suppose we name the function to do this problem, us, for unstructure, then:
us(a*b+c*d,Y)
gives
Y = [+,[*,a,b],[*,c,d]]
and
us(3*exp(2*x+1),Y)
gives
Y = [*,3,[exp,[+,[*,2,x],1]]].
Of course, if univ is given a list, it will output the corresponding structure for the list, so using univ, write a PROLOG function to reverse the whole unstructure process.


12.9.
Write PROLOG predicates to take the derivatives of common functions. For instance, the derivative of some atom, X, with respect to X is 1:

   deriv(X,X,1) :- atomic(X).
where atomic is a predicate that tests for an atom. Another example would be that the derivative of the sum of two functions is the sum of the derivatives of the functions:
   deriv([+,U,V],X,[+,DU,DV]) :- deriv(U,X,DU), deriv(V,X,DU). 
In the above example we represented complex expressions in a list notation with the function at the start of the list. If U and V are arbitrary functions and C is an integer constant, write PROLOG rules to find the derivatives of at least the following functions:
1)
C,
2)
[-,U],
3)
[-,U,V],
4)
[*,C,U],
5)
[*,U,V],
6)
[/,U,V],
7)
[exp,U], (e to the power U),
8)
[power,U,C], (U to the power, C), and
9)
[ln, U], (the natural log of U).
The built-in PROLOG predicate, integer, can be used to test for an integer.


12.10.
PROLOG has often been promoted as a relational data base language. In the following exercises, use a data base of baseball games such as the following:

   game(1,april,7,cubs,4,mets,1).
   game(2,april,8,cubs,1,mets,4).
   game(3,april,9,cubs,9,cardinals,7).
   game(4,april,10,cubs,4,cardinals,3).
   game(5,april,11,cubs,1,astros,8).
You might want to generate data for the Cubs or for your favorite team with possibly up to 162 games for a full season. Write PROLOG functions to determine:

a)how many games the Cubs won, b) how many times the Cubs beat a particular team such as the Cardinals, c)how many games did the Cubs win in a particular month, d)what was the Cubs longest winning streak in general and e) what was the Cubs longest winning streak against a particular team. This should take into account that the Cubs may beat one team, say the Mets, then win or lose a number of games against some other team or teams and then win some more games against the Mets.

Of course, there may be other questions you want to program as well. All the above problems should be done recursively and without resorting to the looping-like method described in section 12.1.


12.11.
Produce a simple English language interface for the above problem so that users can type in questions like these:
How many times did the Cubs beat the Mets?
How many games did the Cubs lose in September?
To make it still more interesting, you could give you system the ability to handle follow-up questions as in this sequence:
How many times did the Cubs lose to the Cardinals?
( System gives a numeric answer )
When?
( System lists the dates )
No really sophisticated language understanding methods are needed to do this problem. Just create special ad-hoc solutions that work.


12.12.
Design (and program if you want) a PROLOG program that will keep track of a collection of compact discs. The example of using structures to represent the contents of cds in the first section of this chapter may be rather poor. You need to take into account that many cds will have more than one piece of music. Also take into account the possibility that different pieces of music on the same cd may be done by different orchestras and conductors. Take into account the fact that there can be more than one composer with the same last name. The method of accessing the PROLOG database given in the text was too awkward for ordinary users that do not know about PROLOG and the inner workings of the program. Produce a natural language interface like the one in the previous exercise that will make it easy to ask questions about the database of cds. If you don't have a cd or record collection available for data, consult a catalog for data.


File translated from TEX by TTH, version 2.60.
On 9 Feb 2000, 15:36.