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 interval-consistency, which is significantly cheaper to maintain than domain-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 narrower, 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
domain-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:

`Head``+:`

`Indexicals``.`

- The clause consists of propagating indexicals for solving
`C`. `Head``-:`

`Indexicals``.`

- The clause consists of propagating indexicals for solving the
negation of
`C`. `Head``+?`

`Indexical``.`

- The clause consists of a single checking indexical for testing
entailment of
`C`. `Head``-?`

`Indexical``.`

- The clause consists of a single checking indexical for testing
entailment of the negation of
`C`.

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.