Information Technology Reference
In-Depth Information
To capture the whole truth about a recursive predicate, one must make sure that
for all
n
, queries of size
n
will succeed, just as for the
above
predicate. Again, there is
a two-step procedure:
1.
Write clauses to handle the
n
0 case. For the
left
predicate, this means writing
clauses for the case where
x
is directly to the left of
y
on the table:
=
left(X,Y) :- just_left(X,Y).
(
+
)
2.
Write clauses to handle the
case. For the
left
predicate, assume that
queries of size
n
already work properly. Now suppose there is a query
left
(
n
1
)
x
,
y
(
+
)
of size
. There are only three ways this can happen:
a.
x
and
y
are both on the table, and
x
is just to the left of a block
z
. This means
that
left
(
n
1
is of size
n
,so
left(X,Y) :- just_left(X,Z), left(Z,Y).
b.
x
is on a block
z
, where
z
is also to the left of
y
. This means that
left
z
,
y
)
(
)
z
,
y
is
of size
n
,so
left(X,Y) :- on(X,Z), left(Z,Y).
c.
y
is on a block
z
, where
x
is also to the left of
z
. This means that
left
(
)
x
,
z
is
of size
n
,so
left(X,Y) :- on(Y,Z), left(X,Z).
This shows precisely where the four clauses in the program come from. As before,
the justification for this two-step procedure is mathematical induction.
One nice thing about using this notion of size is that one can now be more explicit
about how to handle the issue of program termination. The idea is simple:
Termination.
A recursive program will terminate if the query that matches the
head of a clause is always bigger (according to the size measure being used) than the
queries from the body of the clause.
This is sufficient because as the clause is used over and over, the size keeps going
down. Eventually the size will be 0, with no further recursion.
To see this, note that for the recursive clause for the
above
predicate, the program
went from a query
above
(
x
,
y
)
of size
(
n
+
)
matching the head, to a query of size
n
,
1
above
(
in the body. So the size decreases. The
left
predicate is similar.
But consider the nonterminating problematic clause for the
poodle
predicate. In
this case, the query from the body is identical to the query matching the head, and so
the size (whatever it is)
cannot
be decreasing. Similarly, for the faulty recursive version
z
,
y
)
