Before we can look at more advanced programming examples, it is necessary to have some idea of how the programs are executed. This is similar in flavor to the way PROLOG programs are executed, but the basic operational step of unifying an atom with the head of a rule is replaced by something more general. In this preliminary section, we assume that all arithmetic constraints are linear; the general case is discussed in a later section.
The computation begins with a goal and an initially empty set of collected constraints. The usual left-right atom selection rule is used to select either an arithmetic constraint or an atom at each stage. When a constraint is selected, it is added to the set of collected constraints, and it is determined whether the resulting set has a solution. If there is no solution, backtracking takes place in the usual way. On the other hand, when an atom is selected, the set of rules is searched in the usual top-down fashion, each time matching that atom with the head of some rule. Such a match is realized by an equation between these two atoms; such an equation is treated like any equation between terms.
As before, it is required that the system of constraints collected so far has a solution. In general, solving this equation proceeds at first by unifying the syntactic parts of the terms in the usual way. However, these terms may contain arithmetic terms. As arithmetic terms have a special meaning, they are not unified syntactically, but rather an equation between them is solved in the domain of real arithmetic.
Let us consider some examples. We start with a program that has no explicit constraints or arithmetic terms, effectively written in PROLOG.
p(f(c)).
q(g(X)) :-
p(f(X)).
?- q(Y).
As the computation proceeds, the collected constraint set and current goal are as follows:
{} ?- q(Y).
{q(Y) = q(g(X)) } ?- p(f(X)).
{q(Y) = q(g(X)), p(f(X)) = p(f(c)) } ?- .
Note that only one successful path is shown here. Also, as we will discuss in more detail later, the ``answer'' to this query is just the set of constraints collected, but ``projected'' onto the goal variables, in this case Y. So the answer to the above query is
Y = g(c).
Now consider a program that includes both arithmetic terms and explicit constraints:
p(10, 10).
q(W, c(U, V)) :-
W - U + V = 10,
p(U, V).
?- q(Z, c(X + Y, X - Y)).
and again we only look at one successful path of the execution:
{} ?- q(Z, c(X + Y, X - Y)).
{q(Z, c(X + Y, X - Y)) = q(W, c(U, V)) } ?- W - U + V = 10, p(U, V).
{q(Z, c(X + Y, X - Y)) = q(W, c(U, V)), W - U + V = 10 } ?- p(U, V).
{
, p(U,V) = p(10, 10) } ?- .
The answer for this derivation is
Y = 0, X = 10, Z = 10.
and we should notice that, as expected, it does not contain any mention of the variables U, V, and W. Also note that, in general, the answers need not give values to variables, and it is possible to get an answer constraint like
X + Y + Z = 0, X > Y.
This facility is a very important and useful feature of CLP( 
) as we will
illustrate later.