Information Technology Reference
In-Depth Information
the current goal G'. We call Am a cut point and call the current goal G' as the
father-goal of “!”. Now it is the turn to solve sub-goals B1,…, Bi, ! , Bi+1, …,
Bq one by one. As a typical sub-goal, “!” is valid and can be jumped over.
Suppose a backtracking is triggered by the fact that some sub-goals behind “!”
can not be unified, then the goal stack will be tracked back to Am-1, the sub-goal
prior to the cut point Am. From the point of SLD tree, all the nodes which are
rooted by the father-goal of “!” and are accessed still will be cut out.
For example, let P be the following program:
(1) p(a).
(2) p(b).
(3) q(b).
(4) r(X):- p(X), q(X).
(5) r(c ).
Let G be the sub-goal “?-r(X)”. Then the SLD tree generated during the process
of SLD resolutionis is presented as figure 2.1. However, if a cut is inserted into
the clause (4) of program P, .i.e., the clause (4) of program P is changed as
follows:
(4)
r(X):- p(X), !, q(X).
Then the corresponding SLD tree should become that presented in figure 2.2. In
the later case, no solution will be generated since a critical part is cut out from
this SLD tree.
