Programming Constraint Propagators

AR is a powerful implementation language for programming constraint propagators [17]. This chapter shows how to program constraint propagators for various constraints.

The following set of event patterns are provided for programming constraint propagators:

• generated: When an agent is generated.
• ins(X): When any variable in X is instantiated.
• bound(X): When the lower or upper bound of any variable in X is updated. There is no distinction between lower bound changes and upper bound changes.
• dom(X): When some inner element has been excluded from the domain of X.
• dom(X,E): When an inner element E has been excluded from the domain of X.
• dom_any(X): When some arbitrary element has been excluded from the domain of X.
• dom_any(X,E): When an arbitrary element E has been excluded from the domain of X.

Note that, when a variable is instantiated, no bound or dom event is posted. Consider the following example:

p(X),{dom(X,E)} => write(dom(E)).

q(X),{dom_any(X,E)} => write(dom_any(E)).

r(X),{bound(X)} => write(bound).

go:-X :: 1..4, p(X), q(X), r(X), X #\= 2, X #\= 4, X #\= 1.

The query go gives the following outputs: dom(2), dom_any(2), dom_any(4), and bound.^14.1 The outputs dom(2) and dom_any(2) are caused by X #\= 2, and the outputs dom_any(4) and bound are caused by X #\= 4. After the constraint X #\= 1 is posted, X is instantiated to 3, which posts an ins(X) event, but does not post a bound event or a dom event.

Also note that the dom_any(X,E) event pattern should only be used on small-sized domains. If it is used on large domains, constraint propagators could be over-flooded with a huge number of dom_any events. For instance, for the propagator q(X) that was defined in the previous example, the query

      X :: 1..1002, q(X), X #>1000

posts 1000 dom_any events. For this reason, in B-Prolog, propagators for handling dom_any(X,E) events are only generated after constraints are preprocessed, and after the domains of the variables in the constraints become small.

Except for dom(X,E) and dom_any(X,E), which have two arguments, none of the events have extra information to be transmitted to their handlers. An action rule can handle multiple single-parameter events. For example, for the following rule,

      p(X),{generated,ins(X),bound(X)} => q(X).

p(X) is activated when p(X) is generated, when X is instantiated, or when either bound of X's domain is updated.

The following two types of conditions can be used in the guards of rules:

• dvar(X): X is an integer domain variable.
• n_vars_gt(M,N): The number of variables in the last M arguments of the agent is greater than N, where both M and N must be integer constants. Note that the condition does not take the arguments whose variables are to be counted. The system can always fetch that information from its parent call. This built-in should only be used in guards of action rules or matching clauses. The behavior is unpredictable if this built-in is used elsewhere.