~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.
~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.
~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?
~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?
~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?
~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".
~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.
~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.
~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.
~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.
~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 / .
~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.
~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?
~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.
~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.
~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 )?
~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.
~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.
~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.
~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 )?
~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.
~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 ) ?
~23
The answer is in knowledge base "arith1".
~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)?
~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.
~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?").
~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").
~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.
~29
You should have found that it failed. This is odd: it should have
succeeded (why?).
~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.
~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.
~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) )?
~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?
~34
Now try
not( lives_in(jill,X) )?
~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.
~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.