“X is a boy if X is a male and X is a child.”
Artificial Intelligence © Rules in Prolog 1
General rules in Prolog
Simple Prolog databases are not very interesting. No intelligence! We want programs that reason.
Copyright By PowCoder代写 加微信 powcoder
Recall the introductory material on back-chaining and conditional sentences:
• If X is male and X is a child then X is a boy.
• If X is a toddler then X is a child.
Prolog programs may (and usually will) contain such conditional sentences, which in Prolog are called general rules or clauses.
child(X) :- toddler(X).
Like atoms, rules in a program end with a period.
“X is a child if X is a toddler.”
likes(bob,X) :- child(X).
“Bob likes children.”
likes(X,Y) :- baby(Y).
Comma in a rule means “and”.
“Everyone likes babies.”
boy(X) :- male(X), child(X).
:- means “if”
For a clause
More about clauses
a :- b1, … ,bn.
• a is called the head of the clause. It must be an atom.
• b1,…,bn is called the body of the clause. Each b can be either an atom or the negation of an atom.
• read as: a if b1 and … and bn.
For uniformity of terminology, an atomic sentence in Prolog is also called a clause, sometimes a unit clause. So baby(marc) and likes(bob,ray) are also clauses.
A unit clause a is said to have a as its head and an empty body. Indeed, in Prolog , you can write it as
To summarize:
A Prolog program is a sequence of clauses, each ending with a period. A clause is a head and a body separated by :-. A head is an atom, and a body is a sequence of atoms or their negations separated by commas.
cps721 Artificial Intelligence © Rules in Prolog 2
A program with clauses
baby(marc). baby(mary).
toddler(michelle). toddler(steve).
toddler(bob).
likes(marc,michelle). likes(bob,ray).
likes(bob,michelle).
male(ray). male(marc). male(bob).
male(steve).
female(mary). female(michelle).
child(X) :- toddler(X).
boy(X) :- male(X), child(X).
girl(X) :- female(X), child(X).
person(X) :- male(X).
person(X) :- female(X).
adult(X) :- person(X),
not child(X), not baby(X).
likes(X,Y) :- baby(Y), adult(X).
likes(X,bob). /* Everyone likes bob. */
/* Comments like this may be inserted anywhere in
your program except in the middle of a clause. They
are useful to remind you (and others) what you
intend by certain parts of your program. Use them!*/
cps721 Artificial Intelligence © Rules in Prolog 3
Querying a general program
Queries are the same as before. But now Prolog makes use of the program’s clauses to answer them.
Prolog uses back-chaining, exactly as described in the introductory material in this course.
Who likes Mary?
likes(X,mary).
• Prolog searches in the program for the first clause which matches the query, which in this case is likes(X,Y) :- baby(Y), adult(X).
• So it sets up the subgoal: baby(mary), adult(X).
This is a conjunctive query, and Prolog tries to answer this.
• It finds the unit clause baby(mary) in the program, so its new subgoal is adult(X).
• It searches for the first clause in the program whose head matches this, and finds:
adult(X) :- person(X), not child(X),
not baby(X).
cps721 Artificial Intelligence © Rules in Prolog 4
• So it establishes a new subgoal:
person(X),
not child(X), not baby(X).
• Again, it searches for the first clause whose head matches person(X), which is:
person(X) :- male(X).
• So it establishes the new subgoal:
male(X), not child(X), not baby(X).
• The first clause in the program which matches male(X) is male(ray), so the next subgoal is:
not child(ray), not baby(ray). • Prolog works on not child(ray).
– It attempts child(ray). This leads to trying to solve toddler(ray) which fails.
– Therefore, not child(ray) succeeds. • Prolog now works on not baby(ray) which
eventually succeeds.
So Prolog succeeds on the top level goal
likes(X,mary) with X = ray.
cps721 Artificial Intelligence © Rules in Prolog 5
Artificial Intelligence
Rules in Prolog 6
Evaluating likes(X,mary). likes(X,mary).
Note the use of a rule here
child(ray).
toddler(ray).
baby(mary), adult(X).
person(X), not child(X), not baby(X).
male(X), not child(X), not baby(X). X = ray
not child(ray), not baby(ray).
not baby(ray).
success X = ray
baby(ray).
adult(mary).
adult(mary).
person(mary), not child(mary), not baby(mary).
person(mary), not child(mary), not baby(mary).
male(mary),
not child(mary), not baby(mary).
female(mary), not child(mary), not baby(mary).
male(mary),
not child(mary), not baby(mary).
female(mary), not child(mary), not baby(mary).
Backtracking
baby(Y), adult(mary).
success X = mary Y = bob
child(mary).
child(mary).
not baby(mary). toddler(mary). X
toddler(mary).
cps721 Artificial Intelligence
Rules in Prolog 7
not child(mary), not baby(mary).
not child(mary), not baby(mary).
female(X), likes(X,Y). X = mary
likes(mary,Y).
not baby(mary).
Artificial Intelligence © Rules in Prolog 8
Writing meaningful Prolog
When writing Prolog programs, it is important to consider carefully what we intend the predicates to mean, and to make sure that the clauses we write are all true.
The next issue to consider is whether or not we have included enough clauses to allow Prolog to draw appropriate conclusions involving the predicates.
Finally, we need to consider how back- chaining will use the clauses when actually deriving conlusions.
To summarize, we need
1. the truth, and nothing but;
2. the whole truth;
3. presented in the right form for back-chaining.
Artificial Intelligence © Rules in Prolog 9
A blocks world
Would like to describe the scene and get Prolog to deduce that
Block 3 is above Block 6
Block 1 is to the left of Block 7 Block 4 is to the right of Block 2
A blocks world program
/* on(X,Y) means that block X is directly on top
of (touching) block Y. */
on(b1,b2). on(b3,b4). on(b4,b5). on(b5,b6).
/* just_left(X,Y) means that block X is on the
table and is immediately to the left of block Y,
which is also on the table. */
just_left(b2,b6). just_left(b6,b7).
/* above(X,Y) means that block X is somewhere above
Y in the pile of blocks in which Y occurs. */
above(X,Y) :- on(X,Y).
above(X,Z) :- on(X,Y), above(Y,Z).
/* left(X,Y) means that block X is to be found
somewhere to the left of block Y.
Thus, left(b2,b7), left(b1,b7) and left(b1,b4)
are all true. left(b5,b1) is false. */
left(X,Z) :- above(X,Y), left(Y,Z). /* X is high */ left(X,Y) :- above(Y,Z), left(X,Z). /* X is low */ left(X,Y) :- just_left(X,Y).
left(X,Y) :- just_left(X,Z), left(Z,Y).
right(X,Y) :- left(Y,X).
cps721 Artificial Intelligence © Rules in Prolog 10
Artificial Intelligence
Rules in Prolog 11
Evaluating above(b3,b6). above(b3,b6).
on(b3,b6).
on(b3,Y), above(Y,b6). Y = b4
on(b4,b6).
on(b4,Y), above(Y,b6). Y = b5
above(b4,b6).
above(b5,b6).
on(b5,b6).
The example we just saw makes use of recursion.
Recursive clause = one in which the predicate of the head is the same as a predicate mentioned in the body.
above(X,Z) :- on(X,Y), above(Y,Z).
If x is on y and y is above z, then x is above z
Most modern programming languages (Pascal, C) provide recursion, which is usually taught as an advanced technique.
In fact, it’s really quite a simple idea and lies at the heart of Prolog programming.
cps721 Artificial Intelligence © Rules in Prolog 12
on(b2,Y), left(Y,b5).
on(b2,Y1), above(Y1,Y), left(Y,b5).
on(b5,Z), left(b2,Z). Z = b6
Artificial Intelligence
Rules in Prolog 13
Evaluating left(b1,b5). left(b1,b5)
above(b2,Y), left(Y,b5).
above(b5,Z), left(b2,Z).
above(b1,Y), left(Y,b5)
on(b1,Y), left(Y,b5). Y = b2
left(b2,b5).
left(b2,b6).
just_left(b2,b6).
Renaming variables
Sometimes, as in the previous example, it is necessary to rename variables in a program clause before using them to generate a new subgoal .
In the previous example, we had a subgoal: above(b2,Y), left(Y,b5).
We were generating a new subgoal from this one by using the program clause
above(X,Z) :- on(X,Y), above(Y,Z).
Notice that the subgoal and the program clause have a variable, Y, in common.
Suppose we just blindly generate a new subgoal:
on(b2,Y), above(Y,Y), left(Y,b5)
which is not right.
But if we rename the variables of the program clause so that they are different from the variables of the subgoal (after all, they can have any names we want): above(X1,Z1) :- on(X1,Y1), above(Y1,Z1).
Then the new subgoal is:
on(b2,Y1), above(Y1,Y), left(Y,b5)
which works fine.
cps721 Artificial Intelligence © Rules in Prolog 14
When you (as opposed to Prolog) are using a program clause and a subgoal to establish a new subgoal, make sure the clause’s variables are different from the subgoal’s variables.
In fact, Prolog does this automatically by storing clauses using internal variables which it guarantees to be different from any other variable in any other program clause or query.
Example: Recall the program clause
likes(X,bob). /* Everyone likes Bob */
Suppose this is the entire program and consider the query “Who likes Bob?”:
likes(Y,bob). Y = _967. yes
_967 here is an internal variable which Prolog used to replace the variable X in the original program clause. The answer Y = _967 means that anything at all is an example of a Y that likes Bob.
cps721 Artificial Intelligence © Rules in Prolog 15
on(b2,Y), left(Y,b7).
on(b2,Y1), above(Y1,Y), left(Y,b7).
left(b6,b7).
Evaluating right(b7,b2). right(b7,b2).
above(b2,Y), left(Y,b7).
just_left(b2,Z), left(Z,b7).
cps721 Artificial Intelligence ©
Rules in Prolog 16
above(b7,Z), left(b2,Z).
on(b7,Z), on(b7,Y), left(b2,Z). above(Y,Z),
left(b2,Z).
left(b2,b7).
just_left(b2,b7).
just_left(b6,b7).
Nonterminating Programs
When using recursion, it is possible to write programs which go on forever. For example:
left(X,Z) :- left(X,Y), just_left(Y,Z).
What this says is correct: If x is to the left of y and y is just to the left of z, then x is to the left of z.
left(b1,b2)
left(b1,Y), just_left(Y,b2)
left(b1,Y1), just_left(Y1,Y), just_left(Y,b2)
left(b1,Y2), just_left(Y2,Y1), just_left(Y1,Y), just_left(Y,b2)
Eventually, Prolog reports: “Sorry, there isn’t enough memory to complete evaluation of the query.”
cps721 Artificial Intelligence © Rules in Prolog 17
Avoiding non-termination
When writing recursive programs, there is no simple way to guarantee that they will terminate.
However, a good rule of thumb is that when a clause is recursive, the body should contain at least one atom before the recursive one to provide a new value for one of the variables.
For example, instead of
left(X,Z) :- left(X,Y), just_left(Y,Z).
we should write
left(X,Z) :- just_left(Y,Z), left(X,Y).
These two clauses mean the same thing in English, but because of the left-to-right order of Prolog, the second one will reach the recursive predicate only after we have found a specific value for Y.
cps721 Artificial Intelligence © Rules in Prolog 18
find a value for Y
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com