FD Predicates (SICStus Prolog)

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

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.

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:

When a constraint is reified as in Constraint #<=> B, the solver spawns two coroutines 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 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. X in R denotes an indexical corresponding to a constraint C. S denotes the current store.

10.9.10.7 FD Predicates