Next: Execution of Propagating Indexicals, Previous: Monotonicity of Ranges, Up: Defining Primitive Constraints [Contents][Index]

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 bounds 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 the variables
involved and the finite domains with which their domains should be
intersected when the propagator is run. Therefore the FD predicate with
`n` arguments consists of `n` indexicals, each specifying a left
hand side variable and a right hand side expression that evaluates to a
finite domain, which is a function of the expression and of the
constraint store. For example, the third indexical in the above FD
predicate evaluates to the finite domain `3..13` for `T` if
`D(X,S) = 1..5` and `D(Y,S) = 2..8`. As the domain of some
variables gets smaller, the indexical may further narrow the domain of
other variables. Therefore such an indexical (called a propagating
indexical) acts as a coroutine 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 coroutine is blocked. When the indexical becomes unblocked, it computes a finite domain for intersecting with the domain of its left hand side. The coroutine then waits until some change occurs in a domain of a variable occurring in its right hand side. Eventually, the computation reaches a point when the indexical is entailed by the store, i.e. no changes in its right hand side can prune its left hand side any longer, and the coroutine can cease to exist.

Note that FD predicates must be correct and checking (see CLPFD Interface).

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, then 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, then 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 body consists of propagating indexicals for solving

`C`. The body can in fact be of a more general form—see Compiled Indexicals.`Head`-:`Indexicals`.The body consists of propagating indexicals for solving the negation of

`C`.`Head`+?`Indexical`.The body consists of a single checking indexical for testing entailment of

`C`.`Head`-?`Indexical`.The body consists of a single checking indexical for testing entailment of the negation of

`C`.

When a constraint is reified as in

,
the solver spawns two coroutines corresponding to detecting entailment
and disentailment. Eventually, one of them will succeed in this and
consequently will bind `Constraint` #<=> `B``B` to 0 or 1. A third coroutine 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 coroutine is
dismissed.

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.

denotes an indexical
corresponding to a constraint `X` in `R``C`. `S` denotes the current
store.

Send feedback on this subject.