/* 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.'~
).