There are two elegant and simple ways of building constraints available in ECL^{i}PS^{e}, 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 ECL^{i}PS^{e} 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 ECL^{i}PS^{e} 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.