Information Technology Reference
In-Depth Information
Figure 4.5.
The start of a trace of a
left
query
?- left(b3,b3).
Call: (7) left(b3, b3)
% The main goal
Call: (8) just_left(b3, b3)
Fail: (8) just_left(b3, b3)
Redo: (7) left(b3, b3)
% Reconsider.
Call: (8) just_left(b3, _L205)
Fail: (8) just_left(b3, _L205)
Redo: (7) left(b3, b3)
% Reconsider.
Call: (8) on(b3, _L205)
% Try on(b3,Z).
Exit: (8) on(b3, b4)
Call: (8) left(b4, b3)
% Then start left(b4,b3).
Call: (9) just_left(b4, b3)
Fail: (9) just_left(b4, b3)
Redo: (8) left(b4, b3)
% Reconsider. ...
of
opp_sex
, the query from the body is the same as the query matching the head but
with the arguments reversed, and so again the size does not decrease.
Finally, consider the incorrect version of the
above
predicate (where the order of the
two conjuncts is changed). It has
above
(
)
in the head and
above
(
)
in the body,
just like the correct version. The difference is that the correct version makes sure that
the
z
is lower than
x
using the
on
predicate. This guarantees that
above
(
x
,
y
z
,
y
)
z
,
y
will be
smaller than
above
(
)
. There is no such guarantee in the incorrect version, so the
program may not terminate.
x
,
y
4.7 Efficiency in Prolog
So far, the blocks-world program is grammatically correct, logically correct, and in
the right form for back-chaining. It does exactly what is intended. Yet, while it gives
correct results, it does not do so
efficiently
.
Consider, for example, a trace of the query
left(b3,b3)
. The start is shown in
figure 4.5. As the trace continues, the query will eventually fail, as it should. But the
eventually
is very far away: a full trace would go on for more than 1500 lines. The
reason for this has to do with the way the
left
predicate is defined in the program.
A query
left
(
)
x
,
y
is handled in three stages:
1.
See if
x
and
y
are both on the table (using
just_left
).
2.
See if
x
is on another block
z
, and try
left
with that.
