/* logic\$lib:lesson6.SCR */ script_text( 1, ' LOGIC PROGRAMMING LESSON 6'~<> ''~<> ''~<> 'This lesson starts by continuing a theme of Lesson 5: arithmetic,'~<> 'numbers, and how Prolog\'s treatment of them differs from formal logic. I'~<> 'shall finish by introducing the "not" predicate properly.'~<> ''~<> 'Please type'~<> ' prolog.'~<> 'to switch your Logic Programming Tutor into Prolog mode; then go on to'~<> 'the next section.'~ ). script_text( 2, 'Lesson 5 introduced the BUILT-IN comparison operators. We said they are'~<> '"built-in", because Prolog can understand their occurrence in questions'~<> 'without requiring you to write facts defining them. If > were not'~<> 'defined, you could do so for yourself by adding lots of facts like'~<> ' 1 > 0. -1 > -1000. 9639172 > 92646.'~<> 'and so on. This is not entirely feasible - it might take perhaps 3000'~<> 'years to add facts comparing all the numbers between nought and a'~<> 'million.'~<> ''~<> 'The implementors of Prolog therefore ask the computer hardware to do the'~<> 'comparisons - modern computers take about one-millionth of a second to'~<> 'compare two numbers. Letting the hardware do the work does impose some'~<> 'restrictions: as you\'ve found, you can\'t ask "X > 1?" and get a list of'~<> 'all numbers greater than 1, or even a representative selection.'~ ). script_text( 3, 'We have seen how to compare numbers; but how can we calculate them in'~<> 'the first place? The answer is: by using the special word "is". Like the'~<> 'comparison operators, "is" is INFIX: it goes between its arguments. The'~<> 'argument on the right is a formula whose value is to be computed; the'~<> 'argument on the left is a variable that\'s to receive its value.'~<> ''~<> 'To see what "is" does, try these questions (if you\'re new to computers,'~<> 'they\'ll give you practice in finding the arithmetic keys):'~<> ''~<> ' X is 8+2?'~<> ' X is 8-2?'~<> ' X is 8*2?'~<> ' X is 8/2?'~<> ' X is 8^2?'~<> ' X is 8 mod 2?'~ ). script_text( 4, 'The first two are obvious: addition and subtraction. The third is'~<> 'multiplication: the keyboard symbol most frequently used for this is'~<> 'irritatingly different from the mathematical symbol. The next is'~<> 'division.'~<> ''~<> 'The final two are used less frequently. 8^2 means 8 to the power 2'~<> '(eight squared); similarly, 8^3 would be eight cubed.'~<> ''~<> '8 mod 2 is eight remainder two, which should have come out to zero.'~<> 'Similarly, 8 mod 3 would be the remainder on dividing eight by three,'~<> 'i.e. two. Remainder is useful for operations like, given a number of'~<> 'days (say 23), how many days remain after taking away all the complete'~<> 'weeks. You could calculate this by doing'~<> ' X is 23 mod 7?'~ ). script_text( 5, 'If you have programmed before, you may be used to different symbols.'~<> 'Some languages use ** instead of ^ ; some use "rem" instead of "mod".'~<> ''~<> 'If you\'ve done some mathematics, it\'s also worth noting that you can\'t'~<> 'use dot or juxtaposition for multiplication:'~<> ''~<> ' X is A B?'~<> ' X is A.B?'~<> ''~<> 'to multiply A by B will not work as intended. Always write'~<> ''~<> ' X is A*B?'~ ). script_text( 6, 'There are two syntactic quirks worth noting. The first occurs in a'~<> 'question like'~<> ''~<> ' X is 8mod2?'~<> ''~<> 'If you try this, you should get a syntax error. The reason is that'~<> 'Prolog treats "mod2" as one word, not as "mod 2". In general, two'~<> 'alphanumeric words must be separated by at least one space; so must a'~<> 'word and a following number. So always leave a space after the "mod".'~ ). script_text( 7, 'Similarly, you might think that'~<> ''~<> ' X is 8--2?'~<> ''~<> 'would mean "X becomes the result of taking -2 from 8, i.e. 10. That'~<> 'would be incorrect. We saw in Lesson 5 that Prolog treats >= and =< as'~<> 'one operator, not as two adjacent ones. This is a general rule. If you'~<> 'run lots of special symbols together without spaces, Prolog treats them'~<> 'as one. So in'~<> ''~<> ' X is 8*-2?'~<> ''~<> 'it would treat the *- as one operator, not as a multiply followed by a'~<> 'minus.'~ ). script_text( 8, 'To get round this, you must leave a space between them. Instead of'~<> 'writing'~<> ' X is 8--2?'~<> 'write'~<> ' X is 8- -2?'~<> ''~<> 'This problem will not occur frequently in arithmetic, because the only'~<> 'time two operators can go next to one another is when the second is a'~<> 'minus. However, it\'s worth bearing in the back of your mind for when you'~<> 'use operators elsewhere in more advanced work.'~ ). script_text( 9, 'Brackets can be used in the obvious way. As in maths,'~<> ' X is 2*3+5?'~<> 'will set X to 11, but'~<> ' X is 2*(3+5)?'~<> 'will set it to 16.'~<> ''~<> 'An important point is that the conventions about how things are'~<> 'bracketed may be different from what you\'re used to. For example, does'~<> ' 8^3/3'~<> 'mean (eight cubed) all divided by three, or does it mean eight to the'~<> 'power (three divided by three)? Try it and see.'~ ). script_text( 10, 'Trying it is easy: ask'~<> ' X is 8^3/3?'~<> ''~<> 'You should have got the answer X=170.667. This is the same answer that'~<> 'you\'d get if you asked'~<> ' X is (8^3)/3?'~<> 'whereas'~<> ' X is 8^(3/3)?'~<> 'would give you eight to the power one, i.e. eight.'~<> ''~<> 'From this, we can see that brackets are inserted preferentially around'~<> 'the ^ . More on this below.'~ ). script_text( 11, 'You probably learnt at school, rules about whether to deal with the'~<> 'addition or the multiplication first in a formula like 2*3+5. Similar'~<> 'rules apply in Prolog. If you type'~<> ''~<> ' X is 1+2*3?'~<> ' X is 1+(2*3)?'~<> ' X is (1+2)*3?'~<> ''~<> 'you will obtain the answers 7, 7, and 9. The operator * is said to have'~<> 'greater PRIORITY than the operator + , because if they appear both'~<> 'unbracketed next to each other, the formula is interpreted as if the'~<> 'part containing * were bracketed. Sometimes we say that * BINDS MORE'~<> 'TIGHTLY than + .'~<> ''~<> 'Similarly, you now know that ^ binds more tightly than / .'~ ). script_text( 12, 'Prolog has about 20 special operator symbols, of differing binding'~<> 'powers. It is important to get their precedences right, otherwise you may'~<> 'produce wrong result, by thinking Prolog inserts brackets where it'~<> 'doesn\'t. Ambiguities occur in natural language too: consider'~<> ''~<> ' Serve hot or cold with cream.'~<> ' Shampoo and rinse until clean.'~<> ' The crash was caused by the driver of a lorry full of gin.'~<> ' The lilies of the valley of the shadow of death.'~<> ' The Minister of the Interior of the Prince.'~<> ''~<> 'When writing arithmetic, it\'s safest to insert brackets whenever two'~<> 'operators are competing, unless they are + and * . Everyone knows that +'~<> 'binds less tightly than *, and luckily Prolog agrees. So if you write'~<> ' X is 1+2*3?'~<> 'there is no danger of another reader misunderstanding you. The rules for'~<> '^, /, mod etc are less well-known: if you write 8^3/2, YOU may know you'~<> 'meant (8^3)/2, but your teacher may have forgotten the rules, and think'~<> 'you meant 8^(3/2). It\'s made worse because different computer languages'~<> 'bracket in different ways. So use brackets to make things clear.'~ ). script_text( 13, 'What I\'ve just taught you about priority is necessary but not'~<> 'sufficient; it doesn\'t help with strings of one operator, like'~<> '1-2-3-4-5.'~<> ''~<> 'Try evaluating'~<> ''~<> ' X is 3 - 2 - 1?'~<> ' X is (3 - 2) - 1?'~<> ' X is 3 - (2 - 1)?'~<> ''~<> 'Where do the implicit brackets go?'~ ). script_text( 14, 'Answer: on the left. The first formula is equivalent to the second, as'~<> 'far as Prolog is concerned. The - operator is said to be'~<> 'LEFT-ASSOCIATIVE, or to ASSOCIATE TO THE LEFT, because when two minuses'~<> 'adjoin in a formula, the leftmost one is implicitly bracketed.'~<> ''~<> 'Again, the moral is: use brackets to make things clear. You will help'~<> 'other readers, and you will help yourself, when you read your program'~<> 'six months after it was written.'~<> ''~<> 'The material between sections 6 and 14 is what every new user of a'~<> 'programming language has to learn about that language\'s syntactic'~<> 'peculiarities. It\'s not exciting, but it must be borne in mind to avoid'~<> 'mistakes. From now on, I shall assume you can apply such principles to'~<> 'other parts of Prolog, so I shall now turn to the more interesting topic'~<> 'of how you can use these calculations.'~ ). script_text( 15, 'For something to do with arithmetic, assume that the exchange rate from'~<> 'pounds to dollars is 1.4 (well, it was when I wrote this in January'~<> '1984...). In Lesson 5, we considered the prices in pence of sweets.'~<> 'Suppose that we want to write one question which finds the price of a'~<> 'Twix, not in pence, but in dollars. Using the knowledge base "mars", we'~<> 'would write something like'~<> ''~<> ' costs( twix, Pence ), Dollars is Pence * 0.014 ?'~<> ''~<> 'This is a compound question, with whose first part you are familiar - it'~<> 'puts the price of a Twix into the variable Pence. The second part of the'~<> 'question multiplies the value in variable Pence by 0.014, and places'~<> 'the result in the variable Dollars.'~ ). script_text( 16, 'We can use "is" in predicate definitions as well as in interactive'~<> 'questions. For example, consider the predicate'~<> ''~<> ' exchange( Pence, Dollars ) :-'~<> ' Dollars is Pence * 0.014.'~<> ''~<> 'We can understand this logically as meaning'~<> ' Dollars is the correct exchange for Pence if'~<> ' Dollars is equal to Pence * 0.014.'~<> ''~<> 'Try typing in the definition of "exchange" (make sure your Tutor is in'~<> 'Prolog mode first), and then try it out with questions such as'~<> ''~<> ' exchange( 10, D )?'~<> ' exchange( 10, 0.14 )?'~<> ' exchange( 10, 550 )?'~<> ' exchange( P, 0.14 )?'~ ). script_text( 17, 'As you might expect, the first question above takes the first argument'~<> '(a value in pence), and multiplies it by 0.014, putting that argument'~<> 'into the second argument.'~<> ''~<> 'The second question is a test. It asks, in effect, is 0.14 the correct'~<> 'dollar exchange for 10 pence? If you typed in the values as I gave them,'~<> 'you should have got the answer "yes".'~<> ''~<> 'Similarly, the third question should give the answer "no", because 550'~<> 'is not a correct dollar exchange for 10 pence.'~<> ''~<> 'What about the final one? Please go on to the next section.'~ ). script_text( 18, 'Now, logically speaking, the third question ought to set P to the pence'~<> 'value corresponding to 0.14 dollars. What it actually does though is to'~<> 'give an error saying ``numbers needed\'\'. After Lesson 5, you may not'~<> 'be surprised by this. What is happening is that, as ever, Prolog is'~<> 'falling short of logic. And once again, the reason is efficiency.'~<> ''~<> 'In a question like'~<> ' X > 1?'~<> 'the reason Prolog can give no answer is that there are too many possible'~<> 'solutions. Even if it were possible to enumerate them all, you wouldn\'t'~<> 'want to wait.'~ ). script_text( 19, 'The reason a question like'~<> ' 10 is Pence * 0.014?'~<> 'can\'t be answered is that Prolog is not an equation solver. This becomes'~<> 'clearer if we consider a question like'~<> ' 1000 is A+B*C+D+E/F?'~<> ''~<> 'Logically, this has a clear meaning. It means "what values of A,B,C,D,E'~<> 'and F make A+B*C+D+E/F equal to 1000? Implementationwise, such a'~<> 'question is not easy to answer. Automatic equation solvng requires'~<> 'clever techniques from artificial intelligence, and is best left to'~<> 'specialised algebra packages, not general purpose languages like Prolog.'~ ). script_text( 20, 'The upshot of all this is that "is" expects all the variables on its'~<> 'right-hand side to have values. This means that the "exchange" predicate'~<> 'above will only work if Pence has a value before the "is" is evaluated.'~<> ''~<> 'Now, suppose we define the predicate'~<> ''~<> ' total_cost( Weight, UnitPrice, TotalCost ) :-'~<> ' TotalCost is Weight * UnitPrice.'~<> ''~<> 'intending its logical meaning to be this:'~<> ' The total cost of Weight amount of goods, priced at UnitPrice'~<> ' per unit weight, is TotalCost if'~<> ' TotalCost equals Weight times UnitPrice.'~<> ''~<> 'You may use or have used something similar during the trading game.'~<> 'Which of these questions will work?'~<> ''~<> ' total_cost( 50, 0.2, TotalCost )?'~<> ' total_cost( Weight, 0.2, 10 )?'~<> ' total_cost( 50, UnitPrice, 10 )?'~ ). script_text( 21, 'The answer is, only the first. In the other two, one of the variables on'~<> 'the right-hand side does not have a value when "is" is called.'~<> ''~<> 'So, to summarise, efficiency demands that "is" is not reversible.'~<> 'Predicates written using it are used like functions in mathematics and'~<> 'conventional programming languages. You put numbers into some of the'~<> 'arguments, and you get new numbers out of other arguments.'~<> 'Conventionally, we talk about INPUT and OUTPUT arguments, so we say that'~<> 'the first two arguments of total_cost are inputs, and the third is an'~<> 'output.'~<> ''~<> 'If you try to run such predicates backwards, by putting numbers in the'~<> 'output argument(s), and expecting to get new numbers out of the inputs,'~<> 'you will get an error. Thus, the questions'~<> ' total_cost( Weight, 0.2, 10 )?'~<> ' total_cost( 50, UnitPrice, 10 )?'~<> 'will both give errors, because the first two arguments are both inputs.'~ ). script_text( 22, 'Now for a bit of practice with arithmetic. The next problem is taken'~<> 'from "Programming in Prolog", by Clocksin and Mellish. In knowledge base'~<> '"arith", you have a number of unconditional facts of the form'~<> ''~<> ' has_population( p, c ).'~<> ' has_area( c, a ).'~<> ''~<> 'The first means that country c has c million people; the second, that'~<> 'country c has an area of a million square miles. Restore "arith", and'~<> 'you will see what I mean.'~<> ''~<> 'Can you define a predicate "has_density(C,D)" which is true if country C'~<> 'has a population density of D people per square mile? You might use if'~<> 'in a question like'~<> ''~<> ' has_density( china, D ) ?'~ ). script_text( 23, 'The answer is in knowledge base "arith1".'~ ). script_text( 24, 'The conclusions I want you to draw so far are that:'~<> ''~<> ' If you want to evaluate a formula into a number, you must use the'~<> ' misleadingly named "is", with a variable on its left, and formula on'~<> ' its right:'~<> ' X is 2+2?'~<> ' Product is 1*2*3*4*5?'~<> ' DiffSq is (X-Y)*(X+Y)?'~<> ''~<> ' All the variables in a formula on "is"s right must have (numerical)'~<> ' values.'~<> ''~<> ' "is" is not reversible, so (assuming X and Y don\'t both have values)'~<> ' you can\'t get a sensible answer from'~<> ' 4 is X+Y?'~<> ' 21 is (X-Y)*(X+Y)?'~ ). script_text( 25, ' If a number is followed by a name (an atom), they must be separated by'~<> ' a space.'~<> ' 8 mod 2 is ok.'~<> ' 8 mod2 is not.'~<> ''~<> ' Leave spaces between different operators.'~<> ' 8- -2 means 8 - (-2).'~<> ' 8--2 will give an error.'~<> ''~<> ' The priority and associativity of operators are important. If in'~<> ' doubt, use brackets.'~<> ''~<> 'Incidentally, the reason that you could\'t use "is" as a varb on its own'~<> 'is that it has this special (and really rather badly named) arithmetic'~<> 'significance to Prolog.'~ ). script_text( 26, 'Now I shall go on to the last part of this lesson: not. This predicate,'~<> 'which was used in the animals classifier of Supplement 4, takes one'~<> 'argument, which must be a Prolog goal. It succeeds if a call to the'~<> 'argument would fail, and fails if that call would succeed.'~<> ''~<> 'For example, suppose you have the following facts (from file NOT).'~<> ''~<> ' is_a(joe,man). is_a(bill,man).'~<> ' is_a(jill,woman). is_a(sue,woman).'~<> ''~<> ' lives_in(joe,london). lives_in(bill,london).'~<> ' lives_in(jill,brighton). lives_in(sue,paris).'~<> ''~<> 'Then the question'~<> ' is_a(joe,man)?'~<> 'would succeed. Therefore, the question'~<> ' not( is_a(joe,man) )?'~<> 'would fail, as you would expect ("is it not true that Joe is a man?").'~ ). script_text( 27, 'Similarly, the question'~<> ''~<> ' is_a( M, man ), not( lives_in(M,london) )?'~<> ''~<> 'will find a M who is a man but does not live in London (note that the'~<> 'English meaning of "but" in this sentence is similar to that of "and").'~ ). script_text( 28, 'There\'s a slight complication when we want to negate a conjunction of'~<> 'goals. How would we negate'~<> ''~<> ' is_a(joe,man), lives_in(joe,paris)?'~<> ''~<> 'The obvious way is to enclose the whole lot inside a "not(...)":'~<> ''~<> ' not(is_a(joe,man), lives_in(joe,paris) )?'~<> ''~<> 'Try it and see what happens.'~ ). script_text( 29, 'You should have found that it failed. This is odd: it should have'~<> 'succeeded (why?).'~ ). script_text( 30, 'The problem is due to the comma: it\'s a question of two halves, Brian.'~<> ''~<> ' not(is_a(joe,man), lives_in(joe,paris) )?'~<> ' ^'~<> ' !'~<> ''~<> 'When Prolog sees such a comma inside argument brackets, it treats that'~<> 'comma as separating the arguments; here, Prolog thinks that "not" was'~<> 'given TWO arguments and not ONE. There is no two-argument form of "not",'~<> 'so the call fails.'~ ). script_text( 31, 'To circumvent this, put extra brackets around the entire question:'~<> ''~<> ' not(( is_a(joe,man), lives_in(joe,paris) ))?'~<> ''~<> 'They shield the comma, so that Prolog no longer sees it as an argument'~<> 'separator, but as an "and". Moral: if you need to negate a conjunction'~<> 'of goals, always put extra brackets round it.'~ ). script_text( 32, 'Now, suppose we had the facts (valid perhaps if we know two men named'~<> 'Joe):'~<> ''~<> ' lives_in( joe, london ).'~<> ' lives_in( joe, bristol ).'~<> ''~<> 'What is the result of'~<> ''~<> ' not( lives_in(joe,london) )?'~ ). script_text( 33, 'Answer: it FAILS, although there is one Joe not in London. This is'~<> 'because the question'~<> ''~<> ' lives_in( joe, london )?'~<> ''~<> 'succeeds. "not" negates that success, turning it into failure.'~<> ''~<> 'So not(P) always means : is it true that P never holds?'~<> ' and not : is it true that P is sometimes false?'~ ). script_text( 34, 'Now try'~<> ''~<> ' not( lives_in(jill,X) )? '~ ). script_text( 35, 'Notice that it fails; and it does not set X. This is for the same reason'~<> 'that "X \\= marathon" failed in lesson 5. Presumably, the intent of such'~<> 'a question is to discover an X where Jill does not live.'~<> ''~<> 'The way to program this is to equip the database with a list of all'~<> 'place names within the universe of discourse:'~<> ' place( london ). place( bristol ). ...'~<> ''~<> 'You can then ask a question like'~<> ''~<> ' place( X ), not( lives_in(jill,X) )?'~<> ''~<> 'In general, the same applies to variables in the argument to "not" as'~<> 'applies to the arguments of \\=. Make sure that by the time a "not" is'~<> 'executed, all the variables in its argument have a value. If they don\'t,'~<> 'the results will be confusing.'~ ). script_text( 36, 'To summarise about "not" '~<> ''~<> ' Its argument is a goal. If this fails, "not" succeeds; if it succeeds,'~<> ' "not" fails. Always remember this rule to predict what "not" will do.'~<> ''~<> ' If the argument is a conjunction of goals, put an extra pair of'~<> ' brackets around it:'~<> ' not(( is_a(joe,man), lives_in(joe,paris) ))?'~<> ''~<> ' Ensure that any variables in the argument have values by the time'~<> ' "not" is excuted.'~ ).