The following example defines the constraint X+Y=T as an FD predicate in terms of three indexicals. Each indexical is a rule responsible for removing values detected as incompatible from one particular constraint argument. Indexicals are not Prolog goals; thus, the example does not express a conjunction. However, an indexical may make the store contradictory, in which case backtracking is triggered:
plus(X,Y,T) +:
X in min(T) - max(Y) .. max(T) - min(Y),
Y in min(T) - max(X) .. max(T) - min(X),
T in min(X) + min(Y) .. max(X) + max(Y).
The above definition contains a single clause used for constraint solving. The first indexical wakes up whenever the bounds of S(T) or S(Y) are updated, and removes from D(X,S) any values that are not compatible with the new bounds of T and Y. Note that in the event of “holes” in the domains of T or Y, D(X,S) may contain some values that are incompatible with X+Y=T but go undetected. Like most built-in arithmetic constraints, the above definition maintains bound-consistency, which is significantly cheaper to maintain than arc-consistency and suffices in most cases. The constraint could for example be used as follows:
| ?- X in 1..5, Y in 2..8, plus(X,Y,T).
X in 1..5,
Y in 2..8,
T in 3..13
Thus, when an FD predicate is called, the ‘+:’ clause is activated.
The definition of a user constraint has to specify what domain constraints should be added to the constraint store when the constraint is posted. Therefore the FD predicate contains a set of indexicals, each representing a domain constraint to be added to the constraint store. The actual domain constraint depends on the constraint store itself. For example, the third indexical in the above FD predicate prescribes the domain constraint ‘T :: 3..13’ if the store contains ‘X :: 1..5, Y :: 2..8’. As the domain of some variables gets smaller, the indexical may enforce a new, stricter constraint on some other variables. Therefore such an indexical (called a propagating indexical) can be viewed as an agent reacting to the changes in the store by enforcing further changes in the store.
In general there are three stages in the lifetime of a propagating indexical. When it is posted it may not be evaluated immediately (e.g. has to wait until some variables are ground before being able to modify the store). Until the preconditions for the evaluation are satisfied, the agent does not enforce any constraints. When the indexical becomes evaluable the resulting domain constraint is added to the store. The agent then waits and reacts to changes in the domains of variables occurring in the indexical by re-evaluating it and adding the new, stricter constraint to the store. Eventually the computation reaches a phase when no further refinement of the store can result in a more precise constraint (the indexical is entailed by the store), and then the agent can cease to exist.
A necessary condition for the FD predicate to be correctly defined is the following: for any store mapping each variable to a singleton domain the execution of the indexicals should succeed without contradiction exactly when the predicate is intended to be true.
There can be several alternative definitions for the same user
constraint with different strengths in propagation. For example, the
definition of plusd below encodes the same X+Y=T
constraint as the plus predicate above, but maintaining
arc-consistency:
plusd(X,Y,T) +:
X in dom(T) - dom(Y),
Y in dom(T) - dom(X),
T in dom(X) + dom(Y).
| ?- X in {1}\/{3}, Y in {10}\/{20}, plusd(X, Y, T).
X in{1}\/{3},
Y in{10}\/{20},
T in{11}\/{13}\/{21}\/{23}
This costs more in terms of execution time, but gives more precise
results. For singleton domains plus and plusd behave in
the same way.
In our design, general indexicals can only appear in the context of FD predicate definitions. The rationale for this restriction is the need for general indexicals to be able to suspend and resume, and this ability is only provided by the FD predicate mechanism.
If the program merely posts a constraint, it suffices for the definition to contain a single clause for solving the constraint. If a constraint is reified or occurs in a propositional formula, the definition must contain four clauses for solving and checking entailment of the constraint and its negation. The role of each clause is reflected in the “neck” operator. The following table summarizes the different forms of indexical clauses corresponding to a constraint C. In all cases, Head should be a compound term with all arguments being distinct variables:
+: Indexicals. -: Indexicals. +? Indexical. -? Indexical.When a constraint is reified, the solver spawns two reactive agents corresponding to detecting entailment and disentailment. Eventually, one of them will succeed in this and consequently will bind B to 0 or 1. A third agent is spawned, waiting for B to become assigned, at which time the constraint (or its negation) is posted. In the mean time, the constraint may have been detected as (dis)entailed, in which case the third agent is dismissed. The waiting is implemented by means of the coroutining facilities of SICStus Prolog.
As an example of a constraint with all methods defined, consider the following library constraint defining a disequation between two domain variables:
'x\\=y'(X,Y) +:
X in \{Y},
Y in \{X}.
'x\\=y'(X,Y) -:
X in dom(Y),
Y in dom(X).
'x\\=y'(X,Y) +?
X in \dom(Y).
'x\\=y'(X,Y) -?
X in {Y}.
The following sections provide more precise coding rules and operational
details for indexicals. X in R denotes an indexical
corresponding to a constraint C. S denotes the current store.