A new, extended, chr library has been developed, with the intention of providing the basis for a system that will allow more optimisations than the previous implementation. At the same time, some of the syntax of the CHR has been changed to conform better to standard Prolog.
The system is still experimental, and provides no special support for debugging CHR code. Please report any problems encountered while using this system.
The main user visible differences from the original chr library are as follows:
The extended library is invoked by lib(ech). Given that it is now
integrated into the compiler. It can be invoked from a file that contains
CHR code, as :- lib(ech)., as long as this occurs before the CHR
code.
As programs containing CHRs are no longer compiled by a separate process, the .chr extension is no longer implicitly supported. Files with the .chr extension can still be compiled by explicitly specifying the extension in the compile command, as in [’file.chr’]. Associated with this change, there are some changes to the declarations of the .chr format:
The syntax for naming a rule has been changed, because the old method (using @ clashes with the use of @ in modules. The new operator for naming rules is ::=. Here is part of the minmax handler in the new syntax:
:- handler minmax. :- constraints leq/2, neq/2, minimum/3, maximum/3. :- op(700, xfx, leq). built_in ::= X leq Y <=> \+nonground(X), \+nonground(Y) | X @=< Y. reflexivity ::= X leq X <=> true. ...
After loading the extended chr library, programs containing CHR code can be compiled directly. Thus, CHR code can be freely mixed with normal Prolog code in any file. In particular, a compilation may now compile code from different files in different modules which may all contain CHR codes. This was a problem with the old library because CHR code had to be compile separately.
In the extended library, CHR code can occur anywhere in a particular module, and for each module, all the CHR code (which may reside in different files) will all be compiled into one unit (handler declarations are ignored by the system, they are present for compatibility purposes only), with the same constraint store. CHR code in different modules are entirely separate and independent from each other.
In order to allow CHR code to occur anywhere inside a module, and also
because it is difficult to define a meaning for replacing multi-heads rules,
compilation of CHR code is always incremental when a new file for a
module is compiled, i.e. any existing CHR
code in a module is not replaced by those in the newly compiled
file. However, when the whole module is recompiled (i.e. compiling a file
with the module/1 directive), or if the module is erased, then any
existing CHR code in the module is erased along with the other code in the
module.
It is possible to clear out old CHR code in all modules when compiling a file. This is done with the chr/1 predicate. This first remove any existing CHR code in any module before the compilation starts. It thus approximates the semantics of chr/1 of the old library, but no Prolog file is generated. It is mainly intended for compatibility with the old library, and when you are using CHR without using the module facilities.
In the old chr library, it was not clearly defined when a constraint will be added to or removed from the constraint store during the execution of a rule. In the extended chr library, all head constraints that occur in the head of a rule are mutually exclusive, i.e. they cannot refer to the same constraint. This ensures that similar heads in a rule will match different constraints in the constraint store. Beyond this, the state of a constraint – if it is in the constraint store or not – that has been matched in the head is not defined during the execution of the rest of the head and guard. As soon as the guard is satisfied, any constraints removed by a rule will no longer be in the constraint store, and any constraint that is not removed by the rule will be present in the constraint store.
This can have an effect on execution. For example, in the finite domain example in the old chr directory (domain.chr), there is the following rule:
X lt Y, X::[A|L] <=>
\+nonground(Y), remove_higher(Y,[A|L],L1), remove(Y,L1,L2) |
X::L2.
Unfortunately this rule is not sufficiently specified in the extended
CHR, and can lead to looping under certain circumstances. The two remove predicate in the guard removes elements from the domain, but if no
elements are removed (because X lt Y is redundant, e.g. X lt 5 with
X::[1..2]), then in the old CHR execution, the body goal, the constraint
X::L2 would not be actually executed, because the older constraint in
the head (the one that matched X::[A|L]) has not yet been removed when
the new constraint is imposed. With the extended CHR, the old constraint
is removed after the guard, so the X::L2 is executed, and this can
lead to looping. The rule should thus be written as:
X lt Y, X::[A|L] <=>
\+nonground(Y), remove_higher(Y,[A|L],L1), remove(Y,L1,L2),
L2\==[A|L] |
X::L2.
Consider the following propagation rule:
p(X), q(Y) ==> <Body>. :- p(X).
The execution of this rule, started by calling p(X), will try to match
all q(Y) in the constraint store, and thus it can be satisfied,
with <Body> executed,
multiple number of times with different q(Y). <Body> for
a particular q(Y) will be executed first, before trying to match
the next q(Y). The execution of <Body> may however cause the
removal of p(X). In this case, no further matching with q(Y)
will be performed.
Note that there is no commitment with propagation and simpagation rule if the constraint being matched is not removed:
p(X), q(Y) ==> <Body1>. p(X), r(Y) ==> <Body2>. :- p(X).
Both rules will always be executed.
The body of a rule is executed as soon as its guard succeeds. In the case of propagation rules, this means that the other propagation rules for this constraint will not be tried until the body goals have all been executed. This is unlike the old CHR, where for propagation rules, the body is not executed until all the propagation rules have been tried, and if more than one propagation rule has fired (successful in its guard execution), then the most recently fired rule’s body is executed first. For properly written, mutually exclusive propagation rule, this should not make a difference (modulo the effect of the removal of constraints in the body).
The priority at which an ECH rule is executed depends on the ‘active’ constraint, i.e. the constraint that triggered the execution of the rules. Normally, the ECH rules are executed at the default priority, but a different priority can be associated with a constraint when it is declared, specifying the priority at which the ECH rules will be executed when that constraint is the active constraint.
:- constraints chr_labeling/0:at_lower(1).
this specifies that if chr_labeling/0 was the active constraint, then the rules will be executed at a lower priority than the default. The priorities are mapped to the priority system of ECLiPSe, and at_lower(1) maps to a priority one lower than the default, so that ECH rules executing at the default priority will execute first. This is particularly useful for labelling, as this allow the other ECH constraints to be executed during the labelling process rather than afterwards.
The priority specified can be at_lower(N), at_higher(N), or at_absolute_priority(N). For at_lower(N), the priority is the default + N; for at_higher(N), it is the default - N. at_absolute_priority(N) sets the priority to N, regardless of the default, and its use is not recommended. The available priorities are from 1 (highest) to 11 (lowest). The default priority is initially set to 9, but can be changed with the chr_priority option. Note that the priority at which the rules will run at is determined at compile time, and changing the default priority will only affect new constraints compiled after the change. It should therefore only be used in a directive before any of the ECH rules.
This behaviour is different from the old chr library, and from older versions of ech library, where the rules ran at different priorities before and after suspension. This can lead to different behaviours with the same rule, either with other constraints solvers, or even with other CHR rules, as a woken CHR executes at much higher priority than the initial run. With the current ech execution, the rules are executed at the same priority before and after suspension, for the same active constraint. The default priority is set at 9 so that it is very likely to be lower than the priority used in other constraint solvers. The user is now allowed to alter the priority of specific ECH constraints to allow the user more control so that for example a labelling rule can run at a lower priority than the other constraints.
The check_guard_bindings and already_in_store options from
the old chr library are supported. Note that the extended compiler can
actually detect some cases where guard bindings cannot constrain any global
variables (for example, var/1), and will in such cases no check
guard bindings.
New options, intended to control the way the compiler tries to optimise
code, are introduced. These are intended for the developers of the compiler,
and will not be discussed in detail here. The only currently supported
option in this category is single_symmetric_simpagation.
Another new option, default_chr_priority, allows the default
priority to be changed, e.g.
:- option(default_chr_priority, 6).
changes the default priority to 6, so the compiler would generate new CHR code which defaults to this priority (unless overridden in the constraints declaration). The available values are from 1 to 11.
The old CHR built-ins, chr_get_constraint/1 and
chr_get_constraint/2 are both implemented in this library.
A new built-in predicate, in_chrstore/1, is used to inspect the
constraint store:
in_chrstore(+Constraint)
is used to test if Constraint is in the constraint store or not. It
can be used to prevent the addition of redundant constraints:
X leq Y, Y leq Z ==> \+in_chrstore(X leq Z)| X leq Z.
The above usage is only useful if the already_in_store option is
off. Note that as the state of a constraint that appears in the head is
not defined in the guard, it is strongly suggested that the user does not
perform this test in the guard for such constraints,
A source to source transformation is performed on CHR code by the compiler, and the resulting code is compiled in the same module as the CHR code. These transformed predicates all begin with ’CHR’, so the user should avoid using such predicates.