Information Technology Reference
In-Depth Information
Figure 4.3.
Tracing the
above
predicate
?- above(b1,b2).
Call: (7) above(b1, b2)
% The main goal
Call: (8) on(b1, b2)
% Try on(b1,b2) using line 10.
Exit: (8) on(b1, b2)
% Succeeds because of line 2.
Exit: (7) above(b1, b2)
% The main goal succeeds.
Yes
?- above(b3,b5).
Call: (8) above(b3, b5)
% The main goal.
Call: (9) on(b3, b5)
% - Try on(b3,b5).
Fail: (9) on(b3, b5)
% This fails.
Redo: (8) above(b3, b5)
% Reconsider.
Call: (9) on(b3, _L205)
% - Try on(b3,Z) from line 11.
Exit: (9) on(b3, b4)
% This succeeds for Z=b4.
Call: (9) above(b4, b5)
% - Now try above(Z,b5) for Z=b4.
Call: (10) on(b4, b5)
% - Try on(b4,b5).
Exit: (10) on(b4, b5)
% This succeeds.
Exit: (9) above(b4, b5)
% This succeeds;
Exit: (8) above(b3, b5)
% The main goal succeeds.
Yes
4.3 Recursion in Prolog
Most modern programming languages provide recursion, but it is usually considered
to be an advanced technique. In fact, it is really quite simple and lies at the heart of
Prolog programming.
In the simplest case, a predicate is considered
recursive
when the predicate appears
in both the head and the body of a clause, as in line 11. When these are written
as English sentences, the predicate is used in both the
if
and the
then
parts of the
sentence.
Recursion is needed when there is a predicate that involves using another predicate
some number
of times. In the example with the
above
predicate, a block
x
is above a
block
y
when there are
some number n
of intermediate blocks such that
x
is on
b
1
,
b
1
is
on
b
2
,
b
2
is on
b
3
, ...,
b
n
−
2
is on
b
n
−
1
,
b
n
−
1
is on
b
n
, and finally
b
n
is on
y
. The
n
here
can be any number. When
n
0, there are no intermediate blocks:
x
is directly on
y
.
Once this pattern of needing to use another predicate some number
n
of times
becomes clear (where the number
n
is not known in advance), clauses for the predicate
are written in a two-step operation:
=
