Information Technology Reference
In-Depth Information
Figure 4.4.
Tracing the
left
predicate
?- left(b1,b7).
Call: (7) left(b1, b7)
% This is the main goal.
Call: (8) just_left(b1, b7)
% - Try just_left(b1,b7).
Fail: (8) just_left(b1, b7)
% This fails.
Redo: (7) left(b1, b7)
% Reconsider.
Call: (8) just_left(b1, _L205)
% - Try just_left(b1,Z).
Fail: (8) just_left(b1, _L205)
% This also fails.
Redo: (7) left(b1, b7)
% Reconsider.
Call: (8) on(b1, _L205)
% - Try on(b1,Z) (line 17).
Exit: (8) on(b1, b2)
% This succeeds for Z=b2.
Call: (8) left(b2, b7)
% - Try left(Z,b7) for Z=b2.
Call: (9) just_left(b2, b7)
%
- Try just_left(b2,b7).
Fail: (9) just_left(b2, b7)
%
This fails.
Redo: (8) left(b2, b7)
% Reconsider.
Call: (9) just_left(b2, _L223)
%
- Try just_left(b2,Z1).
Exit: (9) just_left(b2, b6)
%
Ok for Z1=b6.
Call: (9) left(b6, b7)
%
- Try left(b6,b7).
Call: (10) just_left(b6, b7)
%
- just_left(b6,b7).
Exit: (10) just_left(b6, b7)
%
This succeeds.
Exit: (9) left(b6, b7)
%
This succeeds.
Exit: (8) left(b2, b7)
% This succeeds.
Exit: (7) left(b1, b7)
% The main goal succeeds.
Yes
to work for any
n
. The key idea was that there was a measure of some sort of the
size
of the queries; a program had to work for queries of any size. In the case of the
above
predicate, the size was the number of intermediate blocks between a top block and a
bottom block.
Different recursive predicates require different measures of size. Any measure can
be considered but it takes practice to find one that works. In the case of the
left
predicate, the size of a query
left
(
)
is the following:
The number of blocks between
x
and the table +
the number of blocks between
y
and the table +
the number of blocks on the table between the base of
x
and the base of
y
(where the base means the block on the table below it).
x
,
y
So, for example, the size of
left(b6,b7)
will be 0, the size of
left(b1,b7)
will be 3,
and the size of
left(b1,b4)
will be 4.
