Information Technology Reference
In-Depth Information
above(X,Y) :- above(Z,Y), on(X,Z).
This clause says exactly the same thing as the one in the program; it simply changes
the order of the conjunction. So from the point of view of truth, it works just as well
as the earlier one. It is logically correct. But it does not work well for back-chaining.
Consider the query
above(b1,b1)
:
1.
The first clause fails because nothing is on block B1.
2.
The second clause says to first find a block
Z1
such that
above(Z1,b1)
holds
(here renaming the
Z
variable to
Z1
).
3. The first clause for
above(Z1,b1)
fails because nothing is on block B1.
4. The second clause for
above(Z1,b1)
says to first find a block
Z2
such that
above(Z2,b1)
holds (again renaming the
Z
variable).
5. The program goes back to step 3, where the first clause fails, and so on.
In terms of conjunctive queries to be established, here is how back-chaining would
work with this query:
above(b1,b1).
above(Z1,b1), on(b1,Z1).
above(Z2,b1), on(Z1,Z2), on(b1,Z1).
above(Z3,b1), on(Z2,Z3), on(Z1,Z2), on(b1,Z1).
...
It is clear that the conjunctive queries will get longer and longer, and so Prolog will
eventually produce an error when it runs out of memory.
When writing recursive programs, there is no simple way to
guarantee
that they
will terminate. However, a good rule of thumb is that when a clause is recursive, the
recursive predicate should appear toward the end of the clause, so that new variables
can be instantiated. Instead of
above(X,Y) :- above(Z,Y), on(X,Z).
write
above(X,Y) :- on(X,Z), above(Z,Y).
The two sentences mean the same thing. They are both logically correct. But because
of the way back-chaining works, the second one will try the recursive predicate only
after
it has found a value for the variable
Z
using the
on
predicate.
When the body of a clause contains a recursive predicate, make sure that its new
variables are instantiated by earlier atoms in the body.
