Information Technology Reference
In-Depth Information
{p(X,X), p(Y, f(Y))}. Such a mistake will be covered if the variable Y is not used
in the SLD resolution anymore. However, once the variable Y is used again, the
resolution process will fall into an endless loop.
2.2.4
Non-logic components: CUT
Program is the embodiment of algorithm. Algorithm in the logic programming is
characterized with the following formula:
algorithm = logic + control
Where the logic component determines the function of the algorithm; the control
component determines the strategy which will be used to realize the function.
Theoretically, a programmer just needs to specify the logic component, and then
the corresponding control component can be automatically determined by the
logic programming system. Howerev, most Prolog systems in practice can not
reach such automation. As set forth, in order to guarantee a valid executation of
the program, a programmer have to take the order of clauses into consideration.
Another problem is the fact that an endless branch might be generated during the
SLD resolution, according to the depth-first search strategy adopted by Prolog. In
such a situation, the goal stack used in the resolution algorithm will be
overflowed and bring the resolution process into an error state. The “CUT”
component is introduced to solve this problem.
From the point of declarative semantics, CUT is a non-logical control
component. Represented as the character “!”, CUT can be treated as an atomic
component and be inserted into clauses of the program or the order. Declarative
semantics of a program is not affected by any “!” which appeared in the program
or in the order.
From the point of operational semantics, some control information is carried
by the CUT component. For example, let G be the following goal:
?- A
1
,…,A
m-1
, A
m
, A
m+1
,…,A
k
Let the following, which is denoted by C, be one of the clauses of the program:
A:- B
1
,…, B
i
, ! , B
i+1
, …, B
q
Consider the state that sub-goals A1,…,Am-1 have been solved, and let G' be the
current goal. Suppose Am can be unified with A. After the unification operation,
the body of the clause C is added into the goal G'. Now a cut “!” is contained in
