~1 LOGIC PROGRAMMING LESSON 5 This lesson is about errors, numbers, and comparisons. ~2 Please start by switching your logic programming tutor into Prolog mode, and then loading facts from the knowledge base in "mars". The "load" command was introduced in Supplement 1, and is like "restore" in that it expects to be given the name of a file. However, it only loads facts into the database, and so you can't "show" them, though you can ask questions about them. Files that you load are also inaccessible to "restore" (and vice versa): if you try to restore mars, the Tutor will tell you that it can't find the file. So, give the two commands: prolog. load mars. ~3 You now have a number of facts defining the predicate "costs", which gives the prices of sweets. They all follow the pattern costs( mars, 15 ). where the first argument is the name of a sweet, and the second is a NUMBER representing its price in p. So far, we have used ATOMS and VARIABLES in facts. We haven't said much about what you can do with numbers, though they did crop up in various exercises. Please note that these numbers should not include units: Prolog will not accept facts like costs( mars, 15 pence ). So, for the moment, you must just remember (or make a note) of what the numbers in each fact refer to: pence, dollars, yen, volts, shocks on the Richter scale, population density in heads per hectare... ~4 Now try asking Prolog questions which will answer the enquiries below. 1) What is the price of a Nutty? (I've used the atom "nutty" for this sweet). 2) What are the sweets that cost 15p? 3) Now, by asking ONE question with an "and" (i.e. a comma) in it, find those things which cost the same as a Marathon (I've used the name "marathon" for that sweet). ~5 By now you should be able to do the first two with ease. To do the third, translate this into Prolog: Find a P and S such that a Marathon costs P, and there exists a sweet S such that S costs P. ~6 Here are the answers. Of course, you can use whatever names you want for the variables, as long as they start with a capital letter. 1) costs(nutty,What)? 2) costs(What,15)? 3) costs(marathon,P), costs(S,P)? The third question can be understood as "Find all S costing P, where a Marathon costs P". This way of using the variable P is a frequent trick of logic programmers: one part of the question gives the variable a value, and a later part of the question finds facts which mention that value. ~7 A note on idioms: Each programming language has its own idioms: frequently occurring combinations of commands which experienced programmers recognise without detailed analysis. Basic programmers, for example, recognise the commands FOR i = 1 TO 10 : LET a(i) = 0 : NEXT i as an idiom meaning Set each element of array a to zero The Marathon example demonstrates a Prolog idiom worth recognising: schematically, the question Thing has property P and Object has property P ? finds Objects with the same property P as Thing. Thus, costs(marathon,P), costs(S,P)? finds sweets with the same cost as a Marathon has. (POLITE NOTICE: Of course, some statements look like common idioms but aren't - care is essential). ~8 I shall now introduce comparisons. In programming, it's useful to be able to compare numbers. You can get a long way without them, but they do come in useful eventually. Prolog provides several predicates for such comparisons. Two of them are > and <, meaning greater-than and less-than. Comparisons occurred in the skiing knowledge base, when you were using the Tutor in Logic mode, but I didn't say anything in particular about them. To see how they work in Prolog, try a few questions like >( 1, 2)? <(45,74)? ~9 That you got sensible answers to these shows that you can use > and < just like any other predicate. However, it's inconvenient for us to have to put brackets around the arguments to these symbols, because we're so used to seeing expressions like 1>2 and 45<74 in maths. Prolog therefore allows us to write these comparisons more naturally as 1 > 2? 45 < 74? Try this. Note that it is grammatically correct even when you are as now in Prolog mode and not Logic. We say that the comparison predicates are OPERATORS - this is Prolog jargon for predicates that can be written between their arguments, a la maths. ~10 You can use these predicates in questions. Can you formulate one question that ask which sweets cost more than 15p? ~11 Some people find this tricky, and are tempted to ask something like What > 15? which is incorrect. This temptation is probably because English allows "What costs more than 15p?". However, in Prolog, you can't abbreviate in this way, and you must painstakingly build up the question as a sequence of elementary questions separated by comma. If you have no idea how to attack this, try translating the question below into Prolog: Find an X such that X costs P and P > 15. ~12 You should have asked costs( X, P ), P > 15? though perhaps with different variable names. If you're not convinced, ask the question above, and then use the "analyse" command as demonstrated in Lesson 4. This will give you a translation back into English. ~13 You also have some facts defining the "likes" predicate, where the first argument is someone's name, and the second names a sweet. Try translating Who likes sweets costing more than 15p? into one Prolog question. ~14 If you're having trouble, try translating this form: Find an S such that W likes S and S costs P and P > 15? ~15 You should have got likes(W,S), costs(S,P), P > 15? (but perhaps with different variable names). ~16 Now try What sweets cost more than 13p and less than 20p? ~17 If you're having trouble, think of it as Find an S such that S costs P and P > 13 and P < 20? ~18 You should have got costs(S,P), P > 13, P < 20? As before, if you can't see why, try translating back into English, either on your own, or with the help of analyse. Next, try Who likes sweets that cost more than a Mars Bar? ~19 Think of it as Find an X such that X likes S and S costs P and mars costs M and P > M. ~20 The answer should have been something like likes(X,S), costs(S,P), costs(mars,M), P > M? ~21 Finally, try Who likes sweets that cost more than the one that Adam likes? ~22 Hint: think of it as Find an X such that X likes XS and XS costs XP and adam likes AS and AS costs AP and AP < XP? ~23 Now for a change of viewpoint. Some people always ask how Prolog knows that 2 > 1 and that 32 > 2. Does it have a gigantic set of facts somewhere which say things like 2>1. 3>1. 4>1. ... 3>2. 4>2. 5>2. ... 4>3. 5>3. 6>3. ... and so on for all the numbers which you could ever ask about? The answer is no. All computers have special instructions for comparing numbers. When answering most predicates, Prolog looks up the answers in the database. However, when it encounters > and <, it treats them as special, and runs the number-comparison instructions to get an answer. For this reason, we say that > and < are BUILT-IN. You don't have to define them: the implementor has done so already. ~24 You can confirm this by trying to ask a question like mars > twix ? then Prolog will give you an ERROR-MESSAGE , saying that it can't answer the question (you may have seen all too many error messages already, if you have mis-typed things). The message will say that > needs numbers. This is entirely fair. Mars Bars and Twixes are not numbers, so you can't compare them (to be exact, you can't compare their names). ~25 Perhaps we could fool Prolog into believing that mars > twix, by asserting the fact mars > twix. Go on, try it. Prolog will give another message, saying that you are not allowed to update built-in facts. The reason for this is efficiency. It is much faster for a computer to use its number-comparing instructions than for it to search the knowledge base for answers. Most programmers want numerical operations like > to be as fast as possible, and very few want to write facts like "mars > twix". The optimum engineering solution is to make Prolog prohibit such extra facts, so that it can always use the number-comparing instructions, and run comparisons as fast as possible. ~26 Still concerning error messages and speed, try asking X > 1 ? Logically, this means 'which X are greater than 1?' or 'find all numbers bigger than 1'. Prolog will not give you the answers; instead, you will get another error. This is because there is an infinity of numbers greater than 1, and to generate them all would take longer than I have for the course, especially with the VAX as slow as it is today. Instead, Prolog rejects the query, and insists that when you use > , each side has a (numeric) value. ~27 You have now seen two kinds of error. The first is where Prolog rejects input which ought to be reasonable, in order to run more quickly (in "X > 1?"). This is one of many instances where Prolog does not do everything that logic does. The cave-world exercise in Supplement 2 was another instance of this, where you may have written predicates that were logically correct, but that got Prolog into an infinite loop. Yet another instance is that Prolog won't let you assert two facts in one go by using "and" in the head, as in loves(john,mary), likes(mary,wine). The second kind of error is where Prolog rejects rubbish ("mars>twix"). Much of the business of programming is learning the details of a language (to avoid the first kind of error), and learning how to make programs do only sensible things (avoiding the second kind). ~28 Now let's look at the order in which Prolog evaluates things. Consider the question costs(S,P), P > 15? Now, try re-ordering it as P > 15, costs( S, P )? You will get yet another error-message: once again, > needs numbers. Why? Surely the erroneous question is logically equivalent to one which works? And surely Prolog will accept anything which is logically valid? The reason for the error is that Prolog answers questions from left to right. It can't find a value for P until answering the second part of the question - "S costs P"?. By then, it has already tried to compare P with 15, despite P not yet having a value. This is another way in which Prolog will reject some logically valid commands. When using > , remember that questions are answered from left to right, and that variables being compared must have received their values from earlier parts of the question. ~29 Now for some more comparison predicates. As well as the built-in predicates "<" and ">" , Prolog recognises several others. The complete set is: > < =< >= \= = The final four symbols mean 'less than or equal to', 'greater than or equal to', 'not the same as', and 'equal'. A handy mnemonic for which way round to write =< and >= is that you place the equals in such a position that the signs don't look like arrows. So <= and => are WRONG. These combinations of symbols are the nearest that your keyboard can come to the mathematical equivalents - even modern computer keyboards do not contain more than about 100 printable symbols. ~30 Now that you have the \= operator, can you ask a question to find all sweets that don't cost 15p? ~31 Think of it as Find an X such that X costs P and P is not equal to 15? ~32 The = and \= operators can be used to compare atoms as well as numbers. So whereas mars > twix? will give an error, mars = twix? and mars \= twix? will not. Can you now ask one question that finds the price of all sweets that are neither Yorkies nor Mars bars? Use atoms "yorkie" and "mars". ~33 Think of it as Find an X such that X costs P and X isn't a yorkie and X isn't a mars bar. ~34 You should have typed something like costs( X, P ), X \= yorkie, X \= mars? ~35 Now, can you find all items which are NOT Marathons? Not their prices, but just their names. ~36 That was a trick question. Some people will have tried the answer costs( X, P ), X \= marathon? on the assumption that the "costs" predicate mentions every sweet worth talking about. ~37 Others will have tried this: X \= marathon ? If you did that, Prolog would have replied "no", and not set X to anything. Why? Well, the nearest Prolog could get to an answer would be to generate an infinite number of names, naming non-Marathons (perhaps: mars, galaxy, nebula, black hole, whitehall, front hall...). This is both impossible and not useful, rather like wanting a solution to X > 1. So the implementors of Prolog have made things easy for themselves by saying: we shall only make \= work sensibly if, when it's comparing variables, both those variables have already been set. Otherwise, we'll just make it give the (misleading) answer "No". ~38 In practice, when asking such a question, you will have some classification in mind - in this case, into kinds of food. Perhaps something like type_of(mars,sweet). type_of(tango,drink). type_of(peperami,savoury). and so on. You can then ask questions like type_of(X,food), X \= marathon ? That's the best way to deal with situations where you may need a list of all the individuals that aren't something else. ~39 To summarise what has gone so far: You can use NUMBERS as arguments to predicates. Prolog provides BUILT-IN predicates for comparing numbers. These are > >= =< < \= = You can write these BETWEEN their arguments, without brackets. That resembles maths notation: for this reason, they're called OPERATORS. You will get an ERROR-MESSAGE if you try to compare atoms (i.e. names) with these predicates. You will also get one if you try to re-define them by adding facts like 1 > 2. mars > twix. ~40 Although a question like X > 1? makes logical sense, Prolog won't answer it. Instead, it will give you an error. That's because the question has an infinite number of answers, and the computer is only finite. The questions costs(S,P), P > 15? and P > 15, costs( S, P )? are logically equivalent. However, Prolog can't answer the second one. That's because it works from left to right inside questions, and the variable P must have gained a value in order for the comparison to work. ~41 There are two operators for comparing non-numeric (as well as numeric) items. These are \= = Like the numeric comparisons, \= can't be used to compare variables that have no value. A question like X \= marathon can't be answered, because it would have to generate an infinite list of individuals, most of which would have nothing at all to do with your program (although, for this lesson, you may care that a Mars isn't a Marathon, you don't care that elephants, abstract justice, and pandiculation aren't one either). But in this case, Prolog doesn't give an error message. Instead, it (misleadingly) says "No". ~42 To make all the comparison operators safe, so that they behave as logic dictates they should, you should simply remember that Prolog answers questions from left to right. Always put the comparison operators in such a position that any variables they compare will already have gained values. ~43 Finally, a word on Prolog execution in general. We have seen that Prolog answers questions from left to right. Another aspect of execution is in which order it visits facts. Given the facts loves(john,mary). loves(hendrik,elaine). which order do you get the solutions in when you ask loves(X,Y)? The answer is: from top to bottom. When trying to answer a simple goal, Prolog starts at the top of the database and works downwards. ~44 There is more to Prolog execution than this. Suppose you ask loves(X,Y), Y \= mary? with the above facts stored. What Prolog does is to start at the left of the question with the first goal, for loves. It searches down the database until it can get an answer. This gives it X as john and Y as mary. Having got an answer for the first part of the question, it now resumes its left-to-right progress, and tries to answer the comparison. Here, it finds that Y\=mary is false. Now, some systems might give up at that point. But Prolog has been designed to try all possible combinations. It returns, or BACKTRACKS, to the loves(X,Y) and tries RE-DOING it, looking for the next fact down. This gives it another answer, X as hendrik and Y as elaine. With this new answer, it resumes its rightward movement, and again tries Y\=mary. This time, it is true, and therefore the whole question succeeds. ~45 I shall not say more about the order of execution here: it's best explained individually, and with plenty of diagrams, by your teacher. However, if you want to watch Prolog at work, you can use the "trace" command. This is a bit like "why". It takes the previous question you typed, and re-runs it, writing out details about everything Prolog does on the way. So if you have just asked loves(X,Y), Y \= mary? and you then say trace. you will be able to observe Prolog visiting each fact and each part of the question. Remember that we also call facts, CLAUSES: this is also how trace refers to them. The output from trace can be quite voluminous. As with "why", you can send it to a printer, so trace ctc. will send the trace to the CTC printer. ~46 You might now try tracing some questions. Start with really simple ones, otherwise you will drown in the output. For instance, you might delete all facts, enter ONE fact about loves, and ask a question about it. Choose one question that will succeed, and another that will fail, and see what trace shows in each case. Then work up to two loves facts, like those I showed above, and ask a question which depends on the bottom one, such as loves(hendrik,X)? loves(X,Y)? Then try a compound question such as loves(X,Y), X \= mary? You can try the same kind of thing with the "mars" knowledge base, using the comparison operators. Doing this should give you a feel for the way that Prolog orders its inferences, and how this way of doing things enables it to give logically correct answers. ~47 You have now reached the end of Lesson 5. Before going on to Lesson 6, please do any exercises your teacher has set for this lesson.