Up Next

15.1  Two Ways of Specifying Constraint Behaviours

There are two elegant and simple ways of building constraints available in ECLiPSe, called Propia and Constraint Handling Rules (or CHR’s). They are themselves built using the facilities described in chapter 14.

Consider a simple noclash constraint requiring that two activities cannot be in progress at the same time. For the sake of the example, the constraint involves two variables, the start times S1 and S2 of the two activities, which both have duration 5. Logically this constraint states that noclash ⇔ (S1 >= S2 + 5 ∨ S2 >= S1 + 5). The same logic can be expressed as two ECLiPSe clauses: 

noclash(S1,S2) :-
    ic:(S1 $>= S2+5).
noclash(S1,S2) :-
    ic:(S2 $>= S1+5).

Constraint propagation elicits information from constraints without leaving any choice points. Constraint propagation behaviour can be associated with each of the above representations, by CHR’s and by Propia.

One way to propagate information from noclash is to wait until the domains of the start times are reduced sufficiently that only one ordering of the tasks is possible, and then to enforce the constraint that the second task not start until the first is finished.

This behaviour can be implemented in CHR’s as follows: 

:- constraints noclash/2.
noclash(S1,S2) <=> ic:(S2 #< S1+5) | ic:(S1 #>= S2+5).
noclash(S1,S2) <=> ic:(S1 #< S2+5) | ic:(S2 #>= S1+5).

Consider the query: 

?- ic:([S1,S2]::1..10),
   noclash(S1,S2),
   S1 #>= 6.

In this query noclash achieves no propagation when it is initially posted with the start time domains set to 1..10. However, after imposing S1>=6, the domain of S1 is reduced to 6..10. Immediately the noclash constraint wakes, detects that the first condition S1+5 >= S2 is entailed, and narrows the domain of S2 to 1..5.

The same behaviour can be expressed in Propia, but this time the original ECLiPSe representation of noclash as two clauses is used directly. The propagation behaviour is automatically extracted from the two clauses by Propia when the noclash goal is annotated as follows: 

?-      [S1,S2]::1..10,
        noclash(S1,S2) infers most,
        S1 #>= 6.

Propia and CHRs make it easy to turn the logical statement of a constraint into code that efficiently enforces that constraint.
Figure 15.1: Building Constraints without Tears
Up Next