Information Technology Reference
In-Depth Information
Figure 4.2.
A blocks-world program
blocks.pl
% on(X,Y) means that block X is directly on top of block Y.
1
on(b1,b2).
on(b3,b4).
on(b4,b5).
on(b5,b6).
2
% just left(X,Y) means that blocks X and Y are on the table
4
% and that X is immediately to the left of Y.
5
just_left(b2,b6).
just_left(b6,b7).
6
% above(X,Y) means that block X is somewhere above block Y
8
% in the pile where Y occurs.
9
above(X,Y) :- on(X,Y).
10
above(X,Y) :- on(X,Z), above(Z,Y).
11
% left(X,Y) means that block X is somewhere to the left
13
% of block Y but perhaps higher or lower than Y.
14
left(X,Y) :- just_left(X,Y).
15
left(X,Y) :- just_left(X,Z), left(Z,Y).
16
left(X,Y) :- on(X,Z), left(Z,Y).
% leftmost is on something.
17
left(X,Y) :- on(Y,Z), left(X,Z).
% rightmost is on something.
18
% right(X,Y) is the opposite of left(X,Y).
20
right(Y,X) :- left(X,Y).
21
But what about the
above
predicate? How do we know that the whole truth and
nothing but the truth is included for this one? Consider the sentences represented by
the clauses in lines 10 and 11:
-
If
x
is directly on
y
, then
x
is above
y
.
-
If
x
is directly on
z
, and
z
is above
y
, then
x
is above
y
.
Both these sentences are clearly true. But is this all the necessary information?
Let us first check that the clauses work on some examples by looking at a trace
of some queries in figure 4.3.
(From now on,
user-typed queries are no longer
highlighted in bold.)
For the first query, Prolog determines that block B1 is above block B2 because B1
is directly on B2.
For the second query, Prolog determines that block B3 is above block B5 because
B3 is directly on B4, and B4 is above B5. (It determines that B4 is above B5 because
B4 is directly on B5.)
So in trying to establish the query
above(b3,b5)
, Prolog had to first establish
above(b4,b5)
. This means that
above
is a recursive predicate.
