Information Technology Reference
In-Depth Information
Figure 3.12.
The Prolog back-chaining procedure
To establish a query consisting of atoms
A
1
,
A
2
, ...,
A
n
:
1.
If
n
=
0, there's nothing to do, and so exit with success.
2.
Otherwise, begin by renaming all the variables in the conjunctive query.
3.
Go through each clause of the
program
from top to bottom:
a.
Assume the current clause has head
H
and body
B
1
, ...,
B
m
, (where for
atomic clauses,
m
=
0).
b.
Test to see if the head
H unifies
with
A
1
, the first atom of the query.
c.
If it does not unify, try the next clause in the program.
If it does unify, try to establish
B
1
, ...,
B
m
,
A
2
,...,
A
n
, by back-chaining,
where the
∗
means the result of replacing the variables by their values after
unification.
d.
e.
If the resulting conjunctive query was successful, exit the procedure with
success; if it was not successful, then try the next clause in the program (just
as if the
H
had not unified at step 3c).
4.
If all of the clauses of the program have been tried without success, then exit
with failure.
after the unification of
H
and
A
1
, or perhaps the rest of the query,
A
2
, ...,
A
n
,
will not
succeed for the values of variables after that unification, and backtracking is indicated.
So even though the
H
unifies with
A
1
, this may not be the desired clause, and the
procedure will look for alternatives for
A
1
in step e.
To deal with such issues, back-chaining is invoked on a new conjunctive query,
B
1
, ...,
B
m
,
A
2
, ...,
A
n
, where two changes have been made to the original:
A
1
has been replaced in the query by the
body
of the clause whose head matches
A
1
. Note that if that matching clause had no body (that is, if the clause was
atomic), then there are no
B
i
atoms, the new query starts at
A
2
, and the first part
of the query is finished, at least tentatively.
After unifying
A
1
with
H
, the procedure considers the values of the resulting
variables. Some variables might appear in both the head and the body of the
matching clause and the procedure needs to have the right values for those vari-
ables. Also, there can be variables in
A
1
that appear in the rest of the conjunctive
