Previous Up Next

9.7  Writing Good CHR Programs

This section gives some programming hints. For maximum efficiency of your constraint handler, see also the subsection on options, especially on check_guard_bindings and the debug_compile flag.

9.7.1  Choosing CHRs

Constraint handling rules for a given constraint system can often be derived from its definition in formalisms such as inference rules, rewrite rules, sequents, formulas expressing axioms and theorems. CHRs can also be found by first considering special cases of each constraint and then looking at interactions of pairs of constraints sharing a variable. Cases that don’t occur in the application can be ignored. CHRs can also improve application programs by turning certain predicates into constraints to provide “short-cuts” (lemmas). For example, to the predicate append/3 one can add append(L1,[],L2) <=> L1=L2 together with label_with append(L1,L2,L3) if true.

Starting from an executable specification, the rules can then be refined and adapted to the specifics of the application. Efficiency can be improved by strengthening or weakening the guards to perform simplification as early as needed and to do the “just right” amount of propagation. Propagation rules can be expensive, because no constraints are removed. If the speed of the final handler is not satisfactory, it can be rewritten using meta-terms or auxiliary C functions.

The rules for a constraint can be scattered across the chr file as long as they are in the same module. The rules are tried in some order determined by the CHR compiler. Due to optimizations this order is not necessarily the textual order in which the rules where written. In addition, the incremental addition of constraints at run-time causes constraints to be tried for application of rules in some dynamically determined order.

9.7.2  Optimizations

Single-headed rules should be preferred to two-headed rules which involve the expensive search for a partner constraint. Rules with two heads can be avoided by changing the “granularity” of the constraints. For example, assume one wants to express that n variables are different from each other. It is more efficient to have a single constraint all_different(List_of_n_Vars) than n2 inequality constraints (see handler domain.chr). However, the extreme case of having a single constraint modelling the whole constraint store will usually be inefficient.

Rules with two heads are more efficient, if the two heads of the rule share a variable (which is usually the case). Then the search for a partner constraint has to consider less candidates. Moreover, two rules with identical (or sufficiently similar) heads can be merged into one rule so that the search for a partner constraint is only performed once instead of twice.

Rules with more than two heads are not allowed for efficiency reasons. If needed, they can usually be written as several rules with two heads. For example, in the handler for set constraints set.chr, the propagation rule:

set_union(S1, S2, S), set(S1, S1Glb, S1Lub), set(S2, S2Glb, S2Lub) ==>
        s_union(S1Glb, S2Glb, SGlb),
        s_union(S1Lub, S2Lub, SLub),
        set(S, SGlb, SLub).

is translated into:

set_union(S1, S2, S), set(S1, S1Glb, S1Lub) ==>
        '$set_union'(S2, S1, S1Glb, S1Lub, S).
set(S2, S2Glb, S2Lub) \ '$set_union'(S2, S1, S1Glb, S1Lub, S) <=>
        s_union(S1Glb, S2Glb, SGlb),
        s_union(S1Lub, S2Lub, SLub),
        set(S, SGlb, SLub).

As guards are tried frequently, they should be simple tests not involving side-effects. For efficiency and clarity reasons, one should also avoid using user-defined constraints in guards. Currently, besides conjunctions, disjunctions are allowed in the guard, but they should be used with care. The use of other control built-in predicates of ECLiPSe is discouraged. Negation and if-then-else can be used if their first arguments are either simple goals (see ECLiPSe user manual) or goals that don’t touch global variables. Similarly, goals preceding a cut must fulfil this condition. Built-in constraints (e.g. finite domains, rational arithmetic) work as tests only in the current implementation. Head matching is more efficient than explicitly checking equalities in the guard (which requires the check_guard_bindings flag to be on). In the current implementation, local variables (those that do not occur in the heads) can be shared between the guard and the body.

Several handlers can be used simultaneously if they don’t share user-defined constraints. The current implementation will not work correctly if the same constraint is defined in rules of different handlers that have been compiled separately. In such a case, the handlers must be merged “by hand”. This means that the source code has to be edited so that the rules for the shared constraint are together (in one module). Changes may be necessary (like strengthening guards) to avoid divergence or loops in the computation.

Constraint handlers can be tightly integrated with constraints defined with other extensions of ECLiPSe (e.g. meta-terms) by using the ECLiPSe built-in predicate notify_constrained(Var) to notify ECLiPSe each time a variable becomes more constrained. This happens if a user-defined constraint is called for the first time or if a user-defined constraint is rewritten by a CHR into a stronger constraint with the same functor.

For pretty printing of the user-defined constraints in the answer at the top-level and debuggers, ECLiPSe macro transformation (for write mode) can be used. This is especially useful when the constraints have some not so readable notation inside the handler. For an example, see the constraint handler bool bool.chr.

Previous Up Next