程序代写代做代考 flex interpreter Excel data structure database chain Elm AI compiler algorithm Fortran prolog cache SQL Contents 1

40 Rules
then a warning will be issued for Y: singleton var# 1 in bird/1, where var# 1 means the first variable in the clause. By default, warnings are switched off. In order to be able to see warnings you must use:
?- warnings(on).
2.3 Rules for the car database
Returning to the car database used in the previous chapter, if we were developing a system to automatically put a given car into its correct insurance group, what sort of rules would we expect? It is common for a points system to be used. The points that a particular car gains are due to a variety of its attributes, and it is the number of points that determines its risk category or insurance group. For our first rule we will take the engine capacity as the relevant attribute: the higher the capacity, the more points the car will score. For example:
risk_for_capacity(Capacity, 1):- Capacity < 1000. risk_for_capacity(Capacity, 2):- Capacity >= 1000,
Capacity < 1300. risk_for_capacity(Capacity, 3):- Capacity >= 1300,
Capacity < 1500. risk_for_capacity(Capacity, 4):- Capacity >= 1500,
Capacity < 2000. risk_for_capacity(Capacity, 5):- Capacity >= 2000,
Capacity < 3500. risk_for_capacity(Capacity, 6):- Capacity >= 3500.
The points value is the second argument. Note that it does not need to be assigned in any way in the body of the rule which would be extremely poor Prolog style.
A single one of these rules is called a clause. A set of clauses all with the same head is known collectively as a single rule. Thus we have a single risk_for_capacity rule comprised of six clauses. It is quite usual for a large set of clauses to exist for a rule, all having the same head, as in this example.
All clauses for a rule should be contiguous to aid readability. If the clauses for a rule are separated by clauses for a different rule you will get a warning from the Prolog system.

Rules 41 The risk_for_capacity rule allows us to make the following type of query: How many
points does a capacity of 1800 get?
?- risk_for_capacity(1800, Points).
Which has the solution tree:
risk_for_capacity(1800,Points)
{ Capacity = 1800, Points = 4}
risk_for_capacity(Capacity,4)
1800 >= 1500 1800 < 2000 This shows the successful match with the fourth clause, which is achieved by backtracking each time one of the conditions fails in the first three clauses. Notice that the search strategy that has been given applies to backtracking over the clauses in the rules. In the above example: risk_for_capacity(1800, Points) is matched against the first clause, but then the right hand side of this clause, Capacity < 1000, fails and backtracking then allows the next clause to be tried. The solution tree gives us a diagrammatic representation of how a solution can be derived from the known rules and facts. The solution tree is a diagrammatic representation of the proof of the goal and as such is an extremely powerful mental model. You should try to draw solution trees whenever your understanding of a goal sequence is less than perfect. Being able to reliably draw a proof tree enables you to hand execute Prolog and this is a powerful test of your understanding. This is also a very useful exercise in conditions where you cannot test your code against a Prolog system, such as in an exam! Some guide lines on drawing solution trees will be given as we meet more complicated examples. We can find the points for risk_for_capacity for all cars by making the query: ?- car(Man, Model, Trim, _, Cc, _, _), risk_for_capacity(Cc, Points). We can define a rule that uses both the car and supplier facts. For example, we might need a rule that found the price and the supplier's address for a given car, where we supplied the manufacturer, the model, the trim and the capacity. price_and_address(Man, Mod, Trim, Cap, Price, Address):- car(Man, Mod, Trim, Origin, Cap, _, Price), suppliers(Man, Origin, Address, _). 2.4 Arithmetic Perhaps surprisingly, you can get a long way into Prolog before doing any arithmetic, which is generally the first thing you learn in any other computer language. To add or 42 Rules compute any arithmetic expression in Prolog you need to use the is predicate, which is used for arithmetic assignment. For example, the query: ?- X is (12 + 9). instantiates X to 21, in the same way that the assignment operators = or := may be used in other languages, with one very important difference, which will be discussed in the following chapter. The normal arithmetic operators are supported: * for multiply, / for divide, + for add and - for minus. In addition there are two bit-shift operators', << which performs a left-shift and >> which shifts right. These shift left or right the bit-pattern which represents the number to the left of the operator by the number of bits specified on the right of the operator, thus:
?- X is (1 << 1). /* 0001 << 1 = 0010 = 2 */ X=2 ?- Xis(12>>2)./*1100>>2=0011=3*/ X=3
Note the two ‘comments’ in the above code. Comments are introduced with /* and terminated with */. Such comments may extend over one or more lines, all text between the opening /* and the closing */ being ignored by the interpreter. Alternatively, a comment may be started with %, but will then only extend to the end of the line, thus there is no need for a termination character. The liberal use of comments is strongly recommended as an aid to program comprehension.
We can define a rule which determines the discounted price of a car using ‘is’ to do a simple bit of arithmetic. Say we are offering a 10% discount for cash:
discount_for_cash(Fullprice,Cutprice):- Cutprice is Fullprice * 0.9.
We’ll meet is again in the next chapter where we’ll discuss it more thoroughly.
Exercises 2
(1) The left hand part of a rule is called the rule __________ whilst the sub-goals on the right hand side are called the __________ of the rule.
(2) Draw the solution tree for the bird(X) query whose execution is shown traced in section 2.2.
(3) Experiment with the buys and bird rules, introducing your own facts and queries until you feel perfectly at home with them and can effortlessly predict the results of your queries.
(4) Put the following facts into Prolog’s database:

event(battle_of_hastings, 1066). event(plague_of_london, 1665). event(fire_of_london, 1666). event(man_on_the_moon, 1969).
Define a rule happened_before(X,Y) which defines the relation that event X happened before event Y, and use it to obtain all such pairs of events. You will need to use the system predicate <, less than. For example ?- (5 < 7). succeeds. Suitably instantiated variables can be used either side of < instead of numbers. Start the rule with 'happened_before(X,Y) :-'. (5) Tom dislikes anyone in the third year who likes Dave. Dave only likes hard workers and first years. Pete and Nigel are in the first year, Sam and Jane are in the third year. Sam and Pete dislike Dave and like Tom. Jane likes Dave. Pete, Nigel and Jane are all hard workers. Use Prolog to express the facts and rules (remember to start the students' names with a lower-case letter) and find out: Who does Tom dislike? (6) Introduce the following car facts into the database alongside those we have met previously: car(ford, capri, injection,uk, 2800, sports, 11200). car(alfa_romeo, sprint, veloce, italy, 2000, coupe, 12500). car(volvo, 928, gls, sweden, 1400, hatchback, 6290). car(mitsubishi, colt, glx, japan, 1800, estate, 7420). car(mercedes, roadster, 280, germany, 2800, convertible, 18450). Write a set of facts that gives points for the type of car body according to the following table: Rules 43 type points estate 1 saloon 2 hatchback 1 sports 3 coupe 5 convertible 7 (7) Write a rule that uses the facts and the risk_for_capacity rule already given to give the total points scored by a car for engine capacity and body type. This will entail 44 Rules adding together the points for the capacity and the points for the body type. The car is to be identified by the manufacturer and model. 3.1 Simple example of recursion Recursive rules are simply rules which call themselves. Defining a rule in terms of itself can lead to very elegant and concise programs. Many mathematical functions can be expressed recursively, the most common example being the factorial function denoted by an exclamation mark. But before doing the factorial example, we will look at one of the simplest examples possible that involves recursion. The problem is to move the cursor a given number of spaces towards the right of the screen, and we might use this rule to format our output. Such a function is commonly called tab, short for tabulate. However, there is already a built-in predicate called tab so we will call our rule spaces. An example of its use is: write_headings:- spaces(20), writeln('MANUFACTURER MODEL PRICE'). (Notice that I am assuming writeln has been defined.) This rule would move the cursor 20 spaces to the right before printing the text and going to a new line. Remember from the preceding chapter how to assign a numeric value to a variable: this is effected by the is predicate, which we will now explain a little more fully. The is built-in predicate is an 'infix' operator, that is it comes between its arguments, e.g. ?- X is 29, writeln(X). ?- X is 777 * 5, writeln(X). The fact that it is defined as being infix is a matter of convenience. It might have been defined as 'prefix', i.e. coming before its arguments. All the predicates we've used so far have been prefix, the 'car' predicate for example. If is were to be prefix the first of the above queries would need to be written as: ?- is(X,29),writeln(X). It is obviously more convenient to use the infix form. Notice that an infix operator or predicate must have precisely two arguments. 3 RECURSIVE RULES Recursive rules 45 46 Recursive rules As stated in the preceding chapter, is is rather like = in other languages. However, the left-hand side of is must be an uninstantiated variable, i.e. it must not already have a value, or must be equal to the value of the expression to its right. This is known as 'non-destructive assignment which is really a consequence of logic which insists that we cannot arbitrarily reassign values to variables which might change the truth value of a statement. Thus, the following query: ?- X is 4, write(X), X is X + 1, write(X). will fail at the X is X + 1 sub-goal because 4 is not 5. We will shortly see how to get round this where we need to increment a numeric value. Remember that, although = is defined in Prolog, it does not have the meaning of assignment, so if you use it where is is required you will not get the desired result! A query such as: ?- X = 1 + 2. will result in Prolog replying: X=1+2 as = is used as a 'matching' operator, as detailed in Chapter 2, and here causes X to be matched to 1 + 2 which is a structure, something we will see a lot more of in later chapters. All recursive programs, whether written in Prolog or some other language, have two basic parts. The first consists of what to do when there is to be no more recursion, which we call the 'boundary case'. For this example, the boundary case is when there are no more spaces to be printed. The other part consists of what to do in the general case, followed by some alteration to the parameters and then a call to the same rule or sub-program. In a conventional language we would distinguish the two cases within the same program by using an 'if..then..else..' type of statement, but in Prolog we use unification (the matching of the arguments) to select the correct clause. We start the rule by considering the boundary case for spaces, i.e. the case where there is nothing to do. This is when spaces(0) is the sub-goal. Here we simply want the query to be satisfied and nothing more to happen. Therefore the first clause of our rule is: spaces(0). This will clearly match with spaces(N), whenever N is instantiated to 0, and cause nothing to happen because there is nothing in the clause's body to execute (a fact is nothing other than a clause without a body). In the general case, we need to write a space and then re-invoke spaces with an argument that corresponds to a count of one less space, e.g.: spaces(N):- N > 0,
write(‘ ‘),

M is N – 1,
spaces(M).
The first sub-goal makes sure the number represented by N is valid: this is good programming practice and may prevent unwelcome results. Consider what would otherwise happen if N were inadvertently instantiated to a negative number.
To illustrate how this rule works, consider the query:
?- spaces(2).
(1) This matches the second clause, so a single space is printed, then, (2) M is calculated to be 1 and spaces(1) is called.
(3) spaces(1) matches the second clause and so another space is printed, then,
(4) M is calculated to be 0 and spaces(0) is called.
(5) spaces(0) is satisfied by the first clause and the query has been satisfied
completely.
Note how a different variable to N is used for the calculation of the argument to the next call of spaces, to circumvent Prolog’s non-destructive assignment: attempting to use N is N – 1 would fail. As a general rule, whenever you want a new value based on that of another variable, such as incrementing and decrementing numbers, then use a new variable for this value.
The solution tree for the query is:
spaces(1)
Recursive rules 47
2 > 0
write( ‘ ‘)
spaces(2) spaces(N)
M is 2-1
1 > 0
{N = 2}
spaces(N)
write(‘ ‘)
{N = 1}
M is 1-1
spaces(0)
spaces(0)
Notice how I have indicated the unifications in curly brackets, the variables in the subgoals beneath the unification are then shown to reflect the result of this unification.

48 Recursive rules
Writing out the unifications explicitly helps us in eliminating errors. It makes the process of drawing such a tree more mechanical and hence less error prone.
Recursion causes severe difficulties for some people as they fail to understand how a function can be executing more than once at any one time. Well this is really looking at the problem the wrong way. Each call to a recursive procedure is using a copy of the original procedure which to all intents and purposes could just as well be called something different. i.e. the recursive calls could be to spaces1 and then spaces2 and so on. If they were called spaces1, spaces2, there would not be, of course, any recursion, and therefore nothing to get confused about! It is vital to realise that the recursive calls are using copies of the original, each of which has its own set of variables and its own position in the execution path to return to. There is nothing inherently complicated about recursion, its just that we get over familiar with how non- recursive calls work which gives us an incomplete mental model which is hard to extend to the recursive cases.
3.2 Calculating factorials
Now for the more complicated factorial example.
For people who haven’t heard of the factorial function, the factorial of a number is the number obtained when you take the number and multiply it by one less than the number, and then by two less, etc. until you reach zero, and is denoted by the exclamation mark. So:
5! = 5 * 4 * 3 * 2 * 1 = 120
By convention, 0! is taken to be 1.
The recursive definition of factorial function is:
N! = N * (N – 1)! 0! = 1
which we can read as: the factorial of a number N is N times the factorial of N – 1, and the factorial of 0 is 1. It should be fairly clear that this information is just exactly enough to calculate any factorial number. For instance, to calculate 4! using this definition and absolutely no insight, we might calculate as follows:
Using first statement: Using first statement: Usingfirststatement: Usingfirststatement: Usingsecondstatement: Using multiplication:
4!=4*3! 4!=4*3*2! 4!=4*3*2*1! 4!=4*3*2*1*0! 4!=4*3*2*1*1
= 24
(The definition assumed that we knew how to multiply).
In Prolog we cannot define a function whose name returns a value, as we can in other languages, such as in:
X = fact(Y).

Recursive rules 49
so we use another argument for the value to be returned, which makes it look more like a subroutine or procedure than a function.
We first define the factorial of 0 as 1:
fact(0, 1).
This is the boundary case. Always start defining a recursive rule be considering the boundary case, it makes defining the recursive part very much easier as you can see what the recursion needs to be aiming at. Each step of the recursion, i.e. each recursive calll should take you one step nearer to being satisfied against the boundary clause.
Then we use the first part of the definition to give us the rule:
fact(N, X) :-
N > 0,
X1 is N – 1,
fact(X1, X2),
X is N * X2.
Again we check that N is in the range that we wish this clause to deal with. This follows the definition very closely. It looks rather different because we have to re-express it in the syntax of Prolog. We can now ask Prolog to calculate a factorial by a query of the form:
?- fact(3, X).
Let’s hand trace the execution of this query:
(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11)
fact(3, X) matches with fact(N, X) with N = 3. Sub-goal N > 0 succeeds.
Sub-goal X1 is N-1 instantiates X1 to 2. Sub-goal fact(2, X2) is called.
fact(2, X2) matches with fact(N, X) with N = 2. Sub-goal N > 0 succeeds.
Sub-goal X1 is N-1 instantiates X1 to 1. Sub-goal fact(1, X2) is called.
fact(1, X2) matches with fact(N, X) with N = 1 Sub-goal N > 0 succeeds.
Sub-goal X1 is N-1 instantiates X1 to 0

50 Recursive rules
(12) (13) (14) (15)
Sub-goal fact(0, X2) is called.
fact(0, X2) matches with fact(0, 1) with X2 = 1. Sub-goal X is N*X2 instantiates X to 2.
Sub-goal X is N*X2 instantiates X to 6.
Notice how I have used indentation to show the ‘depth’ of the solution process.
It is a useful tip always to define the boundary condition before the general case. This can prevent infinite recursion. It is possible for the interpreter to carry on using the general case when it matches on the boundary case as well, if it finds the general case first! If the boundary condition is always before the general case, you know that the interpreter has got to check whether it matches with the boundary case every time ’round’ the recursion regardless of whether a match with the general case is possible. This is commonly known as ‘defensive programming.’ Every effort made in making our rules ‘safe’ will be amply rewarded in the long run.
No sane programmer would calculate factorials this way, a look up table is considerably more efficient, but it does demonstrate a very simple use of recursion. In Prolog we have to use recursion to achieve what we would often use a loop to do in other languages, there being no iterative construct such as Basic’s FOR … NEXT.
Exercises 3
(1) Draw a solution tree for the query ?- fact(3, X), using the hand trace given in the
text as a guide.
(2) Construct a database containing facts about the relations father and mother such as:
father(harold, charles). mother(harold, diana). father(charles, philip). mother(charles, elizabeth).
but covering a few more generations. Make up the names if necessary. Then define the recursive relation ancestor(A, B) which can generate the ancestors of A. (An ancestor is (i) a father, (ii) a mother, (iii) an ancestor of (i), (iv) an ancestor of (ii)).
(3) Define a predicate mod5(X, Y) which instantiates Y to X mod 5 by recursively subtracting 5 from X. (X mod 5 gives the remainder when 5 is divided into X as many complete times as possible, for example 23 mod 5 = 3). Start this by defining the boundary case first, (this is where X <= 5). (4) Define a predicate power(X, N, P) which instantiates P to X raised to the power N (where N is an integer). Remember X to the power 0 is 1. Start by defining the boundary case. Recursive rules 51 (5) Define a predicate that converts a number of minutes into the corresponding hours and minutes by recursively subtracting 60 from the number of minutes and incrementing the number of hours. An example of using the rule is: ?- mins_to_hours_and_mins(124, H, M). H=2 M=4 4 SURVIVAL PREDICATES This chapter introduces some basic built-in predicates which will help you generally as your use of Prolog becomes more advanced and you start to experiment with your own code. The type checking predicates are particularly important in writing defensive code and should be used liberally to aid your debugging. I’ve also introduced assert and retract in this chapter which are predicates that can be used to alter the contents of Prolog’s database whilst the program is running. These have been introduced as you are almost certain to find them being used in example programs from other sources that you may want to try. 4.1 Accessing the operating system on the PC On the PC under DOS you can temporarily return to the operating system by using the predicate shell. This does not apply to Windows where you will find double clicking on the DOS icon from the Program manager a far more convenient way of running DOS. For example to exit to the operating system when running Prolog from DOS, type: ?- shell. To return to Prolog, type "exit" C:\PROLOG>
You may then pass commands to the operating system and run other programs in the normal way. After each command is run you will be reminded that you have suspended Prolog, and of how to resume, by the prompt ‘To return to Prolog type “exit”‘, as illustrated above. Typing exit, followed by , will return you to the interpreter at the same point at which execution was suspended. During the period between executing the shell goal and returning to Prolog the interpreter will remain in memory, thus the memory available in which to run other programs will be reduced by that consumed by Prolog.
You can examine the contents of your directory, or execute any other single operating system command from within the interpreter, by using the system command. For example:
Survival predicates 53

54 Survival predicates
?- system(‘dir /w’).
will display the contents of the current directory down and across the screen. Programs initiated through the system command will have available memory reduced in the same way as for shell. As for shell, system is not available from Windows Prolog.
Additional functionality can be gained by using system with strings constructed using Prolog that write to temporary files, then processing these files using Prolog, as demonstrated by edit later in this chapter.
4.2 Accessing the operating system on the Archimedes
The system predicate allows CLI commands to be executed from within Prolog. Note that no text output will appear in the Kprolog window, so only those CLI commands that manipulate files, directories or environment variables are appropriate. The system predicate is dealt with in more detail in the appendix for Archimedes users.
4.3 Retracting, clearing and abolishing
A fact may be retracted (removed) from the database by using the predicate retract(X). It has one argument which must be instantiated to the fact you would like to remove, e.g.:
?- retract(falcon(kestrel)). yes
Listing the database will show that the fact has been removed. Note that the fact has been removed for good: backtracking will not undo the retraction, although it can be replaced by either using assert(X) (see below) or by typing it directly into the database using ?- consult(user).. The argument of retract does not need to be fully instantiated to the fact, the functor (head) is sufficient, the arguments are used for unification with candidate clauses for retraction. For example:
?- retract(falcon(X)).
would retract the first match with falcon(X) and would also cause X to become instantiated to kestrel in the above example, if we take falcon(kestrel) to be the first entry in the database with the functor falcon.
A set of clauses which have the same head, or functor, may be deleted by using the abolish(X) predicate. For example, if the database contains:
falcon(kestrel). falcon(peregrine). crow(magpie).
then entering:
?- abolish(falcon).

Survival predicates 55
will delete both entries for falcon and leave the one for crow. The abolish predicate simply searches for occurrences of the functor. We can restrict the number of clauses removed by specifying the arity of the clause(s). The arity of a clause is simply its number of arguments, so our falcon clauses have an arity of one, whereas the facts for the ancestor relation in the preceding chapter have an arity of two. For example:
?- abolish(falcon, 1).
retracts all clauses having the functor falcon and one argument. retract and abolish are equally happy to delete rules as well as facts, so be careful!
4.4 Asserting
Facts and rules may be added (asserted), by using one of the assert predicates, assert(X), asserta(X) and assertz(X). The difference between them is that asserta asserts to the start of the database, while assert and assertz assert to the end of the database, e.g.
?- asserta(falcon(kestrel)).
would make falcon(kestrel) the first falcon fact in the database.
Excessive use of assert, asserta, assertz and retract tends to make Prolog programs very difficult to read and understand. This is because they effectively modify the program, and thus tend to destroy the declarative reading of a program. Relations which are true at some points are not true at others; clauses, and, indeed, rules may come and go as program execution proceeds. This causes a reading of the program, which necessarily sees it in a static state, to need to consider the procedural implications of the ‘asserts’ and ‘retracts’ (the dynamic effects of the alteration of the database).
A program without asserts and retracts can be very effectively read because of the declarative nature of the rules and the lack of procedural implications. So it is worth noting that we might be giving up a very useful feature of Prolog when we use assert and retract.
It is strongly suggested that the reader avoids using these predicates whenever possible. You certainly should not use assert and retract for communicating information that would normally be passed by a rule’s parameters. A legitimate use is for the same kind of reason we would use a global flag in a conventional language to signal a condition of global interest. We also use assertz and retract for counting the number of occurrences of facts or particular solutions. For example, we might wish to find out how many falcons are defined in our database. This is the usual technique for counting the number of times a goal succeeds, so for our example we would call count(falcon(X),N):
count(Goal,N):- assertz(count(0)),
count1(Goal), retract(count(N)).

56 Survival predicates
This initialises the counting process by asserting a count of zero, calling a sub-goal to do the main part of the counting (which will be a ‘failure driven loop’), and finally the state of the last count is retracted to give the number. The rule for count1 is:
count1(Goal):-
call(Goal),
retract(count(N)), M is N + 1, assertz(count(M)), fail.
count1(_).
call(X) is a convenient built-in predicate for calling a Prolog goal which we want to represent as a variable and instantiate at run-time. In our example, Goal would be instantiated to falcon(X) and call(Goal) would be equivalent to falcon(X). Here we have used fail as the last goal to force every possible solution of Goal to be evaluated and for each solution we retract the current count, increment it and assert the new count. Ultimately we fail and backtrack into the second clause for count1 which succeeds immediately.
Another convenient use is for what is sometimes called ‘solution caching.’ This is where we have taken considerable effort (or rather our program has) to get a solution to something, we know we will need this solution in the future, and we do not wish to have to go through the same trouble to get it. For instance, if I am interfacing to an external database and I need to access a particular table, then I will need to get the data dictionary information to enable the access. Rather than fetch this information each time I need it, I can cache it by asserting it to the internal database. Then, whenever I need data dictionary information, I look in the internal database first: only if it is not there do I then go and fetch it.
4.5 Editing on the PC under DOS
It is an easy matter to define a predicate which invokes an editor, which then lets you change the contents of a file, and then reads the file into Prolog’s database. This means that we can edit and re-read our rule base without having to stop and restart Prolog.
A useful predicates for reading files, typically containing Prolog programs, into the interpreter is reconsult(F), where F represents the name of the file in each case. Clauses read from a file through reconsult are always added to the database whenever clauses of the same functor and arity are not present in the database. However, if clauses having the same functor and arity are present in the database as any found in the file being read these will be replaced by the new versions. Historically there is also a built-in predicate called consult which is identical to reconsult.
This is how you may define your own version of edit:
edit(File):-
name(File, Flist),
append(“vi “, Flist, L), name(S, L),

system(S),
reconsult(File).
This edit rule is given a single parameter which is the filename of the Prolog source code. Thename(A,L)built-inpredicatetakesasitsfirstargumentanatom,thesecond argument is a list of the ASCII codes that make up the atom, and Prolog expects that either one, but not both, will be instantiated. Examples of its use are:
?- name(fred, X).
X = [102,114,101,100]
?- name(X, [102,114,101,100]).
X = fred
?- name(fred, [102,B,101,C]).
B = 114 C = 100
The square brackets, [], enclosing the ASCII codes are simply Prolog’s way of writing a list: lists will be covered in detail in Chapter 7, but note here that a string enclosed in double quotes in Prolog is equivalent to the list of its ASCII codes: thus “vi ” is another way of writing [118,105,32]. The rule append( L1, L2, L3) concatenates, or joins, lists L1 and L2 to form list L3 (see section 7.3), so the edit rule takes the list of ASCII codes corresponding to ‘vi ‘ and concatenates it with the list of ASCII codes which corresponds to the file name, to form list L. Then, using name it turns this ASCII list into an atom and calls system with it. This will invoke the editor with the filename you gave edit.
When system is finished, i.e. when you finish editing, the file that has just been edited is reconsulted, thus, as explained above, any existing definitions of rules in the file being reconsulted are removed from the internal database before adding the ones in the file to the database. This is exactly what we require in an editing situation where we wish to replace the old version of rules with the newly edited version.
If you intend using edit frequently then define a file called prolog.ini in your Prolog directory, or one on an append path, and put the definition for edit into it. This file will then be consulted every time you invoke Prolog (see also section 1.5, Initialisation file).
4.6 Spy points
How to trace Prolog’s execution using the built-in predicate ‘trace’ was described in Chapter 3. This described the debugger in ‘trace’ mode which gives complete trace information starting from the query goal. This will quite often produce far too much information for convenient analysis. More control over the tracing facility can be obtained by setting so-called spy points on particular predicates in our code. When we set a spy point on a particular predicate, the debugger will work in ‘debug’ mode, that is execution will proceed without trace information being output until the predicate with the spy point is called. At this point the trace debugging mode is entered. If we subsequently use ‘run’ then execution will continue without debugging information until
Survival predicates 57

58 Survival predicates
the next spy point is reached. We can set spy points on predicates by using the built- in predicate ‘spy’ giving the predicate name as the only argument. For example:
?- spy(count1).
We can set as many spy points as needed by calling spy for each spy point we want. Spy points can be removed one at a time by using nospy, giving the name of the predicate for its argument, or all at once using nospyall.
4.7 Declaring operators
The ‘op’ predicate allows us to define new Prolog operators, which are either infix (coming between their arguments), or prefix (coming before their argument). We have already met some examples of infix and prefix operators, as well as the usual arithmetic operators which are generally infix. Note that ‘:-‘ is an infix operator coming between the head and body of a rule and ‘?-‘ is a prefix operator coming before a query.
Declaring certain Prolog functors as infix and prefix can dramatically improve the syntax of our Prolog clauses in certain situations. There are many examples of the use of ‘op’ in the chapter on Expert Systems where it is used to implement a natural syntax for defining expert system production rules.
It is also necessary to specify an operator’s precedence and associativity. The precedence determines the order of evaluation when used in a situation that would otherwise be ambiguous. The precedence is a number in the range 1-1200. For example, when the expression ‘a+b*c’ is evaluated the multiplication is done before the addition because the plus is declared internally in the Prolog system to have a higher precedence than multiplication. The precedence can be thought of as specifying how tightly binding the operator is to its arguments. The lower the precedence, the more tightly binding it is. It is also necessary to specify the associativity. This is for situations where the same operator (functor), or operators with the same precedence, are used more than once in an expression without brackets. In the case of infix operators it specifies whether the expression to the left of the operator should be evaluated before or after the expression on the right. This information is supplied by providing a pattern for the operator, taking one of the following forms:
fx, fy, xfx, xfy, yfx, yfy
The ‘y’ indicates the expression to be evaluated first, the ‘x’ indicates the evaluation of the expression is to be ‘delayed’. Where the evaluation of expressions is not an issue, we can think of the precedence and associativity as providing the necessary information for translation into normal Prolog clauses. The principal functor will be the operator with the lowest precedence. For example ‘a+b*c’ translates to ‘+(a,*(b,c))’, and if ‘+’ is declared as having associativity ‘yfx’ then ‘a+b+c’ translates into ‘+(+(a,b),c)’.
Some simple examples of the use of ‘op’ are:
?- op(40, fx, with).

yes
?- assert(with tom).
yes
?- with X.
X = tom
yes
?- op(60, xfy, and).
yes
?- assert(beer and skittles).
yes
?- X and Y.
X = beer
Y = skittles
yes
You may find it useful to declare the editing predicate which we defined earlier, ‘edit’ as prefix. This will save you the need to provide brackets around the file name. For example:
?- op(40, fx, edit).
?- edit example.
You will need to change the definition of ‘edit’ to use prefix notation.
4.8 Type checking
In the previous chapter the rules for ‘spaces’ and ‘fact’ had a check on the argument of the form ‘N > 0’ to ensure that a legal value was being passed. If the rules were to be passed a term that was not a number this would cause an exception to be raised (Prolog would produce an error message) at run time which would inform us of the type clash. This is very useful when debugging our programs, but it is often much more desirable to check that arguments are what they should be within the code. There are a number of built-in predicates that do this which are summarised in the following table:
Survival predicates 59
Built-in
Succeeds when argument is
var/1
variable

60 Survival predicates
nonvar/1
not a variable
atom/1
atom
atomic/1
atom or number
integer/1
integer
real/1
floating point
number/1
integer or float
We can use these predicates to validate arguments and where they cannot be validated we can either silently fail or use an additional clause to write an error message. They all take a single argument which is indicated by the ‘/1’.
4.9 Comparing terms
We have already seen how arithmetical expressions can be compared with the usual operators ‘>’, ‘<', '>=’, ‘=<'. It is also possible to compare any two terms. There is a standard ordering for terms where variables come before numbers, which come before atoms, which come before compound terms. Older variables come before newer ones. Numbers are treated in numeric order, where there is an integer and float of the same value the integer comes first. Atoms are in alphabetical order. Compound terms are principally ordered by their number of arguments. Where two compound structures have the same number of arguments the ordering is by the principal functor and then by the arguments. The available operators for comparing terms are: '@<', '@=<', '@>‘ and ‘@>=’. Examples are:
? – X @< 46. yes ?- 46 @< tree. yes ?- tree @< tred. no ?- tree @< a(X). yes ?- a(X) @< a(f). yes ?- a(X) @< a(X,f). yes Exercises 4 (1) A Last In First Out stack (often called a LIFO stack), is a data structure that allows us two basic operations: push and pop. We use push to put a new element on the top of the stack. We use pop to remove the top element from the stack. Elements belonging to the stack can be represented in Prolog by using facts with the functor stack. Show how push and pop can be implemented in Prolog, using asserta and retract, by defining rules for push and pop. This is an example of their use: ?- push(item1). ?- push(item2). ?- push(item3). ?- pop(X). X = item3 ?- pop(X). X = item2 (2) Define a rule which will give the current size of the stack being used in question (1). This will need to use the count rule to count the number of stacked entries in the database (3) Define a rule which will clear the current stack. This will best be implemented using the built-in predicate abolish. (4) Add a subgoal to the factorial rule which checks that the argument is an integer and add a clause that produces an error message if the argument is not an integer. Survival predicates 61 5.1 Matching variables with structures 5 STRUCTURES Structures 63 The data structures of Prolog are called terms and are comprised of a functor and a number of components, which may be simple constants and variables as we have met already and collections of these items. The simplest kind of structure is of the form falcon(kestrel), where falcon is the functor of the structure and the constant kestrel is its single component. We can think of this as a record called falcon with one field. Structures can have more than one component, or field, as we have already found out, but structures can also have structures occurring as components, such as: car(body, engine(pistons,crank)) The depth of the nesting of structures within each other is virtually unlimited. Car is a structure of arity two. A single structure is comprised of its functor, its opening bracket, and all the components up to the corresponding closing bracket. The pattern matching technique, unification, will allow variables to be matched not only with constants but with any structure. To see how this works enter the following fact into Prolog's database: car(body, engine(fuel_system,electrics(battery,starter,lights))). We can think of this as a record describing the hierarchical relationship between some components of a car. If it helps, think of it as a tree, with the functor as its root: 64 Structures car body engine fuel system electrics battery starter lights We can now query the car database containing this one fact: ?- car(X, Y). X = body Y = engine(fuel_system,electrics(battery, starter, lights)) Here Y has become instantiated to the entire structure having the functor engine. It is very important to understand that a variable can match any structure at all, regardless of how complicated the structure is. In much the same way, a structure occurring in a query can match a structure occurring in the head of a rule. For example, we might have a rule for calculating the tax payable given a structure of the form salary(Gross,Taxrate): get_tax(salary(Gross,Taxrate), Tax):- Tax is Gross * Taxrate. This can then be queried with: ?- get_tax(salary(12000,0.25), X). X = 3000.0 5.2 Matching structures with structures Consider the query: ?- car(_,engine(X,Y)). taken with our second example concerning the car engine. Here we are trying to match the structure engine(X,Y), which occurs in the query, with the structure engine(fuel_system,electrics(battery,starter,lights)) which occurs in the fact. As you might expect, this succeeds, with X matching fuel_system and Y matching the structure electrics(battery,starter,lights). So the answer to the query is: X = fuel_system Y = electrics(battery,starter,lights) We might say we have picked out the two components of 'engine'. We can go as deep as we like into the structure in order to pick out the components that interest us. For example: ?- car(_, engine(_,electrics(Z,W,Q))). Z = battery W = starter Q = lights Notice that where we are trying to match two structures, they can only be matched, or unified, if they have the same functor, and their components can be matched. We cannot use a variable in place of the functor name, and therefore cannot make queries of the following type: ?- car(W, X(Y,Z)). Exercises 5a (1) What are the arities of the following structures: (a) f(g(h(i))) (b) cord(Y, Y,ab(X)) (c) X is 6 + 19 (2) Give the instantiations that occur when the following pairs of structures are unified, ie give the complete component that each variable becomes instantiated to: (a) bicycle(frame, wheels(spokes,hub),handlebar) with: bicycle(X, Y, Z) (b) document(preface, Y, chapter(Z), index) with: document(X, contents, chapter(section(paragraph)), index) Structures 65 66 Structures 5.3 Examining and building structures Structures can be examined and manipulated using the predicates functor(T,F,A) and arg(N,Term,A). A goal functor(Term,Functor,Arity) will be true if Functor is the functor of term Term, and Arity is its arity, thus: ?- functor(electrics(battery,starter,lights), F, A). F = electrics A=3 ?- functor(Term, electrics, 3). Term = electrics(_28102,_28103,_28103). In the first example, Prolog is passed a simple structure and returns its functor and arity. In the second example, it constructs a 'general' term with the functor electrics and three uninstantiated variables as its components. A goal arg(N,Term,Comp) will be true if component Comp is the Nth component of term Term, thus: ?- arg(2, electrics(battery,starter,lights), Comp). Comp = starter ?- functor(Term, electrics, 3), arg(1, Term, battery), arg(2, Term, starter), arg(3, Term, lights). Term = electrics(battery,starter,lights) In the first example we ask Prolog for the second component, Comp, of the electrics structure. In the second example, we use functor to construct a term with functor electrics and with three uninstantiated variables as components, then use arg to instantiate these components. 5.4 Searching trees A commonly used data structure in Computer Science is the tree. It is used to store information in a particularly ordered fashion to facilitate the connections (relationships) between various parts of the data. Many things in the natural and scientific world form tree structures. We also find tree structures in human affairs, for example, a management structure. We can define a tree in terms of its nodes. The nodes are the parts where the information is kept. For the management example, a node would probably contain the name of the person and who he was in charge of. For the sake of simplicity we are going to limit our discussion to what are known as binary trees. A general type of tree could have any number of branches from a node leading to other nodes, whereas a binary tree always has exactly two. Thus, each of our management tree records, or Structures 67 terms, will be a structure containing two components: the first being a constant (the person's name), and the second, a structure with two components (as we are limiting ourselves to a binary tree): the names of the two people he manages. The node right at the top of the tree (Computer Scientists and genealogists have always imagined trees to grow downwards) is known as the 'root node'. For our management example the root node is: management_tree(adams, manages(brown,collins)). The facts for 'brown' and 'collins' are: management_tree(brown, manages(dorking,evans)). management_tree(collins, manages(fortnum,gault)). To keep this example to a manageable size, we'll end our tree with facts for 'dorking', 'evans', 'fortnum' and 'gault'. These introduce 'null' which stands for 'no one'. management_tree(dorking, manages(null,null)). management_tree(evans, manages(null,null)). management_tree(fortnum, manages(null,null)). management_tree(gault, manages(null,null)). Here is our management database in 'binary tree' form: dorking adams brown collins evans fortnum gault We can write a Prolog rule to navigate through the tree structure in various ways. One way is known as pre-order. This is where we start at the root and list the left 'manages' node, and then the left 'manages' node of that 'manages', until we reach null, when we list the right 'manages', and then the right 'manages' of the parent and so on. It is a left to right, depth first method of listing nodes. It is succinctly described as the root node followed by the left 'manages' node in pre-order followed by the right 'manages' node in pre-order. ThistranslateswonderfullyeasilyintoProlog(wemustincludetheboundary case as the first clause): preorder(null). preorder(Name):- management_tree(Name, manages(NameS1,NameS2)), writeln(Name), preorder(NameS1), preorder(NameS2). In response to the query: 68 Structures ?- preorder(adams). Prolog will give us: adams brown dorking evans collins fortnum gault yes Here’s the first part of the solution tree for this query. This is a good example for drawing a solution tree as it is quite complex, but try to see this as a mechanical process. We start with the query at the top and write the match with the head of a rule underneath, we note the instantiations in curly brackets. We then proceed left to right through the subgoals remembering to make the necessary substitutions for the variables that have become instantiated. When we have written the subgoals for a clause, we take the left most subgoal and complete the solution tree for it, before moving on to the next subgoal. It is then just a matter of repeating the process for each subgoal. I have shortened some of the symbols in the tree for space reasons: preorder(adams) { Nm = adams } preorder(Nm) m_t(Nm, manages(N1,N2)) writeln(adams) { N1 = brown, N2 = collins} m_t(adams, manages(brown,collins)) m_t(Nm, manages(N1,N2)) writeln(Nm) preorder(N1), { Nm = brown } preorder(Nm) preorder(N1), preorder(N2) preorder(N2) The unconnected lines show where the tree has not been completed. You should try to complete this tree on paper. Take notice that where adams is written and the next goal to be solved is preorder(N1) that at this point N1 is instantiated to brown Structures 69 because of the unification of the first subgoal m_t(Nm, manages(N1,N2)) with the ground clause. Exercises 5b (1) For the following structure, name all the functors and components. sentence(noun_phrase(adjective,noun), verb_phrase). (2) A single user computer can be represented by a structure having the following fields: cpu, which is a structure containing components for make and model; memory; disk, which is a structure containing components for type of disk (floppy or hard) and capacity; finally there is a component for the monitor type, which is a structure with components for the resolution and monochrome/colour indicator. Write several facts in Prolog which conform to this structure. Using a query which uses assertz, create new facts corresponding to that part of the structure which concerns the disk. (3) A post-order listing may be achieved by taking a node and listing the left 'manages' in post-order and then the right 'manages' in post-order followed by the node itself. Define a rule 'postorder' which will list any part of the management structure, given at the end of this chapter, in post-order. (4) Add a parameter to the pre-order or post-order rule which serves to indicate the depth within the management tree. Use this to obtain an indented version of the management tree. i.e. your output, for ?- preorder(adams)., should look like: adams brown dorking evans collins fortnum gault yes 6.1 Defining a list A very useful data structure in Prolog is the list. In fact it is just a structure, but it has been given a syntax which makes it particularly easy to use. Lists in Prolog are very much what we commonly understand by lists in normal use. If you have used LISP then you will be familiar with the idea already. Also a singly linked list a might be defsined in a onventional language is much the same. Any list in Prolog is surrounded by square brackets, and the individual entries of the list are separated by commas. Here is a list of towns as it might be written in Prolog: [coventry,leeds,bradford,rugby,sheffield] However, we cannot enter such a list into Prolog's database without it having a functor, such as: towns([coventry,leeds,bradford,rugby,sheffield]). Enter it into the data base and make the following query: ?- towns(X). The interpreter will respond with the list [coventry, etc...] that has been associated with the functor towns. Only a variable or another list can match with a list. A list may consist of a single element, as in: towns([sheffield]). or no elements at all: towns([]). [] is called the empty list or sometimes the null list. Lists 71 6 LISTS 72 Lists 6.2 Heads and tails To get at individual components of a list we have a convention that lets us distinguish the first element(s) of a list from the remaining list: this is achieved by the character | which you will normally find on the far right- or left-hand side of your keyboard. To see how this works, type the following queries: ?- towns([X|Y]). ?- towns([X,Y|Z]). The response to the first query will be: X = coventry Y = [leeds,bradford,rugby,sheffield] The response to the second query will be: X = coventry Y = leeds Z = [bradford,rugby,sheffield] What the | does is to make what occurs on the left of it become instantiated to the head, or first element(s) of the list, and what is on the right of the | to become instantiated to the tail or remainder of the list, which is itself a list. So, if you type the following you will get all of the list except 'coventry': ?- towns([_|Y]). Note that, because the tail of a list is itself a list, whatever is on the right hand side of the |, if it's not a variable, must use list notation. Or put another way, what is on the right of the | must be capable of matching with a list, i.e. it must either be a variable or a list. The following query will therefore produce a syntax error: ?- towns([X|Y,Z]). If we want the second element of a list we could write: ?- towns([_|[Y|_]]). This works because the tail of a list is also a list, so can be treated in the same way as the first list, ie it can be broken into its head and tail using the [H|T] construct. This does not look like a very nice way of getting the nth element of a list, but it's easy to define a predicate that will do it for us using only what we know already. Specifically, we would like to define a predicate to write the Nth element of a list, given the list and the number 'N' of the element. We start by defining the 'boundary case', that is, how we get the first element: The majority of errors made by the newcomer to list processing (whether using Prolog or Lisp) are due to not distinguishing between dealing with a list (or the tail of a list) and an element of a list. Take great care to make this distinction and you will save yourself a great deal of trouble. getnth([X|_], 1) :- writeln(X). This will clearly write the first element of a list. Now we try to define the general case so that it will naturally work backwards to the case we have just defined, in much the same way as the factorial function did, thus: getnth([X|Y], N) :- N > 1,
N1 is N – 1,
getnth(Y, N1).
This recursively discards the head of the list N – 1 times at which point the first clause is called because of the match with the number 1. To see how this works it is easier to consider a concrete example. Take the query:
?- getnth([coventry,leeds,bradford,rugby], 3)
and manually trace its execution like this:
(1) Query matches on second clause, with X = coventry, Y = [leeds,bradford,rugby], N = 3;
(2) N > 1 succeeds;
(3) N1 is N – 1 instantiates N1 to 2;
(4) getnth([leeds,bradford,rugby],2) is called;
(5) Query matches on second clause, with X = leeds, Y = [bradford,rugby], N = 2;
(6) N > 1 succeeds;
(7) N1 is N – 1 instantiates N1 to 1;
(8) getnth([bradford,rugby],1) is called;
(9) Query matches on first clause, with X = bradford.
(10) The only sub-goal writeln(X) is executed causing ‘bradford’ to be written.
If you still do not understand how this definition works for any number ‘N’, then use it on a list for different values of ‘N’ with trace on. It is very important that you should be able to hand-trace the execution of a goal in the above manner using pen and paper.
The rule getnth is recursive, as are nearly all rules which process lists. This should not be surprising, as a list is a data structure that can be defined recursively as either being the empty list or an element followed by a list.
Lists 73

74 Lists
6.3 ‘member’ and ‘append’
Consider the problem of determining whether an element is a member of a list. First we see if the element is the head of the list: if it is we have finished. If it isn’t then we check to see if it is in the tail of the list. This is expressed very naturally in Prolog as:
member(X, [X|_]). /* if X is head of list then
goal is satisfied… */ member(X, Y). /* …else look in tail */
The following query will produce the answer ‘yes’:
?- member(dog, [cat,dog]).
This is the solution tree:
?- member(dog,[cat,dog]) |
member(X,[_|Y])
|
member(dog,[dog]) |
member(X,[X|_])
member(X, [_|Y]) :-
{X = dog, Y = [dog]}
{X = dog}
If you still don’t understand how it works, use the trace predicate to follow it in action.
Now consider a predicate that appends two lists (remember that the notation [] is used for the empty list, which has no members, and therefore neither head nor tail). An example of append in use is:
?- append([art,history], [physics,maths],L). L = [art,history,physics,maths]
Note that the first list is appended to the front of the second list. This is the way append has always been defined in Prolog. This is the Prolog for append:
append([], L, L).
append([H|T], L, [H|U]) :- append(T, L, U).
This is rather more subtle than the previous examples and should be studied carefully. Do not be put off by how obscure this looks. The list notation is very concise, and used in such a declarative context as Prolog may make this appear unreadable to the newcomer. Within a little time this kind of statement will become familiar and readily understandable. If you can understand ‘append’, then you have probably grasped the most difficult concept in Prolog, so be prepared to take some time over understanding it.
The first clause should be readily understood: the empty list appended to any list produces the same list. The second clause can be read declaratively as: If the list we

Lists 75
are appending has head H and tail T and we append this to L then the resulting list will have H as the head, and the tail of the list, U, will be the result of appending the tail of the first list, T to the second list L.
Or put another way, the second clause can be described by, the resulting list must have the same head as the first list. The resulting list’s tail must be the result of appending the tail of the first list with all of the second list.
6.4 A method for defining rules that manipulate lists
When you are defining rules that manipulate lists, it is a useful tip always to break the lists into their heads and tails in the head of the rule, identify which heads correspond, and then form the necessary relationships between the lists’ heads and tails in the body of the rule. This is for the general part of the rule. The boundary condition is usually very straightforward and can nearly always be written down straight away. This may be summarised by the following steps:
(1) Express all the lists in the head of the rule as having a head and a tail;
(2) Give the same name to those heads of the list that must be the same;
(3) Give the same name to those tails of the list that must be the same;
(4) Form the necessary relationships between the remaining heads and tails in the body of the rule;
(5) Simplify any head and tail pairs that do not need to be expressed as both head and tail.
We may see how this works by returning to the append predicate. Following the first instruction we express the head of the rule as:
append([H1|T1], [H2|T2], [H3|T3]):-
Using step 2, it should be clear that the resulting list must start with the same element at the first list, giving:
append([H|T1],[H2|T2],[H|T3]):- ||
+————–+
There does not seem to be much more we can do with step 2, so we try step 3. This does not help, so we move on to step 4. Now it should be clear that T3 must be the result of appending T1 to [H2|T2], so the rule is:
append([H|T1], [H2|T2], [H|T3]):- append(T1, [H2|T2], T3).
The last step is now used to replace [H2|T2] with a single variable as there is no need for this list to be separated out into a head and a tail. So finally our rule (without the boundary case) is:

76 Lists
append([H|T1], L, [H|T3]):- append(T1, L, T3).
Which is equivalent to the version given above.
6.5 Which is input, which is output?
One feature of Prolog worth bearing in mind is that when we define predicates to perform various tasks on lists or structures, we are only specifying relationships – we are not saying this variable is the input and another variable is the output. That is only the way we think about it. Prolog has no such concept of input and output parameters. This means that predicates will ‘work backwards’. If we input the definition for member and then the following query, using ; (or the Another solution dialogue) to get all the solutions:
?- member(X, [shoes,ships,sealing_wax,cabbages]).
X = shoes;
X = ships;
X = sealing_wax;
X = cabbages;
no
we get what at first seems a remarkable result, but on closer examination is an inevitable consequence of Prolog. It is very important to remember that we are constantly thinking about Prolog in a conventional and procedural manner and it will often surprise us because of its greater power.
We get a similar result if we use ‘append’ with the third parameter instantiated and variables as the first two parameters:
?- append(X, Y, [a,b,c,d]).
X = []
Y = [a,b,c,d];
X = [a]
Y = [b,c,d];
X = [a,b]
Y = [c,d];
X = [a,b,c]
Y = [d];
X = [a,b,c,d]
Y = [];
no
This feature is not just a novelty but can be very beneficial. Consider the case where you are processing some list a part at a time. The parts that you want to process separately are divided by a certain key value. In the case of a string of characters

Lists 77
represented by their ASCII codes this key value might be 32 for the space character. The space usually divides words, so you can use this to enable you to process one word at a time. How do you pick out each part of the list up to the next space? It’s very simple using ‘append’. Here is a rule that returns the next word from the ASCII list and the rest of the list that has yet to be processed:
process_sentence(Word, Listin, Listout):- append(Word, [32], L),
append(L, Listout, Listin).
Here each word is returned as a list of its ASCII codes. For example:
?- process_sentence(Word, [76, 79, 79, 75, 32, 65, 72, 69, 65, 68], L).
gives:
The rule can be simplified by combining the two appends:
process_sentence(Word, Listin, Listout):- append(Word, [32|Listout], Listin).
6.6 Sorting
How might we sort a list of integers into ascending order? We want a predicate of the form sort(Unsorted,Sorted). We can start by defining the boundary case: a list consisting of a single element is sorted:
sort([X], [X]).
We now have to pick off the remaining cases. There are many different ways of sorting a list. This method is based on the ‘bubble sort’ which basically consists of examining the first two elements of a list, reordering them if necessary, sorting the remainder of the list, and then seeing if the start of the ordered part is greater or less than the greater of the first two considered.
sort([H1,H2|T], [H1,H3|T3]):- (H1 =< H2), sort([H2|T], [H3|T3]), (H1 =< H3). Here we check that the first element, H1, is less than the second, H2, so they are in order, then sort the remainder. If the head of this, H3, is greater or equal to H1 then the output list must be H1 followed by the sorted list H3|T3. sort([H1,H2|T], [H3|S]):- (H1 =< H2), sort([H2|T], [H3|T3]), (H1 > H3), sort([H1|T3], S).
Word = [76,79,79,75]
L = [65,72,69,65,68]

78 Lists
This is the same as the previous case only H1 is greater than H3. Next we have:
sort([H1,H2|T], [H3|S]):- (H1 > H2),
sort([H1|T], [H3|T3]), (H2 > H3), sort([H2|T3], S).
This time the first element of the input list is greater than the second. We basically repeat the last two clauses taking account of this. The final clause is therefore:
sort([H1,H2|T], [H2,H3|T3]):- (H1 > H2),
sort([H1|T], [H3|T3]), (H2 =< H3). Note that the sort as it has been defined is only suitable for sorting numbers. We have made the sort rather inflexible as to the types of thing it can sort. It is common not to build the actual test that the sort depends on directly into the sorting rule. We often find it convenient to define a predicate such as gt(X,Y) which we can define independently of the sort. A typical definition might be: gt(X,Y) :- X > Y.
Which we might use in the example above. We might prefer to define it using the standard ordering comparison:
gt(X,Y) :- X @> Y.
This enables the sort to be used on a much wider range of types. Our sort, using ‘gt’ becomes:
sort([X], [X]).
sort([H1,H2|T], [H1,H3|T3]):- gt(H2, H1),
sort([H2|T], [H3|T3]), gt(H3, H1).
sort([H1,H2|T], [H3|S]):- gt(H2, H1),
sort([H2|T], [H3|T3]), gt(H1, H3), sort([H1|T3], S).
sort([H1,H2|T], [H3|S]):- gt(H1, H2),
sort([H1|T], [H3|T3]), gt(H2, H3), sort([H2|T3], S).
sort([H1,H2|T], [H2,H3|T3]):- gt(H1, H2),

sort([H1|T], [H3|T3]),
gt(H3, H2).
This is a far more convenient form because we can change the definition of gt(X, Y) without looking at the sort code. It can now be generalised to sort anything we like. Later in the chapter we’ll use it to sort cells on a spreadsheet.
The above version of bubble sort was rather unsubtle, we broke the problem down into a list of cases and dealt with each in turn. An alternative and much more elegant approach is to define a predicate, swap(L1,L2), that takes a list and swaps the first pair of elements that are out of order. It fails if all pairs are in order. This can be defined as:
swap([X,Y|Rest], [Y,X|Rest]):- gt(X, Y).
swap([H|T], [H|Rest]):- swap(T, Rest).
The first clause swaps the first pair if they are out of order. The second clause recurses on the tail, leaving the head of the list in place.
The bubble sort can then easily be defined by using swap(X,Y) until it fails at which point we know the list must be sorted:
bubblesort(List, Sorted):- swap(List, Part_sorted), bubblesort(Part_sorted, Sorted).
bubblesort(L, L).
This can most easily be understood by thinking about what it does to a few simple lists. For example, what does it do to these lists?
[1,2,3,4]
[5,1,2,3]
[1,2,3,5]
6.7 Lists containing structures
The elements of a list may be atoms, structures, variables, or any other terms, including other lists. Here is an example of a list containing other lists as its members:
couples([[george,pam],[bruce,sheila],[mike,jenny]]).
This is a list of three elements, each of which is a list containing two elements, each of which is an atom. The query:
?- couples([H|T]).
produces:
Lists 79

80 Lists
H = [george,pam]
T = [[bruce,sheila],[mike,jenny]] yes
Consider:
bits([a,[b,c,d],e,[f,[g,h]]]).
This is a list of four elements. The first is an atom, the second is a list of three atoms, the third is an atom and the last is a list of two elements, the first of which is an atom and the second a list of two atoms.
It may come as no surprise that any structure can be an element of a list. A list itself is just another structure with a particularly simple syntax. A list is really a structure of the following form:
[a,b,c] = list(a,list(b,list(c,[])))
Obviously the left form is a lot more convenient, but in all respects, other than the way you and the Prolog system write it, it is as though it was declared in the right hand fashion. The infix symbol ‘|’ can be thought of as the list functor rather than the word ‘list’ I’ve used above. Then if we think of a list expressed in a prefix form rather than infix it would be:
|(a,|(b,|(c,[])))
This way of thinking or writing a list can be very useful when considering unification. Consider the above list being unified with:
|(H,T).
It’s rather obvious that H is unified with a and T is unified with the structure immediately following the ‘a’ which is itself a list. Remember that the form of a list as it is normally written is really only syntactic sugar, something that makes writing and reading lists more convenient, the actual structure of a list is as shown above which explains its behaviour when unified with other list structures.
A simple application of using structures within a list is the following, where we imagine that we are implementing a spreadsheet program in Prolog. A spreadsheet consists of an array of cells. Some of the cells have values which we display from time to time as the spreadsheet is updated. As a great many of the cells do not have a value, it is efficient to keep a list of only those cells that have values. Many parts of the spreadsheet program will want access to the spreadsheet’s values, so we may feel justified in storing the values as an asserted fact containing the list. The cells are labelled by their row position (1, 2, 3,…) and by their column position (a, b, c,…). The fact containing the list to store the cell values could be:
cell_values([cell(1,a,’CARS’), cell(4,e,6438)]).
A particular cell’s value, if it has one, may be obtained very simply by using member:

get_value(Rownum, Colname, Value):- cell_values(Values),
member(cell(Rownum,Colname,Value), Values).
Although the use of the functor cell can be obviated, its use makes the program more readable and more easily updated if requirements change. Using structures in this way is giving us the same advantage as using records in other languages. It quite literally gives us the facility to structure our data, rather than deal with long unstructured lists of characters, integers or whatever.
We might wish to store the list of cells in sorted order by ascending values of column and row. In order to do this it is only necessary to define the predicate ‘gt’ and then use the bubblesort we defined earlier in this chapter. As we want columns to be more significant than rows, we define ‘gt’ like this:
gt(cell(_,C1,_), cell(_,C2,_)):- C1 @> C2.
gt(cell(R1,C,_), cell(R2,C,_)):- R1 > R2.
Note that, the first cell is always considered greater than the second cell if the first cell’s column is greater than that of the second cell. The second clause is for when the two cells have the same column, in which case we need to test the row numbers.
Exercises 6
(1) Define a list called weekdays, containing monday, tuesday etc.
(2) Given that the first of the month is a monday, define a predicate to print the day for any date in a month.
(3) Define a predicate delete(X, L1, L2) that removes the element X from the list L1 to yield the list L2.
(4) Define a predicate to find the last element in a list.
(5) Write a rule that gives the intersection of two sets represented as lists.
(6) Write a rule to give the union of two sets represented as lists. There must not be any repeated elements.
(7) Define a predicate reverse(X, Y) that reverses the order of the elements of X and instantiates the resulting list to Y. Hint – use append.
(8) Define a rule to sort the cells of the spreadsheet into ascending order by ‘Rownum’. (9) Hand trace the solution to the query:
?- member(X,[tom,dick]),write(X),fail.
(10) A list of the prices of items in stock is kept as a clause in the form:
Lists 81

82 Lists
stock([item(1023,99.95),item(1024,29.95),item(1021,46.75), …]).
Each member of the list is a structure giving the item number and its price. Write a rule, stock_price(Num,Price), which expects to be given the item number and returns its price.
(11) For the stock items in the above question, write a ‘gt’ predicate that would enable the list of stock to be bubble sorted by item number.

7 PROGRAM CONTROL
This chapter introduces Prolog features that affect the flow of control of a program which includes cut, perhaps the most infamous feature of Prolog which is often likened to ‘goto’ in other languages for its lack of readability. Some Prolog efficiency issues concerning clause selection via indexing and some of the ramifications of Prolog’s execution model are discussed.
7.1 Or
As well as being able to specify rules where to satisfy a goal one first satisfies one goal and then goes on to satisfy another goal, it is possible to say ‘to satisfy a goal solve the first sub-goal or solve the second’. As long as one or other sub-goal succeeds, then the main goal will succeed. The symbol for ‘or’ is ;. For example:
happy(X):-
rich(X) ; lucky(X).
meaning someone is happy if they are either rich or lucky. If the database contains the following facts:
rich(tom). lucky(dick).
the following may then be produced:
?- happy(X).
X = tom;
X = dick
In fact the ‘or’ construct is not strictly necessary. We could have expressed the above rule without using an ‘or’:
happy(X):-
rich(X).
Program Control 83

84 Program Control
happy(X):-
lucky(X).
This is exactly equivalent to the previous definition. The ‘or’ is included for convenience where the second construct seems heavy-handed.
When using ‘or’ in everyday language we often use it to mean only one of the alternatives is true. As in: it’s either too hot or too cold, In Prolog ‘goal1 ; goal2’ means that goal1 can be satisfied or goal2 can be satisfied. In logic, ‘or’ is commonly called ‘logical disjunction’ and is often represented as a large ‘V’.
In procedural terms, when the ‘or’ is encountered by the interpreter it creates a backtrack point consisting of the second part of the ‘or’, and then attempts to satisfy the first part of the ‘or’, failing which it will backtrack to and try to satisfy the second part.
7.2 Cut
The ‘cut’ is a special control facility in Prolog which enables the programmer to restrict the backtracking options open to the Prolog system as it executes a goal. The symbol for ‘cut’ is ! and it appears as a sub-goal on the right hand side, i.e. in the body, of a rule. The first part of this explanation will explain the workings of cut quite informally and then we will examine the procedural semantics of cut in rather more depth.
The interpreter on meeting the ‘cut’ for the first time will let it succeed, but any subsequent failure will cause the interpreter to backtrack to the last backtrack point of the parent goal. This can save the interpreter a lot of pointless searching and it is more economical on memory because the interpreter will be remembering fewer backtrack points. In this respect, cut is a very pragmatic feature of Prolog as it allows us to use our knowledge about a particular situation to guide the Prolog system away from pointless searching. Consider the following:
mammal(X):-
warm_blooded(X),
!,
four_legs(X).
warm_blooded(cat). warm_blooded(dog).
four_legs(cat).
four_legs(dog).
If we make the query:
?- mammal(X).
we get the response:
X = cat; no

Program Control 85
as the only solution: ‘dog’ does not appear as a solution when we ask for a second solution by entering a semi-colon (or via the Another Solution dialogue). Backtracking has jumped over the possibility of re-satisfying ‘warm_blooded’ because the cut has removed the choice point of ‘warm_blooded’ which was created when warm_blooded(X) was matched with warm_blooded(cat).
This is not a very realistic example as we would normally want ‘warm_blooded’ to be re-satisfied. Inthecasewherewearelookingupavalue,andweareonlyinterestedin one such value, we can prevent backtracking occurring. As an example consider part of the ‘cars’ database:
supplier(ford,uk,’21 Tinsgate, Dagenham’,’01 233 4821′). supplier(blmc,uk,’18 Beadle Road, Cowley’,’0325 24122′). supplier(fiat,italy,’333 Via Alphonse, Turin’,’0101 888 376 3983′).
We might require a single address for each manufacturer, even if there was more than one address given. It may be our requirement that we only mail one address for each manufacturer. Here we would use the cut like this:
process_supplier(Supplier):- get_address(Supplier,Address),
mail(Supplier,Address).
get_address(Supplier,Address):- supplier(Supplier,Country,Address1,_), !, string_concat(Address1,Country,Address).
The predicate string_concat is to be taken as defined elsewhere.
On satisfying get_address, supplier is first satisfied, and if it is possible for it to be re- satisfied then a backtrack point is created. The ‘cut’ is then executed, and this removes any backtrack points created since entering the current goal, so preventing any possible future backtracking to the ‘supplier’ sub-goal.
The effect of cut is in fact rather more far-reaching than has so far been implied. Not only does it remove any choice points that have been created within the clause where it is activated, it also removes any choice points that the parent goal may have. Consider this simple example that establises whether there is an electrical fault in a given electrical component:
electrical_fault(X):- capacitor(X),
!,
impedance(X, R),
R < 5000. electrical_fault(X):- fuse(X), !, impedance(X, R), R > 100.

86 Program Control
fuse(f436). impedance(f436, 200).
capacitor(c782). impedance(c782, 1000).
We might normally expect the goal electrical_fault to be called with a known component as in:
?-electrical_fault(c782).
This will match with the first clause and create a choice point because of the second electrical_fault clause, capacitor(c782) will then succeed. The cut is then used to remove the choice point. The idea being that we have identified the component as a capacitor, we know that there is no point in backtracking to see if it is fuse! However, if the query had been:
?-electrical_fault(f436).
The first clause for electrical_fault would have failed at the capacitor(f436) goal and backtracing would allow the second clause to be used. Take note, that the capacitor(f436) goal failed before the cut could be executed, which means that the backtrack point for electrical_fault is left intact.
However, if we make the query:
?- electrical_fault(X).
we get the response:
X = c782; no
with no more solutions obtainable by entering a semi-colon. Exactly as before, the backtrack point created for electrical_fault when electrical_fault(X) is matched against its first clause has been removed due to the cut. This prevents ‘f436’ appearing as a solution.
From a programming point of view we can justify the use of the cut in the above example by the simple observation that when electrical_fault is called we expect its argument to be instantiated. Therefore, once we have established that the component in question is a capacitor or a fuse or whatever, we know that there is no point in trying to match it with another component. Therefore it is expedient to prevent any unnecessary searching by including the cut immediately after we have establised what we are dealing with. It should be clear that the declarative semantics have been changed somewhat. We no longer have the luxury of calling the electrical_fault goal with a variable and getting a complete result.

Program Control 87
Use of the cut forces us to think hard about the procedural semantics of Prolog. i.e. about what actually happens when the query is being solved. This is because the cut affects the choice points that are available at the point that it is executed. The following example is rather more abstract than usual, but it is being used to convey the precise semantics of the cut.
Consider the following partial solution tree corresponding to the clauses:
a:- b, c, d.
b:- e, !, f.
b:- g, h.
f:- i.
f:- j. i.
j.
This is the solution tree for the query ‘?- a.’:
a *bcd
*e!*f
i
Choice points have been marked with ‘*’. In order to understand the exact procedural semantics we are going to follow the execution of this goals in great detail.
• The call to a immediately causes a call to b.
• At the point when the body of b is being executed there is a choice point available
for b (hence the star).
• The next goal to be executed is e. When e is executed it also leaves a choice point.
• Now the cut is executed which removes both the choice point for e and b. It must be realised that it is precisely at this point that it is executed that it removes the choice points within its scope.

88 Program Control
• Execution now proceeds with f, which also creates a choice point. This choice point, because it comes after the cut, is left alone.
• At this point control passes to c.
• When c fails control then passes to the most recent choice point which is at f.
• Execution proceeds forward again with control being passed to c which, of course, fails again.
• At this point the whole query fails without any further backtracking, because the choice points prior to the call to f have been removed by the cut.
The entire procedural semantics of cut can be described by: when cut is executed by: it succeeds;
it removes any choice points for the calling goal;
it removes any choice points for goals in the same same clause as the cut
which exist at the time of the call.
The last point has been emphasised because the cut does not affect the choice points of those goals that are subsequent to the cut and this is a peculiarly undeclarative feature making the order of the subgoals overwhelmingly important.
The cut enables us to program the equivalent of ‘IF..THEN..ELSE’ type constructs found in other languages. Conventionally only one part of an ‘IF..THEN..ELSE’ statement is executed: In other words the clauses are mutually exclusive. However, in Prolog, if the first clause for a rule succeeds but a subsequent goal fails, we can go on to backtrack into the second. This is often not desirable. We can stop the backtracking by including a cut immediately after the condition for the particular clause.
To use the spreadsheet as an example again, consider the layout of the cells on the screen. A spreadsheet screen looks something like:

Program Control 89
At any one time only a limited number of cells can actually be shown on the screen. The cells go from a1 up to at least z256. At any one time there is a current cell which is the one the user can change the contents of, or perform the calculation of. In the above example this is b5. The user can change the current cell by using the cursor keys, but if the cursor is already at row one and the user presses the up arrow then we do not want to change anything as it is impossible to go higher up the spreadsheet. The same is true if the user presses the left arrow key when the cursor is at the column labelled ‘a’.
In a conventional language we might express this as:
IF key = ‘up’ THEN
IF current_row = 1 THEN
return
ELSE
current_row = current_row – 1
move_cursor(current_row)
ENDIF
ELSEIF key = ‘left’ THEN
IF current_col = ‘A’ THEN return
ELSE
current_col = current_col – 1
move_cursor(current_col)
ENDIF
ELSEIF key = ‘right’ THEN
. . .
We can express the same mutually exclusive clauses in Prolog by using the ‘cut’ as follows.

90 Program Control
We first define our predicate to be:
process_key(Key,Current_row,Current_col,New_row,New_col)
We need new parameter names for the altered Current_row and Current_col because we cannot destructively assign new values to them. (97 is the ASCII for a).
process_key(up,1,Current_col,1,Current_col):- !.
process_key(up,Current_row,Current_col,New_row,Current_col
):-
New_row is Current_row – 1, move_cursor(New_row),
!.
process_key(left,Current_row,97,Current_row,97):- !.
process_key(left,Current_row,Current_col,Current_row,New_c
ol):-
New_col is Current_col – 1,
move_cursor(New_col),
!. .
.
7.3 Cut/Fail – The eight queens problem
An important Prolog programming construct that involves the use of cut is the cut/fail combination. This is where cut is called immediately before a call to fail. We use this in a situation where we want to force a failure with no prospect of backtracking into any subsequent clauses for the rule in which the cut/fail is placed. It’s a very definite kind of failure, useful in situations where we have entirely established that something is false. The eight queens problems has an elegant solution which shows how the cut/fail combination can be used to excellent effect.
This is a very old problem, how do you place eight queens on a normal chessboard so that no queen can take any other. We will solve a slight variant of this, how to place n queens on a normal chessboard. The following query:
?-queens(8, Solution).
Can then be used to solve the full problem. We expect Solution to be instantiated to some representation of the positions of the eight queens. Queens can move horizontally, vertically and diagonally any number of spaces, so it is clearly not trivial to find a solution. However, it should be immediately clear that every queen must be in a different row. Therefore an intuitive approach is to think of placing one queen at a time at some position within each row.
We will solve the problem recursively by placing a single queen and then solving the problem for one less queen. We will imagine that the rows and columns are labelled 1

Program Control 91
to 8. The boundary is very straightforward, placing no queens, i.e. the queen on row 0, returns no positions:
queens(0, []).
Now for the recursive part, this will subtract one from the current row and make a recursive call for the rest of the solution:
queens(Row, [position(Row,Col)|Rest]):- Row > 0,
Last_row is Row – 1, queens(Last_row, Rest),
Notice that we are returning a list of positions. The head of the list is the position of the queen about to be placed within this goal sequence, we clearly already know the row it is going on, the rest of the goal sequence will determine the column. The tail of the list, which gives the placement of the Row-1 queens, is found from the recursive call.
Now we need to generate a candidate position for the current row, for the moment we will just give this the name candidate_col and consider how it is to be coded a little later: Aftergeneratingthecandidatecolumnforthequeenwecantestifitisplacedin a position where it is safe from the queens placed by the recursive call, we will call this goal unthreatened. Therefore the goal sequence continues with:
candidate_col(Col), unthreatened(position(Row,Col),Rest).
If unthreatened fails then we will backtrack into candidate_col for an alternative column for the queen. Clearly candidate_col needs to be able to backtrack through all eight columns. Remember what was said about member in the previous chapter, that we can use it with a variable for the first argument to generate all elements of a list. This makes candidate_col very easy to define as:
candidate_col(Col):-
member(Col, [1,2,3,4,5,6,7,8]).
We can define unthreatened recursively by noting that a position is safe if it is safe with regard to the first queen position in the list, and is safe from the queens in the rest of the list (this is the recursive call). Therefore the code for unthreatened is:
unthreatened(Position, [Q|Rest]):- safe(Position,Q), unthreatened(Position,Rest).
unthreatened(Position,[]).
Now it only remains to code safe. It is much more easy to code what is unsafe because this is so easily defined. A queen is not safe when it is on the same horizontal, vertical, or diagonal line as another queen. If we test for each of these conditions we can then force failure by using fail. Unfortunately this would not be enough. If the first clause tested whether the queens were on the same row, and the

92 Program Control
second clause tested whether they were on the same column, a failure at the first clause would cause backtracking into the second which might then succeed. What we want is to fail and not allow the possibility of backtracking. We achieve this with the cut/fail goal sequence.
safe(position(R,_), position(R,_)):- !,fail.
safe(position(_,C), position(_,C)):- !,fail.
safe(position(R1,C1), position(R2,C2)):- diff(C1,C2,W),
diff(R1,R2,H),
H=W,!,fail.
safe(_, _). /* otherwise safe */
We check whether the queens are on the same diagonal by calculating the difference in rows and columns of the two queens. Notice the final clause, if none of the previous clauses are executed completely then the queen is safe, none of the cuts will have been executed and the goal will be satisfied by backtracking into the final clause.
Calculating this difference is straightforward we just have to take care to make the difference positive:
diff(X, Y, D):-
X < Y, D is Y - X. diff(X, Y, D):- X >= Y,
D is X – Y.
In the above we are proving that the position is safe by proving that it is not unsafe. We are attempting to prove the negation of unsafe, i.e. NOT unsafe. Negation in this context is equivalent to failure. The goal unsafe will fail if unsafe is not true This is often referred to as negation as failure.
7.4 Repeat
This built-in predicate (BIP) always succeeds and always creates a backtrack point. It behaves exactly as if it were defined by:
repeat.
repeat:- repeat.
A procedural way of interpreting this is: every time repeat is called, it is immediately satisfied and creates a backtrack point which is a call to itself.
This enables us to force goals to be repeated until they succeed. A simple example is where we require a digit (0-9) from the user. We do not want to fail if he gets it wrong, but rather just let him retry until he does give one. A Prolog rule which will only succeed when given a digit and will not fail in any event is:

get_digit(X):-
repeat,
get0(X1),
X1 >= 48,
X1 =< 57, X is X1 - 48, !. get0(X) instantiates X to the ASCII code for a character typed at the keyboard. The ASCII codes for digits 0 - 9 are 48 - 57 inclusive, so, having read a character, we check whether it is in this range. If so, we then subtract the ASCII code for 0 from it to leave us with the integer value of the character. If an invalid character is entered, the use of repeat will cause us to backtrack to get0(X1). Where we have a valid character, the use of cut will then remove the backtrack point created by repeat. The repeat predicate has other uses, such as creating potentially infinite loops for program control purposes which is discussed in a later chapter. 7.5 Findall A common requirement is to obtain all the solutions to a particular goal as a list. We can do this by defining a predicate which is commonly called findall. It has three arguments, the first indicates what we wish to collect a list of, the second is the goal to be solved, and the final argument will become instantiated to the list of solutions. For example, given the two facts: warm_blooded(cat). warm_blooded(dog). We can collect the solutions to the goal warm_blooded(X) with the query: ?- findall(X,warm_blooded(X),L). L = [cat,dog] The first part of findall is a failure driven loop which asserts all the solutions into the database, the second part collects these solutions into a list. Consider: findall(X, Goal, Xlist):- call(Goal), assertz(queue(X)), fail; assertz(queue(bottom)), collect(Xlist). Notice the use of the built-in predicate call which allows us to call a Prolog goal that we do not know the name of until run-time. Also notice the use of the 'or' which allows us to assert a bottom of queue marker when there are no more solutions. The final goal is the one that collects the solutions. This rule is defined as: collect(L):- retract(queue(X)), Program Control 93 94 Program Control !, (X == bottom,!,L = [] ; L = [X|Rest], collect(Rest)). This recursively collects the solutions, we do not want to leave a backtrack point whenever the retract is satisfied so we follow it with a cut. We test for the bottom of the queue with X == bottom. This is a test that requires X to be instantiated to bottom and is more stringent than X = bottom which would succeed when X is not instantiated. Look at the description of '==' in the chapter on built-in predicates for a full explanation. If we are at the bottom of the queue we terminate the list with the empty list, otherwise we make the solution, X, the head of the list to be returned and recursively collect the rest of the list. 7.6 Clause indexing In earlier chapters we have described Prolog's search strategy very naively. In particular Prolog avoids creating choice points where it knows that a subsequent search is not going to yield a match. It does this by generating code for each predicate that contains branch tables for each different first argument. So when the first argument to a predicate is known, it immediately knows what the candidate set of clauses, based on matching first arguments, is without having to do the expensive operation of unification. How it does this need not concern us but if you are interested [Kogg90] describes it. This means that all predicates are effectively indexed on their first argument. This should influence how we program in order that we take advantage of this wherever necessary. If we have large collections of unit ground clauses we should arrange for the argument that we usually search on to be the first. Where we are unable to arrange this it may still be possible to take advantage of clause indexing by using an additional set of clauses whose purpose is nothing other than to improve access to some more fundamental set of clauses. For example, consider a set of employee records of the form: employee(name,national_insurance_id,address) We may have a requirement to look up employees' names based on their national insurance numbers and at the same time have a need to look up their national insurance numbers given their names. We could duplicate the table so that we have name as the first field in one instance of the table and national insurance as the first field in another instance. More efficiently we can introduce a key to the employee facts, for example: employee(key,name, national_insurance_id, address) The key should be a unique integer value. We now need two sets of clauses to give us efficient access to the employee records, one for retrieval on name and one for retrieval on national insurance, for example entries of the form: employee_name(name, key) employee_ni(ni, key) Program Control 95 are required. We can define a rule to automatically choose the correct set of clauses to use by using the built-in predicate nonvar/1 to identify an instantiation of the name or national insurance number: employee(Name, NI, Address):- nonvar(Name), !, employee_name(Name, Key), employee(Key, Name, NI, Address). employee(Name, NI, Address):- nonvar(NI), !, employee_ni(NI, Key), employee(Key, Name, NI, Address). employee(Name, NI, Address):- employee(_, Name, NI, Address). Notice that I've allowed the search to succeed when neither the name nor the national insurance are known by defining a third clause that does not use the key. When a predicate has only one candidate clause for a given call, we say that in this case the call is determinate. Clause indexing not only makes matching with a particular clause very much faster it also means that many more calls are made determinate as the Prolog system can tell in advance whether a choice point is needed. 7.7 Garbage collection The matching of structures within a Prolog program causes parts of the structures to be copied into Prolog's so called 'heap' area (sometimes called the global stack). At any given point it is usually the case that not all structures that have been copied for unification purposes will be referenced by active parts of the execution. The heap is expanded by claiming memory from the operating system. In severe cases this will cause excessive use of the heap, either causing memory to run out or paging to disk. Those parts of the heap which are not referenced are called garbage. In order to keep the heap area as free as possible a garbage collector is used to reclaim unreferenced areas. The standard way for such a garbage collector to work is to mark all the referenced areas of the heap by following all the active pointers, and then to compact the heap, thus freeing space at the top whilst at the same time rearranging any structure pointers to point to the new heap positions of the active structures. Of course, this all takes processing time. Garbage collection for the most part is unobtrusive but where we are trying to provide a very smooth flowing interface with the user, it can be frustrating to have this pause in the middle of what might otherwise seem to be an innocuous piece of code. We might also find garbage collections unwelcome in some time-critical areas of code. More advanced Prolog systems than the Keylink interpreter will offer some control over when 96 Program Control you want garbage collection to happen, in certain situations you will find such facilities invaluable. When trying to avoid the need for garbage collection you should note that backtracking is a situation where the Prolog system can reclaim space by simply restoring pointers to its internal areas. It's a sort of instant garbage collect with no marking or compaction necessary. Thus failure driven loops can be a cheap and cheerful way to avoid the necessity for garbage collection. Exercises 7 (1) Define a predicate which checks that a word is correctly spelt by comparing it with a dictionary of words (a useful sample is given at the end of this question). Then define a predicate, near_miss, which succeeds when the spelling of a word is a 'near miss' with another word, which it returns, where a near miss is defined as being where the first three letters are the same and the lengths of the words are different by at most one letter. The rule for dealing with the words' lengths can be defined by: close_numbers(N, N). close_numbers(N, M):- N =< (M + 1), N >= (M – 1).
You will also need to use the built-in predicate name which was introduced in Chapter 4. To remind you of its use, it has two arguments: the first argument is an atom and the second is the list of ASCII codes corresponding to the letters in the atom. For example:
?- name(duck, X).
X = [100,117,99,107]
(2) Now use the near_miss predicate to give the user all the near misses for each word he enters. If you have duplicates you should consider the placement of ‘cuts’ in your program. (You can use read(X) to read a word from the user – the word must be terminated with a full-stop).
word(ducal).
word(ducat).
word(duchess).
word(duchesse).
word(duchy).
word(duck).
word(duckling).
word(duct).
word(ductile).
word(dud).
word(dude).
word(due).
word(duel).
word(duenna).

word(duet).
word(duff).
word(duffer).
word(duffle).
(3) Modify the above program so that the definition of near_miss is that: the two words start with the same character, they are within one character of being the same length, and that half or more of the remaining characters are the same.
(4) Use findall to collect a list of near misses as given by the goal near_miss in the previous question.
Program Control 97

8.1 put
As well as the write and nl predicates for output there is also put(X) – this has one parameter which should be instantiated to an integer value. The value should be an ASCII code representing a printable character. When executed, put(X) outputs the corresponding character to the current output stream (normally the screen). For example:
?- put(104),put(101),put(108),put(108),put(111).
will print hello on the screen. On the PC you can output any of the IBM’s graphics characters as well. For example:
?- put(182).
will output one of the box-drawing characters.
8.2 get, get0 and read
For input of single characters there are two predicates, get(X) and get0(X). They both have one argument which becomes instantiated to the ASCII code representing a character read from the keyboard. The difference between them is that in the case of get(X), its argument will become instantiated only if the character read is ‘printable’, i.e, not a function key, backspace, etc., whilst with get0(X) any character will do.
?- get(X).
will wait for the input of a single character. The character must be followed by a carriage return.
Here is a rule that reads a line of text typed at the keyboard and returns it as a list of words. It looks for the carriage return character (ASCII code 13) to recognise the end of the line and it recognises the space (ASCII code 32) as a word separator.
read_word_list(L):-
getchar(C), /* one character read ahead */
8 INPUT AND OUTPUT
Input and output 99

100 Input and output
read_word1(L, [], C). /* list is for building */ /* of current word */
read_word1([], [], 13):-!.
read_word1([Word], Wlist, 13):- name(Word, Wlist),!.
read_word1(Words, Wlist, 32):- !,
name(Word, Wlist), getchar(C), read_word1(L, [], C), append([Word], L, Words).
read_word1(Words, Wlist, C):- append(Wlist, [C], Wlist1), getchar(C1), read_word1(Words, Wlist1, C1).
getchar(C):-
repeat,
get0(C), acceptable_char(C),!.
acceptable_char(13). /* special case – */
acceptable_char(C):- /* only printable chars accepted */ C >= 30,
C =< 126. This works by 'carrying' a list of character codes that make up the current word being read in the second parameter of read_word1 and converting this to an atom when a separator (space) or terminator (carriage return) is reached. The list of words making up the entire line is obtained using append. This can easily be extended to fulfil more demanding roles. For example, the number of characters recognised as separators might be extended to include the comma, or upper case letters could automatically be converted to lower case. For reading more than one character at a time there is the read(X) predicate. ?- read(X). Will read an entire term, i.e. a constant, a variable or a structure, and will instantiate X to that term. When you input a term in response to the read(X) predicate you must terminate it with a full-stop and then press . This is a very handy predicate for a quick solution to getting input from the user, but because of the need for the terminating full-stop it is usually not an acceptable approach for finished programs. An approach which processes the input as in read_word_list given above is usually rather more acceptable.

8.3 Reading and writing sequential files
File handling is effected in a very simple manner by redirecting input and output. All the usual built-in predicates can be used as normal, except they will either take their input from, or write their output to, a file.
To redirect the output to a file use the tell(X) predicate. It has one argument which is the file name, which can be a variable just as long as it de-references to a valid file name at run-time. The file is created if it does not exist. If it does exist it is overwritten, the previous contents being destroyed. The told predicate terminates output to the ‘tell’ file, closes it, and causes output to be redirected to the screen. The following example directs user output to a file of his choice, then repeatedly reads a character form the user and writes it to that file, until he types \, when the file is closed.
copy_to_file:-
write(‘Output file? ‘),
read(File),
tell(File),
repeat,
get0(C),
put(C),
(C = 92),
!,
told.
/* ASCII code for \ */
The predicates see(F) and seen are the input equivalents of tell(X) and told. ?- see(datafile).
causes the input to be redirected to the file ‘datafile’. All predicates requiring input will get their input from this file until seen is executed.
There are also the predicates seeing(X) and telling(X) which both have a single parameter which will be matched with the current input and output files respectively. The built-in predicate exists(X) succeeds when the file X is instantiated to exists.
8.4 Logging a Prolog session
Often you would like to have a record of your Prolog session either to examine on screen or to print to file. Sometimes this is useful as proof that something worked, or as a reminder of a certain piece of interaction. But it is also very useful when you want to carefully pore over an execution trace. With an execution trace it is often difficult to take in all the information that the trace offers whilst it is being produced. Also, it is not always possible to see far enough backwards through the trace to glean the necessary information that identifies the programming problem. The simplest way to get a permanent record of your interaction is to use the log built-in predicate. For example:
?- log(mylog).
will output a copy of all screen input and output to the file ‘mylog’ until Prolog exits or close_log is called. For example:
Input and output 101

102 Input and output
?- close_log.
closes the file ‘mylog’. The file is always written to from the start, so if the file exists any previous contents will be lost.
Exercises 8
(1) Modify read_word_list so that it automatically converts upper case to lower case.
(2) Create a file which contains your name and address on several lines. Use see(X) to read from this file and use read_word_list to output your name and address as a series of lists to the screen. You will need to modify read_word_list so that it uses ‘line feed’ (ASCII code 10) to detect the end of a line, rather than carriage return (ASCII code 13).
(3) Put the atom end_of_text at the end of your address file. Define a rule which uses read_word_list to read from your address file and output each line as a list to the screen until the line consisting of end_of_text is reached. At this point it should invoke seen to terminate input from the file.

9.1 Networks and trees
Consider part of the Midlands rail network around Coventry:
Nuneaton
25
10
Birmingham 20
18
Searching 103
9 SEARCHING
Leicester 12
25 21 15
Stratford
Coventry 8
8 Leamington
Rugby
Midlands Rail Network
A basic problem of such networks is how do you get from one place to another. What we need is a search strategy. A search strategy may be optimal or non-optimal. In an optimal solution we care about the distance travelled in a non-optimal one we ignore the distance. For the moment we will just consider non-optimal solutions of getting from A to B.
Firstly we need to represent the information given in the diagram in Prolog. We can use a series of unit ground clauses that record which places are connected and gives the distance between them:
connected(birmingham, nuneaton, 25). connected(nuneaton, leicester, 18). connected(birmingham, coventry, 20). connected(coventry, rugby, 8). connected(coventry, leamington, 8). connected(birmingham, leamington, 21). connected(birmingham, stratford, 25).

104 Searching
connected(stratford, leamington, 15). connected(nuneaton, rugby, 12). connected(coventry, nuneaton, 10).
This describes all the connections in one direction only. We can extend this by adding a second predicate which allows a connection to be the other way too:
connected2(X, Y, D):- connected(X, Y, D).
connected2(X, Y, D):- connected(Y, X, D).
Using a different predicate name avoids the possibility of infinitely recursing.
We need to define a few frequently used tems before going any further. In a network, each connecting line is called an arc, at the end of each arc is a node, the starting point of our search is called the starting node, and the finishing point is called the goal node or the terminal node. The entire set of nodes is sometimes called the search space. A list of connected nodes (nodes that are joined by arcs) is called a path or sometimes a search path.
Once we have a starting node we can redraw our network as a tree using the starting node as the root. If we take coventry as the starting node, then the tree is:
C
Lm B N R
B S S Lm N B L R N
S N B Lm S L S Lm L B
S Lm
Network as a tree
We draw this by starting at the root node and using the same arcs as the network but stopping whenever extending to a node would mean including that node on the path from the root twice. We refer to the nodes connected directly to a single node higher in the tree, children or child nodes. Hence leamington, birmingham, nuneaton and rugby are the child nodes of coventry which is the parent node of its children.
9.2 Finding successor nodes
In order to be able to do any sort of searching on a tree we need a rule that finds all the directly connected nodes to a particular node that does not include any nodes that

Searching 105
have already been visited. This means that the input must be the node to start from AND the path of nodes already visited. We define a rule ‘next_node’ that returns unvisited connected nodes:
next_node(Current, Next, Path):- connected2(Current, Next, _), not(member(Next, Path)).
This is sometimes called a successor function because it is capable of giving us all the successor nodes from any given node.
9.3 Depth first search
A depth first search is where we search as deeply into the tree as possible at every node. That is whenever there is a choice of which node to visit next, we choose the one that is furthest from the root. It is equivalent to the pre-order navigation of a tree that we met in the chapter on structures. For example: a depth first search starting at coventry with the goal node set to leicester visits the nodes: coventry, leamington, birmingham, stratford, nuneaton, stratford, birmingham, birmingham, stratford, leamington, leamington, stratford, nuneaton, leicester.
The search must construct a list of nodes that represents the path from the start node to the goal node. This path is the result of the search, it shows us how to navigate through the nodes from the start node to the goal node. Note that it is not necessarily the same as all the nodes that are examined during the search. In general far more nodes will be examined than will form part of the eventual search path. In the above example of a depth first search from coventry to leicester we gave a list of all the nodes visited but the search path consists of the nodes: coventry, birmingham, nuneaton, and leicester.
The search can be expressed by the following algorithm:
goal_found = false
form a list containing the start node if start_node = goal_node then
goal_found = true
exit
endif
for node = each successor node
add node to list
goal_found = depth_first(node,goal_node,list) if goal_found then
exit
endif next node
Notice that this is a recursive algorithm. The notion of going deeply into the tree can easily be seen in the loop that contains the recursive call. This call is causing the search to deepen (move further away from the start node) before the loop takes the node across the tree (by returning into the loop). Or put another way: the loop is taking the search breadth wise through the tree and the recursive call is taking the search depth wise through the tree.

106 Searching
This can be translated very easily into Prolog. Firstly, the boundary case is when the start node (first argument) is the same as the goal node (second argument). We need to supply the path taken so far as a third argument so that the rule for next_node can calculate the successor nodes. This third argument is not used by the boundary case as successor nodes are not required at the point that we reach the goal node. The fourth argument is for returning the path taken through the tree:
depth_first(Goal,Goal,_,[Goal]).
This means that when the start node is the same as the goal node, then the path consists of just that node. Now for the recursive part:
depth_first(Start, Goal, Visited, [Start|Path]):- next_node(Start, Next_node, Visited), depth_first(Next_node, Goal, [Next_node|Visited],
Path).
This clause finds a successor node using next_node (notice that this is usually a choice point). The start node is made the head of the path. A recursive call carries the search on deeper from the successor node with the nodes visited now having the successor node at the head. We expect the recursive call to yield the path, which is the tail of the path we return.
Any failure of depth_first to find the goal node results in backtracking to the next_node rule which selects a new successor node.
Consider the third and final arguments to depth_first. It might strike you as odd that we need two arguments to carry what is basically the same information, ie the path taken through the tree. The reason why we need two lists is plain to see when you consider what a query to find a particular path looks like. Say we want to do a depth first search from coventry to leicester. Then the query is:
?- depth_first(coventry, leicester, [coventry], Path).
Notice that the argument for the visited nodes is the list containing just coventry, indicating that at the time of calling this is the only visited node. The argument for the path is a variable. We start the search having visited one node and the recursive search instantiates Path to the list of nodes that constitute the path to the goal node.
9.4 Breadth first search
A breadth first search is probably the easiest search to visualise. We start at the root node and examine all the immediately connected nodes in turn, ie each of the root node’s children, stopping if we find the goal node. If we don’t find the goal node we examine all the nodes connected to the nodes that we just examined (the grandchildren) and so on. It shouldn’t be hard to see why this is called breadth first, we are essentially moving across the tree breadth ways before moving down (further away from the root node).

Searching 107
For example: a breadth first search starting with coventry with the goal node of leicester visits leamington, birmingham, nuneaton, rugby, then birmingham, stratford, stratford, leamington, nuneaton, birmingham, leciester.
When the breadth first search is expressed as an algorithm it seems a little different because we have to formalise how we build up a list of nodes to visit. The algorithm for breadth first search is:
goal_found = false
form a list containing only the root node loop until list is empty
current_node = list head
if current_node = goal node then
goal_found = true
exit loop
else
remove current_node from list
add all the child nodes of current_node to end of the list
endif repeat
If we wish to retain the path that gets us to the goal node then this must be added to the algorithm. This increases the algorithm’s complexity considerably because there are many paths being considered at the same time. Consider the case where our start node is coventry and the search path is initially just [coventry]. We now consider all the connected nodes to coventry, this means that we are now considering each of the paths: [leamington,coventry], [birmingham,coventry], [nuneaton,coventry], and [rugby,coventry]. We construct these path lists backwards as it is far more convenient for our program (we can find the first element of a list far easier than the last element). Only one of these paths will eventually prove fruitful and will interest us as the path to the goal node. What we have to do is keep a list of all the paths being considered and when the goal node is reached return the one that has been fruitful. At each recursive stage of the algorithm we extend a search path by each connected node.
How do we implement this algorithm in Prolog?
We start with a convenient bit of packaging that takes the two input arguments, the start node and the goal node and returns the Path from one to the other. This calls ‘breadth_first1’.
The first argument to breadth_first1 is the list of all active search paths which starts off as having just one element, [Start], which is the initial search path and contains only the start node.
The second argument is the goal node which is used to determine when the search has completed.
The third argument is the Path which will become instantiated to the complete path from start node to goal node:

108 Searching
breadth_first(Start, Goal, Path):- breadth_first1([[Start]], Goal, Path).
The first clause for breadth_first1 tests for the terminating condition, ie that the current node is the goal node, in which case it just succeeds returning the path as being the nodes visited so far with the goal node inserted at the head.
breadth_first1([[Goal|Path]|_], Goal, [Goal|Path]).
The next_node predicate can then be used with the previously defined findall predicate to find the set of new paths. The first argument is a list of all the active search paths, each of these must be extended to all its connecting nodes. For example the search path [leamington,coventry] must be extended to: [birmingham,leamington,coventry] and [stratford,leamington,coventry]. Given that a current path can be expressed as [Current|Trail], the call to findall looks like this:
findall([Next,Current|Trail],
next_node(Current, Next, Trail), NewPaths)
Note that findall generates a set of lists which are the set of new paths. This new set of paths can now be appended to the back of the set of path lists.
breadth_first1([[Current|Trail]|OtherPaths], Goal, Path):- findall([Next,Current|Trail],
next_node(Current,Next,Trail), NewPaths), append(OtherPaths, NewPaths, AllPaths), breadth_first1(AllPaths, Goal, Path).
This may not seem very easy to understand due to the first argument being a list of lists and the subtle use of findall. One way to describe what is happening in this clause is by the following:
(1) Remove first path from the current list of paths; (2) Find all the paths that can be extended from this; (3) Put these at the back of the list of paths;
(4) Continue the search with the new list of paths.
This can now be used to find a non-optimal path between any two nodes. For example: to find a route from coventry to leicester we use the query:
?- breadth_first(coventry, leicester, Path).
This is how the set of paths grows for this query. We start with the only path being the list:
[coventry]
This path gets extended by the following call to findall:

Searching 109
findall([Next,coventry], next_node(coventry,Next,[]), NewPaths)
which instantiates NewPaths to:
[
[leamington,coventry], [birmingham,coventry], [nuneaton,coventry], [rugby,coventry]
]
This is appended to the empy list which of course yields the same list. Then we have the recursive call to breadth_first1. This takes the first list from the list of paths and makes this call to findall:
findall([Next,leamington,coventry], next_node(leamington,Next,[coventry]), NewPaths)
This instantiates NewPaths to:
[
[birmingham,leamington,coventry],
[stratford,leamington,coventry] ]
This is then appended to the tail of the input list which gives us the list:
[
[birmingham,coventry], [nuneaton,coventry], [rugby,coventry] [birmingham,leamington,coventry], [stratford,leamington,coventry]
]
And the search continues until there is a match between the head of the first path list and the goal node.
9.5 Best first search
The idea of the best first search is to always extend the search from the most favourable node first. We saw with breadth first search that an extended set of search paths were simply appended to the end of the current set. If we can discriminate in some way between these different search paths we can reorder them which may speed up the searching. Defining what we mean by best can sometimes be a problem. In the case of the rail network we want the resulting path to have the shortest distance, so it makes sense to sort the paths based on their distance. To be able to do this we need a rule that can calculate the distance of a path. Consider:
path_distance([_], 0). path_distance([A,B|Rest], D):-

110 Searching
connected2(A, B, D1), path_distance([B|Rest], D2), D is D1 + D2.
This relies on each pair of nodes in the path being connected which makes it a straightforward matter to sum the distances between each pair.
Our aim is to sort the paths by distance so we need to be able to define ‘greater than’ to use with our bubble sort rule. This will take to paths as arguments and succeed if the first path represents a greater distance:
gt(A, B):- path_distance(A, D1), path_distance(B, D2), D1 > D2.
In order to convert the breadth first search to a best first search only requires us to order the list of paths before making the recursive call to breadth_first1. Completing this is left as an exercise for the reader.
9.6 Distances
Other forms of distance measurements are often required when searching. The distance between two points in a search space can be defined in many ways. For example: take the distance between two points in a city like Manhatten where you have to travel along either streets going North-South or East-West. If two different places are given coordinates X and Y, then the distance between them is the difference in the X values plus the distance in the Y values. This is sometimes called the Manhatten distance as it often occurs in searching problems.
B
A
Manhatten distance from A to B = 4
The two dimensional co-ordinates might be represented as coord(X,Y). The distance between two such co-ordinates can be defined as:
dist(coord(X1,Y1), coord(X2,Y2)), D):- diff(X1, Y1, D1),

diff(X2, Y2, D2),
D is D1 + D2.
diff(A, B):-
A >= B,
D is A – B,
!.
diff(A, B):-
D is B – A.
We define ‘diff’ to always give us a positive value, note the use of the cut to prevent backtracking into the second clause for diff when we know it’s not needed.
It’s now very easy to define gt(X,Y) for our Manhatten distances as:
gt(X, Y):-
dist(X, Y),
X > Y.
Exercises
(1) Draw a tree representing the Midlands Rail Network using Birmingham as the root node.
(2) Give a list of all the nodes visited by a depth first search from Birmingham to Rugby.
(3) Give the path from Birmingham to Rugby obtained by the depth first search in the previous question.
(4) Implement the depth first search in Prolog for question (2), but modify the second clause of depth_first to write the list of visited nodes to the screen.
(5) Using the tree from question (1), give a list of all the nodes visited by a breadth first search from Birmingham to Rugby.
(6) Give the path from Birmingham to Rugby obtained by the breadth first search in the previous question.
(7) Implement the breadth first search in Prolog fo question (7), but modify the second clause of breadth_first1 to show the list of NewPaths on the screen.
(8) Convert the breadth_first seach rule into a best_first rule by sorting the paths by their total distances.
Searching 111

10.1 Introduction
10 MACHINE TRANSLATION
We perform translation of input strings in virtually every aspect of Computer Science. The best known example of a non-trivial application is a compiler. This takes strings of source text and generates binary code corresponding to the intended meanings (as intended by the language designers, rather than the programmer!) of the source statements. The various forms that the statements of the source can take are usually rigidly defined by a ‘grammar’.
The translation process is usually done in two phases:
Syntactic analysis – This is where the source code is checked for conformity to the defined syntax of the language, various structures are built such as a parse tree, and symbol table entries made for ease of subsequent processing (this avoids the necessity of having to work with the original source).
Semantic analysis – This is where the code is generated corresponding to the original source. The meaning of the code is extracted and made apparent by the code generated.
Input Syntactic Parse Semantic Action Text Analysis Tree Analysis
In the case of Natural Language we can only successfully translate subsets of it as it is generally regarded as impossible to write down the syntax rules for an entire Natural Language. Apart from this limitation, the translation process is similar to that for a compiler: we perform syntactic analysis from which we build some internal representation of the input, then we take this and produce the necessary code (or actions) to execute what we understand the meaning of the input to be
An excellent reference for parsing techniques using conventional programming languages is [Rayw83]. A Prolog perspective can be found in [Warr81].
Machine translation 113

114 Machine translation
10.2 Backus Naur Form
It is usual to express a grammar in Backus Naur Form (BNF). For example: ::=
is the Backus Naur Form for saying that a sentence can consist of a noun phrase followed by a verb phrase. It is called a production, as it shows us how a sentence is ‘produced’ from less complicated components. Backus Naur Form is particularly useful for describing what are called Context Free Grammars. These are grammars where these productions apply regardless of any other context.
The open and closed angled brackets indicate that the symbol inside the brackets is a non-terminal, that is, it is composed of other symbols. When a symbol is a non- terminal it always appears on the left hand side of some production of the grammar. A terminal symbol is something that cannot be broken down further. More realistically, it is something which there is no useful purpose in breaking down further, e.g. an identifier in Pascal which consists of characters, but for the purposes of parsing, it is not very useful to consider the individual characters as the terminals. A scanner is often used to identify the terminal symbols of a language. These are mostly things like identifiers, labels, key words etc..
The Backus Naur production for a simple sentence can be directly expressed in Prolog by:
sentence(S):-
append(NP, VP, S),
noun_phrase(NP),
verb_phrase(VP).
This can be made more efficient by eliminating the append. We can do this by introducing a second parameter to the goal, which stands for the remainder of the list when the predicate has completed:
sentence(S0, S):- noun_phrase(S0, S1), verb_phrase(S1, S).
So we would expect that when given the query:
?- sentence([the,boy,stood,on,the,burning,deck], []).
for the ‘noun-phrase’ goal:
S0 = [the,boy,stood,on,the,burning,deck] S1 = [stood,on,the,burning,deck]
i.e. the ‘noun_phrase’ goal takes the entire string, [the,boy,stood,on,the,burning,deck], parses the first part, the boy, as the noun phrase and returns the remainder of the string as the list [stood,on,the,burning,deck].

10.3 Complete example
The Backus Naur form for a tiny part of Natural Language is:
::= ::=
::= ::=

::= ::= the | a
::= burning | young …
::= boy | deck …
::= stood | … ::= on | under | with | …
We can apply a very straightforward and rather mechanical translation of this to Prolog:
sentence(S0, S):- noun_phrase(S0, S1), verb_phrase(S1, S).
noun_phrase(S0, S):- determiner(S0, S1), noun_phrase2(S1, S).
noun_phrase(S0, S):- noun_phrase2(S0, S).
noun_phrase2(S0, S):- adjective(S0, S1), noun_phrase2(S1, S).
noun_phrase2(S0, S):- noun(S0, S).
verb_phrase(S0, S):- verb(S0, S1),
noun_phrase(S1, S).
verb_phrase(S0, S):- verb(S0, S1),
preposition_phrase(S1, S). verb_phrase(S0, S):-
Machine translation 115

116 Machine translation
verb(S0, S).
preposition_phrase(S0, S):- preposition(S0, S1), noun_phrase(S1, S).
determiner([the|S], S). noun([boy|S], S).
noun([deck|S], S). adjective([burning|S], S). verb([stood|S], S). preposition([on|S], S).
This only does the parsing, i.e. all it does is tell you that it can recognise (parse) the input string. To be of any use at all we need it to build a parse tree. This can be done quite simply by adding a third argument to all the rules:
sentence(S0, S, sentence(NP,VP)):- noun_phrase(S0, S1, NP), verb_phrase(S1, S, VP).
noun_phrase(S0, S, np(D,NP2)):- determiner(S0, S1, D), noun_phrase2(S1, S, NP2).
noun_phrase(S0, S, np(NP2)):- noun_phrase2(S0, S, NP2).
noun_phrase2(S0, S, np2(A,NP2)):- adjective(S0, S1, A), noun_phrase2(S1, S, NP2).
noun_phrase2(S0, S, np2(N)):- noun(S0, S, N).
verb_phrase(S0, S, vp(V,NP)):- verb(S0, S1, V), noun_phrase(S1, S, NP).
verb_phrase(S0, S, vp(V,P)):- verb(S0, S1, V), prepositional_phrase(S1, S, P).
verb_phrase(S0, S, vp(V)):- verb(S0, S, V).
prepositional_phrase(S0, S, prep(P,NP)):- preposition(S0, S1, P), noun_phrase(S1, S, NP).
determiner([the|X], X, determiner(the)). noun([boy|X], X, noun(boy)).
noun([deck|X], X, noun(deck)). adjective([burning|X], X, adjective(burning)).

verb([stood|X], X, verb(stood)). preposition([on|X], X, preposition(on)).
The result of the query:
?- sentence([the,boy,stood,on,the,burning,deck], [], P).
is:
The structure that’s returned will, in general, be used as input to the semantic analysis phase of our translation. The above structure is equivalent to the following tree.
P = sentence(np(determiner(the),np2(noun(boy))), vp(verb(stood),prep(preposition(on),np(determiner(the), np2(adjective(burning),np2(noun(deck)))))))
sentence
Machine translation 117
np determiner np2
the noun boy
verb stood
vp
prep on
np
determiner
np2
the adj
burning noun
deck
np2
10.4 Example for data access
The following example is based on a language a little like SQL (Structured Query Language), the standard language for accessing Relational Databases. A Relational Database is conceptually comprised of two-dimensional tables (relations), each of which has a number of named columns, and each data record forms a separate row (tuple) in a table. Here is an example:
EMP
Empno
Empname
Job

118 Machine translation
1
Smith
Clerk
2
Jones
Accountant
3
Peters
Lawyer
4
King
Director
Here we have a table called Emp, containing employee information. It has three columns: Empno, containing employees’ reference numbers, Empname, containing employees’ names, and Job, containing their job titles, and contains three data records (rows or tuples).
The Backus Naur form for part of the SQL grammar for accessing a database table is:
::= ::= select [colname]+ ::= from The ‘[colname]+’ means that there is one or more occurrence of ‘colname’, i.e. the name of a column in the database table named ‘tablename’.
Using our example table ‘Emp’, a query might be:
select empno empname from emp
which would display the reference number and name of all the employees in our Emp table. In order to parse this in Prolog, we assume that we have a rule read_word_list which takes the input string in its original form and converts it to a list of words. The code for such a rule was given in the preceding chapter. An example of its use is:
?- read_word_list(Wlist).
which would wait for the user to enter a string. If the user enters the string:
select empno empname from emp;
then the response is:
Wlist = [select,empno,empname,from,emp]
Note that we are using the semi-colon (ASCII code 59) as the terminating character in our input, rather than carriage return (ASCII code 13) used previously, and the code given for read_word_list should be modified accordingly.
The top-level goal go, reads in the query, parses it and outputs the parse tree produced by the parsing process. It is defined by:

go:-
read_word_list(Wlist),
query(Wlist, [], Plist),
write(‘Parse list is: ‘),
write(Plist),nl.
The code to parse the query follows the Backus Naur definition in precisely the same way as our first example, with extra structures added for the return of a parse tree:
query(S0, S, q(Sel,F)):- select(S0, S1, Sel), from(S1, S, F).
select([select|S0], S, select(Names)):- colnames(S0, S, Names).
colnames(S0, S, [Name]):- colname(S0, S, Name).
colnames(S0, S, [Name|Names]):- colname(S0, S1, Name), colnames(S1, S, Names).
from([from|S0], S1, table(T)):- tablename(S0, S1, T).
Some example data to represent our Emp table is:
colname([empno|S], S, empno). colname([empname|S], S, empname). colname([job|S], S, job).
tablename([emp|S], S, emp).
10.5 Semantic analysis
Using the example query:
select empname empno from emp;
produces the parse tree:
q(select([empname,empno]), table(emp))
Notice that the column names have been collected in a list, as the number of them present in a query is not fixed.
The next problem is to take the parse tree as input and produce the answer to the query it represents. This is achieved most easily by writing rules which match with the various forms of the parse tree, and which then execute the necessary sub-goals to achieve the corresponding effect. This is known as semantic analysis and is the process by which the meaning of the sentence is extracted and made to effect what it stands for.
Machine translation 119

120 Machine translation
For the above parse tree, it is necessary to define a rule which matches with this form of the parse tree:
do_query(q(select(Colnames), table(Tname))):-
It would aid further processing if we translate column names into column numbers, so the first sub-goal is:
get_col_nums(Tname, Colnames, Colnums),
We then need to access the table with name Tname (assume the record is returned as a list):
table(Tname, Rec),
We are then required to output the appropriate view of the record as determined by the specified columns in the ‘select’ part of the parse tree:
output_view(Rec, 1, Colnums),nl,
Finally, we are required to return all possible rows of the table, so the last sub-goal is fail. Wecanaddasecondclausefordo_querytoterminateneatlythesolutiontothe query:
do_query(_):-
write(‘Query answered’),nl.
The code for the various sub-goals is very straightforward, and for the sake of completeness is given here.
output_view(_, _, []):-!.
output_view([Hcol|Rest], Fieldno, [Fieldno|Restnums]) :- !,
write(Hcol),write(‘ ‘),
Next_field is Fieldno + 1, output_view(Rest, Next_field, Restnums).
output_view([_|Rest], Fieldno, Nums):- Next_field is Fieldno + 1, output_view(Rest, Next_field, Nums).
get_col_nums(_, [], []):-!.
get_col_nums(Tname, [Col|Colrest], [Num|Numrest]):-
col_number(Tname, Col, Num), get_col_nums(Tname, Colrest, Numrest).
col_number(emp, empno, 1). col_number(emp, empname, 2). col_number(emp, job, 3).
This is some example data for the emp table:

table(emp,[1,smith,clerk]). table(emp,[2,jones,accountant]). table(emp,[3,peters,lawyer]). table(emp,[4,king,director]).
Exercises 10
(1) Extend the Grammar in Backus Naur form to include the SQL ‘where’ clause for a single condition. For example, a query might now be:
select empno empname from emp where job equals lawyer;
(2) Modify the Prolog for the parser to allow parsing of the new grammar suggested in question 1.
(3) Modify the Prolog for the semantic analyser to cope with the amendment of question 1.
Machine translation 121

11.1 Introduction
Software engineering is concerned with sound design and implementation, efficient use of resources, and maintainability. These rapidly become important considerations as code size increases. As with any computer language all of these issues are of concern to the Prolog developer and, perhaps fortunately, many of the lessons learnt using conventional languages can be usefully employed when coding in Prolog.
11.2 The top level
What do large Prolog programs look like at the topmost level? Or, to put this another way, how do we effect control over our large Prolog programs? The answer is: in much the same way as with a conventional program. Typically we can expect a conventional program to have the following structure:
begin
loop
read command
obey command until exit condition
end
The words in bold are the sort of instructions that are available in conventional languages. This is typical of an interactive program. In many cases we might expect a main menu to be sandwiched between the ‘loop’ and ‘until’. The words in italics are not available in Prolog but we can easily achieve the same effect. Consider:
rap:-
initialise,
repeat
top_menu(X),
fail.
initialise
11 LARGE PROGRAMS
Large programs 123

124 Large programs
This is the main driving ‘loop’ of a three thousand line program. I always indent between a repeat and a fail to make the construct stand out. initialise is a rule which sets up some session specific information.
We can use a menu construct (which in some Prologs is supplied as a built in predicate, but can easily be defined in any Prolog) to allow the program to invoke any of a set of sub-goals. The fail ensures that we always return to the master menu (whether the sub-goals succeed or fail).
This is how the menu facility is defined:
top_menu:- display_top_menu,
read_line(X),
execute(X).
The rule read_line(X) is a general purpose utility that reads user input and converts it to an atom. It is defined thus:
read_line(A):-
get0(C),
process_char(C, L), name(A, L).
process_char(13, []):-!. process_char(C, [C|Rest]):-
get0(C1), process_char(C1, Rest).
The menu is displayed by the following code:
display_top_menu:-
write(‘> Menu select:’),nl,
write(‘(1) Start new rule-base’),nl,
write(‘(2) Test or edit existing rule-base’),nl, write(‘(3) Explain on’),nl,
write(‘(4) Explain off’),nl,
write(‘(5) Restart’),nl,
write(‘(6) Exit’),nl.
This consists of nothing more than a set of write statements. The appropriate goal is then executed by one of the following clauses:
execute(1):-
init_rule_base.
execute(2):-
test_or_edit.
execute(3):-
assertz(tron).
execute(4):-
retract(tron).
execute(5):-
resolve_all.

execute(6):-
halt.
Execution of the display_top_menu goal will cause the following to be displayed:
(1) Start new rule-base
(2) Test or edit existing rule-base (3) Explain on
(4) Explain off
(5) Restart
(6) Exit
Note that the potentially infinite backtracking is terminated here just by calling halt. It is also possible to terminate such a loop by using the cut to remove the choice point created by the repeat.
Selection of ‘1’ will cause execute’s parameter to be instantiated to 1 which causes the rule init_rule_base to be executed.
Another easy to implement facility is to allow the user a choice of actions from the input of a single character. This has the same form as using the menu but without the need for any display:
choose:-
read_line(X),
execute(X).
The ‘execute’ part can then selected by the appropriate letter.
execute(i):-
init_rule_base.
execute(t):-
test_or_edit.
execute(e):- explain(‘explain’).
execute(n):-
noexplain.
This method can be combined with the menus to give the user choice of directly entering commands by a single letter, or allowing him to select from a menu. The addition of the rule:
execute(m):-
top_menu.
does this. The user can enter his commands in a direct fashion when he knows the commands, or, by typing m, he can opt to select from a menu.
11.3 Top Down Design for Prolog programs;
Large Prolog programs can conveniently be defined using conventional methodologies where they embrace the concepts of modularity. In particular the much used ‘top-
Large programs 125

126 Large programs
down’ design method is appropriate. In case the terms ‘top level’ and ‘bottom level’ are unfamiliar to the reader, here are their definitions:
Top level – refers to the main (driving) procedure.
Bottom level – refers to those procedures that do not call other procedures. The top-down design method can then be stated, in a form amended for the Prolog
language, as:
(1) Start at the top level.
(2) Sketch out a goal sequence for this level in English.
(3) Specify structures required at this level.
(4) Progressively formalise into Prolog code identifying the function and parameters of each sub-goal.
(5) Complete specification rigourously, check the declarative semantics of all variables and structures.
(6) Go to the next level down, that is, take each sub-goal in turn, and apply (2) to it. This may, and usually does, involve defining yet more sub-goals.
The method is applied until all levels are specified rigourously.
The reason why this is a good method is that it allows us to think about a small but logically consistent subset of code at a time. When the code for a rule is designed and a sub-goal is defined we do not need to worry about how the sub-goal is going to achieve its function, we just assume that we will be able to design the sub-goal when we get to it and if necessary we will define more sub-goals to be called by this sub-goal in order to make the problem tractable. We can expect always to be able to design rules effectively this way as long as the preceding design and formulation of data structures has been sound. Sometimes the solution may not be the most effective in terms of performance or memory usage but these problems can be examined separately. We should endeavour to keep rules short in order to make their function and operation as clear as possible and their validation as easy as possible. A large part of this involves giving variables and rules meaningful names. Another important factor in making sub-goals easily read and easily verified is the use of neat formatting. Putting a comment immediately before each rule which identifies the input and output parameters and their relationship is to be recommended.
Conventionally, it is always hoped that a procedure can be verified visually by determining that the correct relationship holds between the input and output parameters. This is often quite difficult because of the procedural nature of the code which makes it hard to visualise the effect of the running code from its static code statemnts. With Prolog we find ourselves in a far better position because Prolog is declarative, and it should always be possible to see the run-time implications directly from a visual inspection of the code. However, if we use asserts and retracts frequently we soon find ourselves with the same problems of our less fortunate

Large programs 127
conventional coders. The declarative nature of Prolog is weakened with every assert and retract used and so these predicates must be avoided wherever possible. Alternatively, their use should be localised to as few rules as possible so that the majority of the code is isolated from their effect.
11.4 Encapsulation and Abstract Data Types (ADTs)
The idea of an Abstract Data Type is a very simple one. We specify procedures that perform the operations which we require regardless of how any particular data structure might be used to effect these operations. Then, quite independently, we implement these procedures to do the necessary operations to the chosen data structures. Only these procedures have access to the data structures, and the data structures can only be altered by use of these procedures. This effectively divides the code into those calls which have some specific purpose, but no knowledge of how this purpose is achieved, and the procedures which implement these purposes and operate on the data strucures internally. This sound similar to the Top-down design approach but it has the important additional point that the data structures are entirely hidden from view, they are encapsulated within the Abstract Data Type and only those procedures which form part of the type have knowledge of and access to the actual data structures.
In practise is can be difficult to prevent access to a particular data structure, but we keep to the spirit of the idea by simply passing arguments as variables that represent the structure to the procedures that comprise the ADT and receiving them back whilst only ever allowing the procedures of the ADT to actually look at them. We often call these arguments handles to the data structure.
A typical example would be the creation and manipulation of an ordered list. Our ADT would consist of predicates for creating, adding an element, deleting an element and accessing an element. Their external appearance might be:
create_ordered_list(-L) – return a new handle.
add_to_ordered_list(+L, +Element) – add Element to the list given by the handle L.
delete_from_ordered_list(*L, +Element) – delete Element from the list given by the handle L.
access_ordered_list(+L, +N, -Element) – access the Nth element of list given by the handle L.
Here I have used ‘+’ to denote an input argument, ‘-‘ to denote an output argument, and ‘* to denote input and output.
In implementing this in Prolog we have the choice of making L itself the actual data structure (as long as the user treats it as a handle all will be well) or actually using it as an identifier for the actual data structure, which is more secure, but a little harder to code and will necessitate the use of assert in order to store the data structures used between accesses (these can be retrieved from the database using the handle).

128 Large programs
An important advantage of using an ADT is that we can entirely recode one to use completely different representations and algorithms without having to alter any code that uses the ADT. Efficiency and resource concerns can be entirely encapsulated by the ADT effectively isolating the rest of the code from these concerns.
11.5 Memory management
In most conventional languages memory must be allocated to data structures before they can be used, and deallocated when they are discarded. This is a fairly complex business which often causes severe problems. It is not uncommon for even commercial packages to have problems in this area, sometimes called memory leakage, where unused memory is not properly deallocated. This eventually causes failure by the system running out of memory. Other typical problems involve overwriting of one structure with another, or freeing memory areas that are sill actually required. Luckily for the Prolog programmer these problems do not exist. Memory is allocated for your structures quite automatically and a garbage collector is used to reclaim no longer used memory areas. However, garbage collection is a costly operation and the comments made in the chapter on Program control should be noted. In particular it should be noted that failure driven loops require no garbage collection whereas recursive calls may cause problems unnecessarily where they can easily be replaced by an equivalent failure driven form.
11.6 Failure driven and recursive loops
The constructs whereby a loop is effectively used by using fail to iterate over a set of solutions, or the use of repeat and fail to create an infinite loop are called ‘failure driven loops’, for the obvious reason that it is the failure which is forcing the iteration. This is not the only way we can program to get the looping effect. Our example above could be written:
rap:-
initialise,
rap2.
rap2:-
top_menu(X),
rap2.
Notice that here top_menu(X) would always need to succeed for the looping (or recursion) to continue. To a logician, and for many Prolog programmers, the second solution is more elegant. Unfortunately, many Prolog implementations, including this one, make harder work of it, using more and more stack space as the recursion deepens. This may cause garbage collections (reclamation of memory space) to occur at unpredictable times which can make the performance of the program unacceptable. In the failure driven loop, each failure allows the Prolog system to reclaim all the space used directly.
My own view is that, in general, a failure driven loop is acceptable for simple iterative operations but should be avoided when being used to manipulate complex, and what are usually recursive, data structures..

Exercises
(1) Write a menu-driven program that allows the user to assert, retract and list facts to the screen. Each of these should be menu options. Read facts from the user using the read(X) predicate as described in the chapter on input and output.
(2) Use top-down design to implement a storage and retrieval system for names, telephone numbers and addresses. Your system should allow the user facilities for searching on partial matches with the data. The user should also be able to browse and have some editing facilities. For example, he should be able to alter part of an address.
(3) Give Prolog code for the ADT described in this chapter. Do not pass the actual data structure, but only a handle. The actual data structure can be stored using assert in the form:
ordered_list(handle, data_structure)
where handle is a unique identifier, i.e. 1 for the first used, 2 for the second and so on.
Large programs 129

12 PROLOG AND EXPERT SYSTEMS
12.1 Expert Systems
An expert system encodes and utilises expertise in some domain which is often learnt or elicitated from a human. We expect it to show reasonably intelligent behaviour within the domain being considered. Typical examples of early successful expert systems are: DENDRAL [Lind80], a system for identifying chemical compounds; MYCIN [Feig79, Buch84], a system for diagnosing bacterial infections; and PROSPECTOR [Duda79], a system for identifying mineral deposits.
We expect an expert system to be capable of encoding knowledge about some domain in a particularly straightforward manner, i.e. the knowledge must be encoded quite directly and not need reducing into algorithms. We also expect an expert system to be capable of explaining its line of reasoning and be able to justify the results it produces.
12.2 Suitability of Prolog
Prolog is a suitable language for the development of expert system type programs for several reasons. These are discussed in the following sections.
Rule based
Any program written in Prolog is a series of rules. The rule-based approach has advantages over the conventional approach to writing programs:
Rules can work largely independently of each other (the whole system does not collapse if one is removed in the same way that a FORTRAN or Pascal program might if one line were to be removed). The system will produce some sort of sense even when incorrect (with conventional programs the outcome is very unpredictable and will often lead to a program crash).
A set of rules is a natural structure for expertise. Many human skills, perhaps most, are accomplished by learning rules.
Installing Prolog 131

132 Installing Prolog
Rules can be incrementally updated. In Chapter 1, the example concerning insurance could have more rules with the head ‘risk_for_capacity’ appended to the rule-base without affecting the validity of those already there.
Declarative
To a large extent, Prolog is declarative, which can make program design very like program specification. This makes rules concise and amenable to verification by inspection. Any assignment of variables is effected by unification. There are no explicit decisions or branches. There is virtually no execution logic to specify. This style of specification is ideal for the development of a rule-base for an expert system which allows real world rules to translate in a fairly direct way to program rules.
Explanations
A Prolog program can be made to explain its own reasoning in a very straightforward manner and an example is given later in the chapter.
Backward and forward chaining
The basic theorem-proving aspect of Prolog is backward chaining: this means that the Prolog system starts with what has to be proved and attempts to build a proof tree for it. But, as Prolog is a complete programming language, there is nothing to prevent us coding our own inference engine in Prolog which forward chains. An inference engine is simply a program which can manipulate a known set of facts and rules to produce (infer) new facts. Forward chaining is where we do not try to prove any particular goal, but deduce whatever we can from the known rules and facts. In practice Prolog turns out to be a highly suitable language for writing inference engines. A Prolog program that does this is discussed at the end of this Chapter.
Rules Inference New
Facts Engine Facts
Top-down design
Prolog naturally encourages top-down design when writing programs. Horn clauses naturally break down problems into an hierarchy of sub-goals with local parameters. Hence the natural design method is to start with the principal goal, break it down into sub-goals whilst identifying the variables needed at this level, and then repeat the process for each sub-goal. This is exactly the top-down design method of conventional

Installing Prolog 133
software engineering. Thus Prolog comes with a sound design methodology which facilitates the construction of expert system rule-bases.
First order logic
The value of Prolog being based on first order logic is that this is a mathematically sound vehicle for reasoning and modelling our problem areas. It helps us in formulating logically consistent rules, forcing us to think clearly by directly expressing our programs as logic. An example of where this can be seen to work is in the following problem:
Consider the following statements:
Pat knows Mike’s telephone number.
Mary has the same telephone number as Mike.
Pat dials Mike’s telephone number.
Can we deduce that Pat knows Mary’s telephone number?
Common sense tells us that we cannot, but there definitely is a sense in which Pat knows Mary’s telephone number – she knows the number but not the fact that it is Mary’s. To put it another way, Pat knows Mary’s number but only as Mike’s number. The matter is easily resolved when we express the facts in Prolog, because we are forced to state what we mean by ‘knows’. If we want ‘knows’ to express the relation between a person and another person and their telephone number, then this suggests that the second person in the relation and their number should be a structure. This clearly allows us to express that it is the link between a person and their telephone number that is important, not just the number. So we can express the example as follows.
knows(pat, mikestel(57733)). marystel(57733).
dials(pat, 57733).
and make the queries:
?- dials(pat, X),marystel(X). X = 57733
yes
?- knows(pat, marystel(X)). no
This is clear, concise, and unambiguous. It involves no procedural information, just the declaration of the required relation. Of course it is still possible for the muddle- headed programmer to define nonsense in Prolog, but it is much easier for the clear- minded to express their ideas simply and directly.

134 Installing Prolog
In conclusion, Prolog offers enormous advantages to the expert system builder.
12.2 An Expert System in Prolog
We are going to construct an Expert System to give careers advice to students. It’s going to be very simple and the actual knowledge it encodes should not be taken very seriously!
The system will interact with the user, asking questions to establish information that is needed to execute the rules. It will attempt to identify a profession by establishing that its requirements are met and that the students’ motivations are compatible.
For the purposes of this example we’ll just take a few professions and list their requirements and what the jobs offer:
Fireman. Requires: bravery, very good health, no fear of heights. Offers: excitement.
Solicitor. Requires: good academic grades, good memory, methodical thinking. Offers: good pay.
Policeman. Requires: bravery, fair or good academic grades, very good health. Offers: excitement.
These can be simply encoded in Prolog as sub-goals listing these attributes:
recommended_profession(fireman):- brave(very),
health(very_good), fear_of_heights(none), likes_excitement(greatly).
recommended_profession(solicitor):- academic_grades(good), memory(good), thinking(methodical), likes_good_pay(greatly).
recommended_profession(policeman):- brave(very),
(academic_grades(fair);academic_grades(good)), health(very_good),
likes_excitement(greatly).
We require our Expert System to start with the first profession and try to establish whether it is suitable for the person being ‘interviewed’. To do this it must ask the person for any information it does not know, and keep track of this information in case it is needed for another rule.
A useful utility would be a predicate that displayed a menu of choices with a prompt, and returned the value that had been selected by the user. We’ll make the assumption that each choice on the menu starts with a different letter, so the user will choose his

Installing Prolog 135
selection with a single key which indicates the first letter of his choice. The selections will be given as a list of atoms. We’ll define the ‘menu’ predicate immediately:
menu(Prompt, Selections, Choice):- nl,
write(Prompt),nl,nl, display_selections(Selections), nl,
write(‘Type 1st letter ‘), get(C),nl, get_choice(C,Selections,Choice), nl.
display_selections([]):- nl.
display_selections([H|T]):- tab(5),
write(H),nl, display_selections(T).
get_choice(C, [], Choice):- write(‘Illegal selection’),nl,!.
get_choice(C, [Choice|T], Choice):- name(Choice, [C|_]),!.
get_choice(C, [_|T], Choice):- get_choice(C, T, Choice).
The rule ‘get_choice’ illustrates a very neat way of using ‘name’ and parameter matching to effect the required result. We can then define a rule for finding out how brave someone is as:
brave(X):-
askable(brave),
menu(‘How brave are you?’, [very, averagely,
assertz(brave(Y)), retract(askable(brave)), X = Y,!.
fair, poor],Y),
We use ‘askable’ to keep track of the questions that can be asked, and we retract ‘askable(brave)’ when the question is answered. Also notice that we delay trying to unify ‘X’ with the result from ‘menu’ until after the ‘assertz’ and ‘retract’. This is because when we use the rule ‘brave’ we’ll be trying to establish a goal like ‘brave(very)’, so if the user said he was only averagely brave then the ‘menu’ predicate would fail and we would not get the answer asserted into the database. We ‘assert’ it so that we will not need to ask for it again.
We can produce rules for the other attributes in a similar fashion:

136 Installing Prolog
health(X):-
askable(health),
menu(‘How good is your health?’,
[very_good,average,fair,poor],Y), assertz(health(Y)),
retract(askable(health)), X = Y,!.
fear_of_heights(X):- askable(fear_of_heights),
menu(‘What is your fear of heights?’,
[none,slight,moderate,extreme],Y),
assertz(fear_of_heights(Y)), retract(askable(fear_of_heights)), X = Y,!.
likes_excitement(X):- askable(likes_excitement), menu(‘Do you like excitement?’,
[greatly,moderately,slightly,no],Y), assertz(likes_excitement(Y)),
retract(askable(likes_excitement)), X = Y,!.
academic_grades(X):- askable(academic_grades), menu(‘Are your academic grades?’,
[good,fair,poor],Y), assertz(academic_grades(Y)),
retract(askable(academic_grades)), X = Y,!.
memory(X):- askable(memory), menu(‘Is your memory?’,
[good,fair,poor],Y), assertz(memory(Y)),
retract(askable(memory)), X = Y,!.
thinking(X):- askable(thinking), menu(‘Is your thinking?’,
[methodical,vague],Y), assertz(thinking(Y)),
retract(askable(thinking)), X = Y,!.
likes_good_pay(X):- askable(likes_good_pay), menu(‘Do you like good pay?’,
[greatly,moderately,slightly,no],Y), assertz(likes_good_pay(Y)),
retract(askable(likes_good_pay)), X = Y,!.

Finally we need to have a set of facts for the ‘askable’ questions.
askable(brave). askable(health). askable(fear_of_heights). askable(likes_excitement). askable(academic_grades). askable(memory). askable(thinking). askable(likes_good_pay).
In this form we can run our expert system by typing the query:
?- recommended_profession(X).
12.3 Explanation
To be a proper expert system there really needs to be an explanation facility, so that when the expert system has reached a conclusion we can ask it why it has reached that conclusion and get some meaningful response.
There are many ways of achieving this which depend on the details of the system itself. We can achieve an explanation very easily by just writing an explanation in English in the head of each of the ‘recommended_profession’ clauses. For example:
recommended_profession(fireman, [‘very brave’, ‘very good health’,’no fear of heights’,
‘likes excitement’]):- brave(very), health(very_good), fear_of_heights(none), likes_excitement(greatly).
The second parameter can then be used, when the rule succeeds, to indicate the sub- goals that were satisfied, thereby explaining why ‘fireman’ was chosen.
This gives an adequate trace for a small example like this, but is not adequate in the general case, especially when our rules are deeply nested.
A more general solution is to add a second parameter to each goal head, which explains why that particular goal succeeds, using information passed back from the second parameter of the sub-goal. We can include additional information as to whether the user simply stated that something was true or whether the expert system deduced it from sub-goals. For example:
recommended_profession(fireman, recommended_profession(deduced([B,H,F,L]))):-
brave(very, B), health(very_good, H), fear_of_heights(none, F), likes_excitement(greatly, L).
brave(X, stated(‘How brave are you’,X)):-
Installing Prolog 137

138 Installing Prolog
askable(brave),
menu(‘How brave are you?’,
[very,averagely,fair,poor],Y), assertz(brave(Y,stated(‘How brave are you’,
retract(askable(brave)), X = Y,!.
Y))),
We add second parameters in the same way to all our goals that are not simply for utility purposes (such as ‘get_choice’).
The explanation we now get looks quite complicated. For example:
recommended_profession(deduced( [stated(‘How brave are you’, very),
stated(health,very_good), stated(fear_of_heights,none), stated(likes_excitement,greatly)]).
This might not be very readable, but it is an easy matter to define an ‘explanation sub- system’ to make sense of it for us. This will consist of a rule which takes the recommended profession and the above structure as input, and writes out an English explanation which corresponds to the input structure.
explanation_subsystem(R, recommended_profession(X)):- write(‘The profession ‘),
write(R),
write(‘ was chosen because:’),nl,nl,
explain(X).
explain(stated(X,Y)):- write(‘To the question: ‘), write(X),
write(‘? You answered: ‘), write(Y).
explain(deduced(L)):-
write(‘It was deduced because: ‘),nl, explain(L).
explain([]).
explain([H|T]):-
explain(H),
explain(T).
This gives a readily understood trace.
12.4 Inference engines
We can write more advanced Expert Systems by writing our own inference engines. We can make these backward chain, like the example above, forward chain, deal with certainty factors, in fact we can tailor them to do precisely what we want them to do.

Installing Prolog 139
In order to give a more natural syntax to our rules we can define a number of operators as prefix and infix. This avoids the use of lots of brackets. This is really a cosmetic issue, but it removes much of the Prolog flavour and makes our rules easier to write and understand. This is how we define them using the ‘op/3’ built in predicate:
:- op(1100, fx, forward_rule). :- op(1100, fx, backward_rule). :- op(1100, fx, deduce).
:- op(1080, fx, if).
:- op(1070, xfx, then).
:- op(1060, xfy, and).
:- op(1050, xfx, can).
:- op(1050, xfx, has).
:- op(1050, xfx, has_property). :- op(1050, xfx, found_in).
:- op(1030, xfx, isa).
:- op(1030, xfx, with_certainty).
We use ‘forward_rule’ and ‘backward_rule’ for declaring the rules and these are defined as prefix, that is they come before a single argument which will be the rule. We use ‘deduce’ to invoke backward chaining: it prefixes a single argument which is the goal to be proved. The ‘if’ is for constructing rules and it is also prefix, coming before the premises and the conclusion. The premises and the conclusion are connected by the infix operator ‘then’ which comes between them. Where there is more than one premise they are joined by the infix operator ‘and’. Then there are various descriptors, for example: fish can swim, tiger isa cat, etc. Finally there is the infix operator ‘with_certainty’ which will be used for attaching certainty values to rules.
Here are some example rules and facts:
forward_rule if
and
X isa fish
forward_rule if
and
X has_property edible. X can swim
X found_in ocean
then
X has gills
then
X isa fish.

140 Installing Prolog
fact(cod can swim). fact(cod has gills). fact(cod found_in ocean).
12.4.1 Forward chaining
This works by repeatedly executing the rules and asserting whatever can be deduced from them. The new facts which have been deduced are added into the set of known facts and then the process is repeated. When nothing more can be deduced the system stops.
Rules Facts
Forward Chaining Inference Engine
New facts
The basic idea is to take every rule of the ‘if condition(s) then conclusion’ form and each time the condition(s) can be satisfied the conclusion is asserted. This is known as a cycle of the forward chainer. It cycles through the rules for as long as new assertions are being made. This is an unguided strategy as no particular goal is being targeted, rather, anything that can be derived from the rules is derived. Here we initialise the forward chaining and call the main forward chainer:
fc:-
initialise,
forward_chain,
write(‘Forward chaining finished.’),nl.
initialise:- abolish(proof_cycle), abolish(new_assert), assert(proof_cycle(0)).

Installing Prolog 141
Now we have the main cycling part of the forward chainer. This uses a repeat/fail loop to iterate over the deduction process. It exits from the potentially infinite loop by checking whether new assertions have been made. If they haven’t then cut is called to remove the backtrack point created by the repeat. At each iteration it tries to prove all the rules in the database.
forward_chain:-
repeat,
(
(new_assertions(X),X=0,!)
;
update_proof_cycle, proof_cycle(N), explain([‘Proof cycle ‘,N]), (forward_rule Rule), forward_prove(Rule),
fail
).
update_proof_cycle:- retract(proof_cycle(N)), M is N + 1, assert(proof_cycle(M)).
new_assertions(1):-
proof_cycle(0),!. /* first cycle so no new assertions
needed */
new_assertions(1):- new_assert,
!,
abolish(new_assert). new_assertions(0).
Now for the part that actually does the inferencing. The first clause is trivial as it just tests whether the RHS has already been proved, and if it has, it does nothing. The second clause attempts to satisfy the LHS of the rule, if it can, it asserts the RHS as a fact. Note that it is simply trying to satisfy the LHS as a series of facts, there is no hidden backward chaining going on! The third clause deals with a conjunction in the LHS of a rule.
forward_prove(if LHS then RHS):- proved(RHS),!.
forward_prove(if LHS then RHS):- /* match on a rule, then fc on LHS */
!,
forward_prove(LHS), explain([LHS,’ has been proved’]), my_assert(fact(RHS)), explain([‘Asserting ‘,RHS]).
forward_prove(A and B):- !,

142 Installing Prolog
forward_prove(A), forward_prove(B).
forward_prove(A):- fact(A).
proved(X):-
fact(X).
12.4.2 Backward chaining
For completeness, we’ll define an inference engine for backward chaining. A backward chainer must start with a user supplied goal that it is required to prove. It matches the goal with the RHS of a rule, then attempts to satisfy the LHS of the rule. If it fails it looks for a new match for the goal until there are no more. As with forward chaining this uses ‘if condition(s) then conclusion’ type rules, commonly called productions. This is a more focused approach than forward chaining. A particular goal is being aimed at and the system tries to construct a proof for the goal in question.
Backward Chainer Constructing a Proof tree
G G
IF A & B & C THEN G
ABC A
IF D & E & F THEN A
DEF
Here are the same example rules declared as backward:
backward_rule if
and
X isa fish
backward_rule if
and
X has_property edible. X can swim
X found_in ocean
then
X has gills
then
X isa fish.

Installing Prolog 143
We use these with the same facts as for the forward chaining example.
The backward chainer is a very straightforward piece of Prolog. The first rule is just convenient packaging:
deduce RHS :- backward_prove(RHS).
The first clause of backward_prove is satisfied if the RHS is a fact. The second clause attempts to find a rule where there is a match on the RHS of the rule with the goal currently being proved. If it can find such a rule it backward chains on the LHS. The third clause deals with a conjunction occurring in the LHS of a rule:
backward_prove(RHS):- fact(RHS),
explain([RHS,’ is a known fact.’]).
backward_prove(RHS):-
(backward_rule if LHS then RHS), explain([RHS,’ matches rule with LHS ‘,LHS]), backward_prove(LHS).
backward_prove(A and B):- backward_prove(A), backward_prove(B).
It is a simple matter to augment the inference engine with the ability to ask the user questions. We need to assert into the database what goals can be regarded as askable. For example, we might assert:
askable(X can fly).
If a goal is askable and cannot be satisfied by any of the rules defined so far, then we construct a question to ask the user using a simple translation table. We present the question to the user and act according to his reply:
backward_prove(A):- askable(A),
ask(A).
ask(A):- translations(A,Q), writelist(Q), write(‘? (y/n) ‘), getyn(Ans), retract(askable(A)), Ans = 121, /* ‘y’ */ assert(fact(A)).
translations(X isa Y, [‘Is ‘,X,’ a ‘,Y]).
translations(X has Y, [‘Does ‘,X,’ have ‘,Y]). translations(X has_property Y, [‘Does ‘,X,’ have property ‘,Y]).
translations(X can Y, [‘Can ‘,X,’ ‘,Y]).
translations(X found_in Y, [‘Is ‘,X,’ found in ‘,Y]).

144 Installing Prolog
12.4.3 Backward chaining with certainty factors
Certainty factors are associated with each rule and fact. They describe how much faith is to be placed in the relevant rule or fact. The certainties are combined in the conditional part of the rule by taking the minimum value of the conditional goals and multiplying this with the certainty value of the rule. As with the two above methods production rules are used but with an extra ‘with_certainty C’ part. A threshold can be imposed on the certainty value in order to abandon unprofitable searches. See clause 2 of backward_prove_with_certainty. For example, here are some facts about ‘flu’ with their certainty factors:
fact(george has aching_limbs with_certainty 0.9). fact(george has_property sweaty with_certainty 0.7). fact(george has fever with_certainty 0.6).
And some rules we can use with these:
backward_rule if
X has temperature with_certainty C1 and
X has aching_limbs with_certainty C2
then
X has flu with_certainty 0.9.
backward_rule if
X has_property sweaty with_certainty C1
and
X has fever with_certainty C2
then
X has temperature with_certainty 0.9.
The Prolog code for backward chaining with certainties is a modified form of the backward chainer given above.
deduce RHS with_certainty C :- backward_with_certainty(RHS with_certainty C, C).
backward_with_certainty(RHS with_certainty C, C):- fact(RHS with_certainty C).
backward_with_certainty(RHS with_certainty C, C):- (backward_rule if LHS then RHS with_certainty C1), backward_with_certainty(LHS, C2),
C is C1*C2,
C > 0.
backward_with_certainty(A and B, C):- backward_with_certainty(A, C1), backward_with_certainty(B, C2), minimum([C1,C2], C).

12.4.4 Explanation for the Backward chainer
After a goal has been proved it is desirable to have the facility to examine the proof. We can arrange for this to happen by constructing the proof tree as the program executes. We need to add an argument for the proof into each of the rules used to execute the backward chainer. This is very much the same approach as we used for the ‘recommended_profession’ rule base.
deduce RHS :- backward_prove(RHS, Proof), see_proof(RHS, Proof).
backward_prove(RHS, fact(RHS)):- fact(RHS),
explain([RHS,’ is a known fact.’]).
backward_prove(RHS, rule(RHS,Proof)):- (backward_rule if LHS then RHS), explain([RHS,’ matches rule with LHS ‘,LHS]), backward_prove(LHS, Proof).
backward_prove(A and B, conjunction(Proof1,Proof2)):- backward_prove(A, Proof1),
backward_prove(B, Proof2).
backward_prove(A, asked(A)):- askable(A),
ask(A).
This produces for the ‘fish’ example (I’ve laid this out in a readable form):
rule(
cod has_property edible, conjunction(
rule(
cod isa fish,
conjunction(
fact(cod can swim),
fact(cod has gills)
)
fact(cod found_in ocean) )
)
As with the ‘recommended_profession’ example we need to be able to translate this into something understandable. This is achieved here by using indentation, using the built-in predicate tab, to present the proof in a similar fashion to that above. In addition it writes where the rules and facts were used. The first rule initiates the explanation process by calling ‘output_proof’ with a tab value of 0.
see_proof(RHS, Proof):-
write(‘Do you want to see how ‘), write(RHS),
write(‘ was deduced (y/n)?’),
Installing Prolog 145

146 Installing Prolog
getyn(Ans),
Ans = 121, /* ‘y’ */ nl, output_proof(0,Proof).
output_proof(Tab, rule(RHS,LHS)):- tab(Tab),
write(RHS),
write(‘ was proved by proving the subgoal(s):’),nl, Tab1 is Tab + 8,
output_proof(Tab1,LHS).
output_proof(Tab, conjunction(A,B)):- output_proof(Tab, A), tab(Tab),write(‘AND’),nl, output_proof(Tab, B).
output_proof(Tab, fact(A)):- tab(Tab),
write(A),write(‘ – which is a fact.’),nl.
output_proof(Tab, asked(A)):- tab(Tab),
write(A),write(‘ was given by the user.’),nl.
12.5 Conclusion
This chapter has introduced writing expert systems and inference engines in Prolog. It is possible to write very much more complex Expert Systems using Prolog. Furthermore, systems can be written that provide the inferencing and explanations for a variety of Expert System methods within a single system. Such systems, called ‘shells’, do not come with a specific knowledge or rule base, but will run with a variety of knowledge bases. Such a system is MIKE (Micro Interpreter for Knowledge Engineering), available from the Open University. This allows forward and backward chaining as well as a method of representing knowledge by so-called frames. MIKE will run with the Keylink Interpreter and is introduced in the next chapter. For those wishing to study Expert Systems and Knowledge Engineering MIKE is highly recommended.

13.1 About MIKE
MIKE stands for Micro Interpreter for Knowledge Engineering. It was written by the Open University and version 1.5 is in the public domain. The Open University also supplies a study pack (code PD624) for MIKE which contains tutorial text, a 180 minute VHS video and a 60 minute audio cassette. The study pack may be obtained from:
Learning Materials Sales Office The Open University
P.O. Box 188
Milton Keynes
MK7 6DH
Tel: [+44] (0908) 653338 Fax: [+44] (0908) 653744
MIKE supports a variety of Expert System approaches which includes forward and backward chaining and the use of frames. It is ideal for teaching many of the components of the Scottish Higher concerned with Knowledge Representation and Expert Systems.
13.2 Using MIKE with Keylink Prolog
There are just two source code changes that must be made to the MIKE V1.5 source code to enable it to be successfully consulted and executed using Keylink Prolog. In loadops.pl change the line:
?- op(999,fx,[make_value,add_value]).
to:
In engine2.pl change the definition of the clause:
?- op(999,fx,make_value). ?- op(999,fx,add_value).
Installing Prolog 147
13 MIKE

148 Installing Prolog
in_wm(prolog(X)):- !,
X.
to:
You can consult MIKE with:
?- consult(‘mike.pl’)
The ‘mike.pl’ file has a series of ?-reconsult directives that cause all the other MIKE files to be consulted. It expects all the other MIKE files to be in the current directory. Consulting ‘mike.pl’ may take up to a minute or two. A convenient method for reducing this delay in future MIKE sessions is outlined below, under ‘Fast loading MIKE’.
These are all the changes needed for the PC or Nimbus user. However you will almost certainly want to change the editor which is used in the ‘ed’ predicate defined in file ‘mike.ini’.
Notes for Archimedes users
If you are an Archimedes user you will also need to change file names to suit the Archimedes. It is recommended that you change the dot extension (.pl) part of the DOS filenames with underscore extension (_pl). For example: loadops.pl becomes loadops_pl. You will need to find and change all occurrences of file names in MIKE to follow this convention. These occur in mike.pl and mike.ini. Take care, when consulting ‘mike_pl’, that the current directory is where the MIKE source files are. Note that any successfully consulted file is given file type of Kprolog, that is it assumes from this point on the Prolog icon. All the MIKE files and knowledge bases are genuine Prolog files so they are legitimately given the Prolog file type. However, they cannot be understood by Prolog without MIKE being loaded. This is because MIKE defines many of its own operators in Prolog (see the file ‘loadops.pl’). Therefore it makes no sense to double click on, or drag into Prolog, any of the MIKE files except ‘mike_pl’ (and in this case the current directory must be set to that of the MIKE sources). The same is true of the knowledge bases, these should always be loaded using MIKE’s command ‘kb’.
Fast loading MIKE
When you have successfully consulted MIKE you may wish to make a fast loading version using msave. This will enable you to load MIKE in seconds rather than minutes. You should consult Chapter 14 for instructions on how to do this.
in_wm(prolog(X)):- !,
call(X).

13.3 MIKE Architecture
If you have read and tried the examples in the previous chapter you will find many of the concepts in MIKE familiar. As with the expert system shell we built in the previous chapter MIKE is a Prolog program that allows various styles of rules to be defined and executed. We mostly work with MIKE by giving it commands and goals to the usual Prolog query prompt and terminating them with a full-stop.
As well as interacting with MIKE we can also call Prolog goals, including built-in predicates, directly.
MIKE consists of a Working Memory which consists of Prolog atoms, single quoted strings, lists, and Prolog structures. We expect the working memory to contain the data that is relevant to the current state of play of the rule-base that is being executed. We can think of it as a kind of scratch area or blackboard upon which various partial deductions and other results are placed.
MIKE also has a rule memory where ‘if…then…’ production rules are stored. This clearly forms the deductive component of the expert system that is to be executed.
Our effort in constructing an expert system in Mike is directed at formulating these rules.
MIKE has an inference engine, or strictly speaking, it has several inference engines, that allow it to apply the rules to the working memory and make deductions. Having several different inference engines allows it to apply its rules in fundamentally different ways such as forward and backward chaining which were discussed in the previous chapter.
MIKE has a command set which allows users to interrogate the state of the rule base and working memory. It also provides a range of diagnostic facilities so that we can test and debug our rule sets.
MIKE also has some rather advanced features such as Frames, Truth Maintenance and Demons, some of which will all be discussed later in this chapter.
13.4 Running MIKE
The main MIKE file that must be consulted from Prolog is ‘mike.pl’. This contains a rule which loads the set of Mike Prolog source files that constitute the MIKE system. If you look at the mike.pl file you will see the following rule:
loadmikesources :-
write(‘Loading auxiliary MIKE files’), reconsult(‘loadops.pl’), write(‘loadops loaded’),nl, reconsult(‘engine1.pl’), write(‘engine1 loaded ‘),nl, reconsult(‘engine2.pl’), write(‘engine2 loaded’),nl, reconsult(‘fc_exec.pl’), write(‘fc_exec loaded’),nl, reconsult(‘io.pl’), write(‘io loaded’),nl, reconsult(‘util.pl’), write(‘util loaded’),nl, reconsult(‘findall.pl’), write(‘findall loaded’),nl, reconsult(‘browse.pl’), write(‘browse loaded’),nl,
Installing Prolog 149

150 Installing Prolog
reconsult(‘worlds.pl’), write(‘worlds loaded’),nl,
reconsult(‘xtend.pl’), write(‘xtend loaded’). /* Use xtend.pl for personal extensions */
Each of these files provides part of the functionality of Mike. For example, the inference engines are defined in engine1.pl and engine2.pl. Even if you are not going to use all of Mike’s functionality it is important to load all of the files. So do not be tempted to edit mike.pl or any other of the Mike source files.
All of Mike’s source files should be kept in a single directory. If you are using DOS or RiscOS you must make this the current directory.
Consult the file by using the query:
?- consult(‘mike.pl’).
or if you are using Windows, use the menu sequence File/Open, then use the file dialog to go to Mike’s directory and select mike.pl.
As Mike loads it reports on the successful loading of each source file and then displays a MIKE Copyright banner.
All of Mike’s examples are in files with the extension ‘.kb’, for Knowledge Base. On RiscOS the files will terminate with ‘_kb’. As an example we’ll run the tea making knowledge base. Enter the following query:
?- kb ‘teamakin.kb’.
Notice the space between kb and the file name, the use of single quotes around the file name, and the full-stop at the end.
Mike will output a set of statistics concerning the knowledge base that it has just loaded and you will again be faced with the normal Prolog query prompt.
We can ask Mike to display the current contents of working memory by entering:
?- wm.
You will see that Mike currently has nothing in its working memory. This is a normal state when a knowledge base has not yet been executed and no working memory entries have been explicitly provided by you.
The tea making example is a forward chainer, and we can invoke the forward chaining inference engine with the Mike command ‘fc’. Enter the following query:
?- fc.
Mike will invoke the forward chainer on the current knowledge base and you will immediately see the results which consist of a set of instructions on how to make a cup of tea.
We can interrogate the contents of working memory again with the query:

?- wm.
This time you will see that there are 10 working memory entries. All of these entries bar one, describe a state during the process of making a cup of tea which Mike will have used when determining what to do next. The working memory entry ‘start’ is rather special and is discussed later in the chapter when we take a closer look at using Mike for forward chaining.
13.5 Backward Chaining
The syntax of a MIKE backward chaining rule is:
rule backward if
&
& …
then .
Notice that the rule is terminated with a full-stop. ‘rule’, ‘backward’, ‘if’, ‘&’, and ‘then’ are all symbols that Mike recognises. These have been declared as operators in the Mike source file ‘loadops.pl’ using the Prolog built-in op/3.
The rule name is an arbitrary Prolog atom that the knowledge engineer uses to label his rules.
The various conditions that must be satisfied (the antecedents) are separated by logical conjunctions, repesented in Mike by the ‘&’ symbol. We can also use disjunctions which are represented by the symbol ‘or’.
The conditions may be:

i.e. something to be matched against working memory, for example an atom such as red, or a string such as ‘light is red’, Prolog lists and structures are also valid, these may contain variables as in colour(X).
—
A negation of a working memory pattern, i.e. exactly the same as above but the condition must not match a working memory element.
deduce
Similar to the above, but here the working memory pattern is expected to match by invoking rules rather than matching directly on a working memory element, hence the keyword ‘deduce’, the working memory pattern is expected to be deduced. We sometimes refer to this as triggering further backward chaining.
prolog()
Installing Prolog 151

152 Installing Prolog
This enables us to pass an arbitrary goal to Prolog. It is commonly used to perform arithmetic which Mike does not support directly. So we might calculate a volume, for example, with prolog(V is H*W*L).
query
This enables us to ask the user of the knowledge base a question as the knowledge base is executing. Mike recognises a variety of templates which can be used to get yes/no type answers, or text from the user, or even display a list of options for the user to select from.
The conclusion:

The conclusion of a rule is proved when all the left hand side conditions are satisfied. It is just simply proved, i.e. shown to be true, it is NOT added to working memory.
Example: The creatures knowledge base, ‘cr_b.kb’. This uses a set of backward chaining rules to determine the type of animal when the user gives values to various animal characteristics. Many of the rules, quite naturally, have left hand sides which consist of user queries and conclusions that give the user’s response:
rule body_covering backward
if query ‘What is the body_covering?
(hair/feathers/other/unknown) ‘ receives_answer X
& prolog(X=Y)
then body_covering(Y).
This rule, called ‘body_covering’, uses a query to ask the user what type of body covering the animal has. This particular form of query template expects the user to type an arbitrary atom which is instantiated to the variable which is the argument to receives_answer. The text of the question tries to prompt the user into supplying an answer which is going to be meaningful to the knowledge base.
An example which uses deduce is:
rule mammal_1 backward
if deduce body_covering(hair) then mammal.
i.e. if a rule or rules can be invoked that conclude that the body covering is hair, then this rule can conclude that the animal is a mammal.
A rule using several instances of deduce is:
rule feeding_type_1 backward if deduce mammal
& deduce eats(meat)

then feeding_type(carnivore).
The semantics or meaning of this should be clear.
Briefly have a look at the entire creatures knowledge base using an editor or print it out for reference. Ignore anything to do with explanation for the moment.
Run the example by loading Mike into Prolog and then loading the creatures knowledge base with the query:
?- kb ‘cr_b.kb’.
We need to invoke the backward chainer explicitly by using deduce followed by the conclusion we wish the backward chainer to reach. For example:
?- deduce species(X).
This is an example dialog:
What is the body_covering? (hair/feathers/other/unknown) ==> |: feathers.
What does it feed its young on? (milk/other/unknown) ==> |: unknown.
How does it move? (flies/swims/walks/unknown) ==> |: swims.
What is the colour? (tawny/black_and_white/other/unknown) ==> |: black_and_white.
X = penguin
Exercise 13a: choosing a pub
Write a simple backward chaining expert system which determines which pub to go to. Try to structure the questions into determining answers which can be used in several rules. For example, ask what kind of drink is liked, rather than asking ‘do you like real ale’ in one place and ‘do you like spirits’ in another. You may like to take a copy of the creatures knowledge base and modify it. This gives you a much greater chance of getting the syntax correct.
You should be able to start the system with the query:
?- deduce recommended_pub(X).
Here are some ideas for rules, please refine and expand these, but try to get a small knowledge base working first.
Installing Prolog 153

154 Installing Prolog
likes loud rock music, real ale, money no object => dog and trumpet must be cheap, likes students => union bar
likes irish music, mixed company and drinking guinness => eight bells likes live music, young company and anything to drink => silver sword likes refined company, drinking spirits, dislikes music, money no object => de vere
13.6 Providing ‘canned’ explanation to ‘Why?’
Simple explanation can be provided to questions of the ‘Why’ variety via the ‘explained_by’ keyword. Take the body_covering rule from the creatures knowledge base:
rule body_covering backward
if query ‘What is the body_covering?
(hair/feathers/other/unknown) ‘ receives_answer X
& prolog(X=Y)
then body_covering(Y).
We can provide a canned explanation for why this rule is being invoked with the following:
‘What is the body_covering? (hair/feathers/other/unknown) ‘
explained_by
[‘If the body covering is known to be hair’, nl,
‘then it can be concluded that the creature is a mammal.’, nl,
‘If it is feathers, then the creature is a bird’].
What comes before the explained_by keyword must match the query text exactly. I call the explanation ‘canned’ because there is no intelligence to it whatsoever, it is simply text to be reguritated at the user word for word when the user types ‘Why?.’. However, given its simplicity it can transform a system from being totally unhelpful to being quite user friendly when seen from the user’s perspective.
Now when the user is asked the question:
What is the body_covering? (hair/feathers/other/unknown)
and the user enters:
why.
The canned explanation text will be displayed and Mike will then wait for the answer.

Excercise 13b:
Provide explanation of the ‘canned’ variety to your pub knowledge base.
13.7 Forward chaining
The syntax of a forward chaining rule is:
rule forward if
&
& …
then
&
&…
& .
Notice that instead of a conclusion we have any number of actions which will typically assert something into working memory.
The conditions may be:

i.e. something to be matched against working memory, as described for backward chaining.
—
A negation of a working memory pattern.
deduce
We can trigger backward chaining from a forward chaining rule!
prolog()
This enables us to pass an arbitrary goal to Prolog.
query
Enables us to ask the user questions, as described for backward chaining rules. RHS actions can:
Modify working memory:
add
remove
Installing Prolog 155

156 Installing Prolog
Provide output:
announce
Perform arithmetic:
:=
Query the user:
query receives_answer ask_menu(