10.9.13.4 Indexical Constraints

The following example defines the constraint X+Y=T with 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, but the constaint itself can be called as a Prolog predicate. An indexical may wipe out a variable’s domain, in which case backtracking is triggered, as usual.

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 composed of three propagating indexicals. The first indexical wakes up whenever the bounds of T or Y are updated, and removes from the domain of X 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, the domain of X may still contain some values that are incompatible with X+Y=T. 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 indexical constraint is called, the ‘+:’ clause is activated.

The definition of an indexical has to specify the variables involved and the domain expressions with which their domains should be intersected when the propagator is run. Therefore the indexical constraint with n arguments usually consists of n indexicals, each specifying a left hand side variable and a right hand side expression that evaluates to a set of integers, which is a function of the expression and of the constraint store. For example, the third indexical in the above indexical predicate evaluates to the set 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.

There can be several alternative definitions for the same 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.

If the program only uses a constraint in non-reified contexts, 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 disentailment (entailment of the negation) of C.

When a constraint is reified as in Constraint #<=> B, the solver spawns two coroutines corresponding to detecting entailment and disentailment. Then, eventually, one of the following cases occur after some amount of search and/or propagation:

1. The ‘+?’ indexical detects entailment. The two checking indexicals are disabled and B is bound to 1.
2. The ‘-?’ indexical detects disentailment. The two checking indexicals are disabled and B is bound to 0.
3. B gets bound to 1 by search and/or propagation. The two checking indexicals are disabled and the ‘+:’ indexicals are enabled.
4. B gets bound to 0 by search and/or propagation. The two checking indexicals are disabled and the ‘-:’ indexicals are enabled.

The life cycle of a propagating indexical X in R of constraint C can be described as follows:

• It is suspended until it is provably contracting, and then it is evaluated.
• It is re-evaluated whenever one of the following conditions occurs:
  1. The domain of a variable Y that occurs as dom(Y) or card(Y) in R has been updated.
  2. The lower bound of a variable Y that occurs as min(Y) in R has been updated.
  3. The upper bound of a variable Y that occurs as max(Y) in R has been updated.
• Upon evaluation, X is pruned; three cases exist:
  1. The domain of X was wiped out: backtracking,
  2. The domain of X was not wiped out and R is now a ground expression, i.e., its value cannot contract any more: the constraint is considered entailed (disentailed) for ‘+:’ (‘-:’) indexicals; all active indexicals of constraint C are disabled.
  3. Otherwise, all active indexicals of constraint C remain active.

The life cycle of a checking indexical X in R of constraint C reified to variable B can be described as follows:

• It is suspended until it is provably expanding, and then it is evaluated.
• It is re-evaluated whenever one of the following conditions occurs:
  1. The domain of a variable Y that occurs as dom(Y) or card(Y) in R has been updated.
  2. The lower bound of a variable Y that occurs as min(Y) in R has been updated.
  3. The upper bound of a variable Y that occurs as max(Y) in R has been updated.
• Upon evaluation, the domain of X is compared with the value of R; two cases exist:
  1. The domain of X is included in the value of R: the constraint is considered entailed (disentailed) and B is bound to 1 (0) for ‘+:’ (‘-:’) indexicals; all active indexicals of constraint C are disabled.
  2. Otherwise, all active indexicals of constraint C remain active.