This chapter is Copyright (C) 1996-98 LMU
LMU (Ludwig-Maximilians-University)
Munich, Germany
Permission is granted to make and distribute verbatim copies of this chapter provided the copyright notice and this permission notice are preserved on all copies.
Permission is granted to copy and distribute modified versions of this chapter under the conditions for verbatim copying, provided that the entire resulting derived work is distributed under the terms of a permission notice identical to this one.
Permission is granted to copy and distribute translations of this chapter into another language, under the above conditions for modified versions, except that this permission notice may be stated in a translation approved by LMU.
Experience from real-life applications using constraint-based
programming has shown that typically, one is confronted with a
heterogeneous mix of different types of constraints. To be able to
express constraints as they appear in the application and to write and
combine constraint systems, a special purpose language for writing
constraint systems called constraint handling rules (CHR) was
developed. CHR have been used to encode a wide range of constraint
handlers (solvers), including new domains such as terminological and
temporal reasoning. Several CHR libraries exist in declarative
languages such as Prolog and LISP, worldwide more than 20 projects use
CHR. You can find more information about CHR at URL:
http://www.pst.informatik.uni-muenchen.de/personen/fruehwir/chr-intro.html
The high-level CHR are an excellent tool for rapid prototyping and implementation of constraint handlers. The usual abstract formalism to describe a constraint system, i.e. inference rules, rewrite rules, sequents, formulas expressing axioms and theorems, can be written as CHR in a straightforward way. Starting from this executable specification, the rules can be refined and adapted to the specifics of the application.
The CHR library includes a compiler, which translates CHR programs into Prolog programs on the fly, and a runtime system, which includes a stepper for debugging. Many constraint handlers are provided in the example directory of the library.
CHR are essentially a committed-choice language consisting of guarded
rules that rewrite constraints into simpler ones until they are solved.
CHR define both simplification of and propagation over
constraints. Simplification replaces constraints by
simpler constraints while preserving logical equivalence (e.g.
X>Y,Y>X <=> fail). Propagation adds new constraints which are
logically redundant but may cause further simplification (e.g.
X>Y,Y>Z ==> X>Z). Repeatedly applying CHR incrementally simplifies
and finally solves constraints (e.g. A>B,B>C,C>A
leads to fail.
With multiple heads and propagation rules, CHR provide two features which are essential for non-trivial constraint handling. The declarative reading of CHR as formulas of first order logic allows one to reason about their correctness. On the other hand, regarding CHR as a rewrite system on logical formulas allows one to reason about their termination and confluence.
In case the implementation of CHR disagrees with your expectations
based on this chapter, drop a line to the current maintainer:
christian@ai.univie.ac.at (Christian Holzbaur).
We define a CHR constraint for less-than-or-equal, leq, that can
handle variable arguments. This handler can be found in the library as
the file leq.pl. (The code works regardless of options switched
on or off.)
:- use_module(library(chr)). handler leq. constraints leq/2. :- op(500, xfx, leq). reflexivity @ X leq Y <=> X=Y | true. antisymmetry @ X leq Y , Y leq X <=> X=Y. idempotence @ X leq Y \ X leq Y <=> true. transitivity @ X leq Y , Y leq Z ==> X leq Z.
The CHR specify how leq simplifies and propagates as a
constraint. They implement reflexivity, idempotence, antisymmetry and
transitivity in a straightforward way. CHR reflexivity states
that X leq Y simplifies to true, provided it is the case that
X=Y. This test forms the (optional) guard of a rule, a
precondition on the applicability of the rule. Hence, whenever we see a
constraint of the form A leq A we can simplify it to true.
The rule antisymmetry means that if we find X leq Y as well as
Y leq X in the constraint store, we can replace it by the
logically equivalent X=Y. Note the different use of X=Y in
the two rules: In the reflexivity rule the equality is a
precondition (test) on the rule, while in the antisymmetry rule
it is enforced when the rule fires. (The reflexivity rule could also have
been written as reflexivity X leq X <=> true.)
The rules reflexivity and antisymmetry are
simplification CHR. In such rules, the constraints found are
removed when the rule applies and fires. The rule idempotence is
a simpagation CHR, only the constraints right of '\' will
be removed. The rule says that if we find X leq Y and another X
leq Y in the constraint store, we can remove one.
Finally, the rule transitivity states that the conjunction
X leq Y, Y leq Z implies X leq Z. Operationally, we add
X leq Z as (redundant) constraint, without removing the
constraints X leq Y, Y leq Z. This kind of CHR is called
propagation CHR.
Propagation CHR are useful, as the query A leq B,C leq A,B leq C
illustrates: The first two constraints cause CHR transitivity to
fire and add C leq B to the query. This new constraint together
with B leq C matches the head of CHR antisymmetry, X
leq Y, Y leq X. So the two constraints are replaced by
B=C. Since B=C makes B and C equivalent, CHR
antisymmetry applies to the constraints A leq B, C leq A,
resulting in A=B. The query contains no more CHR constraints, the
simplification stops. The constraint handler we built has solved
A leq B, C leq A, B leq C and produced the answer A=B,
B=C:
A leq B,C leq A,B leq C. % C leq A, A leq B propagates C leq B by transitivity. % C leq B, B leq C simplifies to B=C by antisymmetry. % A leq B, C leq A simplifies to A=B by antisymmetry since B=C. A=B,B=C.
Note that multiple heads of rules are essential in solving these constraints. Also note that this handler implements a (partial) order constraint over any constraint domain, this generality is only possible with CHR.
As another example, we can implement the sieve of Eratosthenes to compute primes simply as (for variations see the handler `primes.pl'):
:- use_module(library(chr)). handler eratosthenes. constraints primes/1,prime/1. primes(1) <=> true. primes(N) <=> N>1 | M is N-1,prime(N),primes(M). % generate candidates absorb(J) @ prime(I) \ prime(J) <=> J mod I =:= 0 | true.
The constraint primes(N) generates candidates for prime numbers,
prime(M), where M is between 1 and N.
The candidates react with each other such that each
number absorbs multiples of itself. In the end, only prime numbers remain.
Looking at the two rules defining primes/1, note that head
matching is used in CHR, so the first rule will only apply to
primes(1). The test N>1 is a guard (precondition) on the
second rule. A call with a free variable, like primes(X),
will delay (suspend). The third, multi-headed rule absorb(J)
reads as follows:
If there is a constraint prime(I) and some other constraint
prime(J) such that J mod I =:= 0 holds, i.e. J is a
multiple of I, then keep prime(I) but remove
prime(J) and execute the body of the rule,
true.
CHR extend the Prolog syntax by a few constructs introduced in the next
sections. Technically, the extension is achieved through the
user:term_expansion/2 mechanism. A file that contains a constraint
handler may also contain arbitrary Prolog code. Constraint handling
rules can be scattered across a file. Declarations and options should
precede rules. There can only be at most one constraint handler per module.
Before you can load or compile any file containing a
constraint handler (solver) written in CHR, the chr library
module has to be imported:
| ?- use_module(library(chr)).
It is recommended to include the corresponding directive at the start of your files containing handlers:
:- use_module(library(chr)).
Declarations in files containing CHR affect the compilation and thus the behavior of the rules at runtime.
The mandatory handler declaration precedes any other CHR specific code. Example:
handler minmax.
A handler name must be a valid Prolog atom.
Per module, only one constraint handler can be defined.
The constraints must be declared before they are used by rules. With this mandatory declaration one lists the constraints the rules will later talk about. The declaration can be used more than once per handler. Example:
constraints leq/2, minimum/3, maximum/3.
The following optional declaration allows for conditional rule compilation. Only the rules mentioned get compiled. Rules are referred to by their names (see section Constraint Handling Rules, Syntax). The latest occurrence takes precedence if used more than once per handler. Although it can be put anywhere in the handler file, it makes sense, as with other declarations, to use it early. Example:
rules antisymmetry, transitivity.
To simplify the handling of operator declarations, in particular
during fcompile/1, operator/3 declarations with the
same denotation as op/3, but
taking effect during compilation and loading, are helpful.
Example:
operator(700, xfx, ::). operator(600, xfx, :).
A constraint handling rule has one or more heads, an optional guard, a body and an optional name. A Head is a Constraint. A constraint is a callable Prolog term, whose functor is a declared constraint. The Guard is a Prolog goal. The Body of a rule is a Prolog goal (including constraints). A rule can be named with a Name which can be any Prolog term (including variables from the rule).
There are three kinds of constraint handling rules:
Rule --> [Name @]
(Simplification | Propagation | Simpagation)
[pragma Pragma].
Simplification --> Heads <=> [Guard '|'] Body
Propagation --> Heads ==> [Guard '|'] Body
Simpagation --> Heads \ Heads <=> [Guard '|'] Body
Heads --> Head | Head, Heads
Head --> Constraint | Constraint # Id
Constraint --> a callable term declared as constraint
Id --> a unique variable
Guard --> Ask | Ask & Tell
Ask --> Goal
Tell --> Goal
Goal --> a callable term, including conjunction and disjunction etc.
Body --> Goal
Pragma --> a conjunction of terms usually referring to
one or more heads identified via #/2
The symbol `|' separates the guard (if present) from the body of a
rule. Since `|' is read as `;' (disjunction) by the
reader, care has to be taken when using disjunction in the guard
or body of the rule. The top level disjunction will always be
interpreted as guard-body separator `|', so proper bracketing has
to be used, e.g. a <=> (b;c) | (d;e) instead of a <=> b;c |
d;e and a <=> true | (d;e) instead of a <=> (d;e).
In simpagation rules, `\' separates the heads of the rule into two parts.
Individual head constraints may be tagged with variables via `#', which may be used as identifiers in pragma declarations, for example. Constraint identifiers must be distinct variables, not occurring elsewhere in the heads.
Guards test the applicability of a rule. Guards come in two parts, tell and ask, separated by `&'. If the `&' operator is not present, the whole guard is assumed to be of the ask type.
Declaratively, a rule relates heads and body provided the guard is
true. A simplification rule means that the heads are true if and only
if the body is true. A propagation rule means that the body is true if
the heads are true. A simpagation rule combines a simplification and a
propagation rule. The rule Heads1 \ Heads2 <=> Body is
equivalent to the simplification rule Heads1, Heads2 <=> Heads1,
Body. However, the simpagation rule is more compact to write, more
efficient to execute and has better termination behavior than the
corresponding simplification rule, since the constraints comprising
Heads1 will not be removed and inserted again.
Each CHR constraint is associated with all rules in whose heads it occurs by the CHR compiler. Every time a CHR constraint is executed (called) or woken and reconsidered, it checks itself the applicability of its associated CHR by trying each CHR. By default, the rules are tried in textual order, i.e. in the order they occur in the defining file. To try a CHR, one of its heads is matched against the constraint. Matching succeeds if the constraint is an instance of the head. If a CHR has more than one head, the constraint store is searched for partner constraints that match the other heads. Heads are tried from left to right, except that in simpagation rules, the heads to be removed are tried before the head constraints to be kept (this is done for efficiency reasons). If the matching succeeds, the guard is executed. Otherwise the next rule is tried.
The guard either succeeds or fails. A guard succeeds if the execution of its Ask and Tell parts succeeds and in the ask part no variable that occurs also in the heads was touched or the cause of an instantiation error. The ask guard will fail otherwise. A variable is touched if it is unified with a term (including other variables from other constraints) different from itself. Tell guards, on the contrary, are trusted and not checked for that property. If the guard succeeds, the rule applies. Otherwise the next rule is tried.
If the firing CHR is a simplification rule, the matched constraints are removed from the store and the body of the CHR is executed. Similarly for a firing simpagation rule, except that the constraints that matched the heads preceding `\' are kept. If the firing CHR is a propagation rule the body of the CHR is executed without removing any constraints. It is remembered that the propagation rule fired, so it will not fire again with the same constraints if the constraint is woken and reconsidered. If the currently active constraint has not been removed, the next rule is tried.
If the current constraint has not been removed and all rules have been tried, it delays until a variable occurring in the constraint is touched. Delaying means that the constraint is inserted into the constraint store. When a constraint is woken, all its rules are tried again. (This process can be watched and inspected with the CHR debugger, see below.)
Pragmas are annotations to rules and constraints that enable the compiler to generate more specific, more optimized code. A pragma can be a conjunction of the following terms:
already_in_heads
already_in_head(Id)
passive(Id)
leq, any pair of constraints, say
A leq B, B leq A, that matches the head X leq Y , Y leq X
of the antisymmetry rule, will also match it when the constraints
are exchanged, B leq A, A leq B. Therefore it is enough if a
currently active constraint enters this rule in the first head only,
the second head can be declared to be passive. Similarly for the
idempotence rule. For this rule, it is more efficient to declare
the first head passive, so that the currently active constraint will be
removed when the rule fires (instead of removing the older constraint
and redoing all the propagation with the currently active constraint).
Note that the compiler itself detects the symmetry of the two head
constraints in the simplification rule antisymmetry, thus it is
automatically declared passive and the compiler outputs CHR
eliminated code for head 2 in antisymmetry.
antisymmetry X leq Y , Y leq X # Id <=> X=Y pragma passive(Id). idempotence X leq Y # Id \ X leq Y <=> true pragma passive(Id). transitivity X leq Y # Id , Y leq Z ==> X leq Z pragma passive(Id).Declaring the first head of rule
transitivity passive changes the
behavior of the handler. It will propagate less depending on the order in
which the constraints arrive:
?- X leq Y, Y leq Z. X leq Y, Y leq Z, X leq Z ? ?- Y leq Z, X leq Y. Y leq Z, X leq Y ? ?- Y leq Z, X leq Y, Z leq X. Y = X, Z = X ?The last query shows that the handler is still complete in the sense that all circular chains of leq-relations are collapsed into equalities.
Options parametrise the rule compilation process. Thus they should precede the rule definitions. Example:
option(check_guard_bindings, off).
The format below lists the names of the recognized options together with the acceptable values. The first entry in the lists is the default value.
option(debug_compile, [off,on]).
option(check_guard_bindings, [on,off]).
option(already_in_store, [off,on]).
Constraint \ Constraint <=> true.
option(already_in_heads, [off,on]).
The remaining options are meant for CHR implementors only:
option(flatten, [on,off]).
option(rule_ordering, [canonical,heuristic]).
option(simpagation_scheme, [single,multi]).
option(revive_scheme, [new,old]).
option(dead_code_elimination, [on,off]).
This table lists the predicates made available by the CHR library. They are meant for advanced users, who want to tailor the CHR system towards their specific needs.
current_handler(?Handler, ?Module)
current_constraint(?Handler, ?Constraint)
insert_constraint(+Constraint, -Id)
insert_constraint(+Constraint, -Id, ?Term)
find_constraint(?Pattern, -Id)
find_constraint(-Var, ?Pattern, -Id)
findall_constraints(?Pattern, ?List)
Constraint # Id pairs
from the constraint store that match Pattern.
findall_constraints(-Var, ?Pattern, ?List)
Constraint # Id pairs
from the constraint store that delay on Var and
match Pattern.
remove_constraint(+Id)
unconstrained(?Var)
unconstrained(X) :-
find_constraint(X, _, _), !, fail.
unconstrained(_).
notify_constrained(?Var)
The CHR compilation process has been made as transparent as possible. The user deals with files containing CHR just as with files containing ordinary Prolog predicates. Thus CHR may be consulted, compiled with various compilation modes, and compiled to file (see section Loading Programs).
Besides predicates for the defined constraints, the CHR compiler generates some support predicates in the module containing the handler. To avoid naming conflicts, the following predicates must not be defined or referred to by user code in the same module:
verify_attributes/3
attribute_goal/2
attach_increment/2
'attach_F/A'/2
'F/A_N_M_...'/Arity
For the prime number example that is:
attach_increment/2
attach_prime/1/2
attach_primes/1/2
attribute_goal/2
goal_expansion/3
prime/1
prime/1_1/2
prime/1_1_0/3
prime/1_2/2
primes/1
primes/1_1/2
verify_attributes/3
If an author of a handler wants to avoid naming conflicts with the
code that uses the handler, it is easy to encapsulate the handler.
The module declaration below puts the handler into module primes,
which exports only selected predicates - the constraints in our example.
:- module(primes, [primes/1,prime/1]).
:- use_module(library(chr)).
handler eratosthenes.
constraints primes/1,prime/1.
...
This table lists the operators as used by the CHR library:
:- op(1200, xfx, @). :- op(1190, xfx, pragma). :- op(1180, xfx, [==>,<=>]). :- op(1180, fy, chr_spy). :- op(1180, fy, chr_nospy). :- op(1150, fx, handler). :- op(1150, fx, constraints). :- op(1150, fx, rules). :- op(1100, xfx, '|'). :- op(1100, xfx, \ ). :- op(1050, xfx, &). :- op( 500, yfx, #).
The CHR runtime system reports instantiation and type errors for the predicates:
find_constraint/2
findall_constraints/3
insert_constraint/2
remove_constraint/1
notify_constrained/1
The only other CHR specific runtime error is:
{CHR ERROR: registering <New>, module <Module> already hosts <Old>}
The following exceptional conditions are detected by the CHR compiler:
{CHR Compiler ERROR: syntax rule <N>: <Term>}
{CHR Compiler ERROR: too many general heads in <Name>}
C \ C <=> true
must not be combined with other heads in rule <Name>.
{CHR Compiler ERROR: bad pragma <Pragma> in <Name>}
{CHR Compiler ERROR: found head <F/A> in <Name>, expected one of: <F/A list>}
{CHR Compiler ERROR: head identifiers in <Name> are not unique variables}
{CHR Compiler ERROR: no handler defined}
{CHR Compiler ERROR: compilation failed}
Use option(debug_compile,on) preceding any rules
in the file containing the handler to enable CHR debugging.
The CHR debugging mechanism works by instrumenting the code
generated by the CHR compiler.
Basically, the CHR debugger works like the Prolog debugger.
The main differences are: there are extra ports specific to CHR,
and the CHR debugger provides no means for the user to change
the flow of control, i.e. there are currently no retry and fail
options available.
The entities reflected by the CHR debugger are constraints
and rules. Constraints are treated like ordinary Prolog goals
with the usual ports: [call,exit,redo,fail].
In addition, constraints may get inserted into or removed from the
constraint store (ports: insert,remove), and stored
constraints containing variables will be woken and reconsidered
(port: wake) when variables are touched.
The execution of a constraint consists of trying to apply the rules
mentioning the constraint in their heads. Two ports for rules reflect this
process: At a try port the active constraint matches one of the
heads of the rule, and matching constraints for the remaining heads of
the rule, if any, have been found as well. The transition from a
try port to an apply port takes place when the guard has
been successfully evaluated, i.e. when the rule commits. At the
apply port, the body of the rule is just about to be executed. The
body is a Prolog goal transparent to the CHR debugger. If the
rule body contains CHR constraints, the CHR debugger will track
them again. If the rules were consulted, the Prolog debugger can be
used to study the evaluations of the other predicates in the body.
The following predicates control the operation of the CHR debugger:
chr_trace
chr_leash gives full control over
the ports at which you are prompted.
chr_debug
chr_nodebug
chr_notrace
chr_nodebug.
chr_debugging
chr_leash(+Mode)
call
exit
redo
fail
wake
try
apply
insert
remove
[call,exit,fail,wake,apply]. Predefined shortcuts are:
chr_leash(none), chr_leash(off)
chr_leash(all)
chr_leash(default)
chr_leash([call,exit,fail,wake,apply]).
chr_leash(call)
For CHR programs of any size, it is clearly impractical to creep through the entire program. Spy-points make it possible to stop the program upon an event of interest. Once there, one can set further spy-points in order to catch the control flow a bit further on, or one can start creeping.
Setting a spy-point on a constraint or a rule indicates that you wish to see all control flow through the various ports involved, except during skips. When control passes through any port with a spy-point set on it, a message is output and the user is asked to interact. Note that the current mode of leashing does not affect spy-points: user interaction is requested on every port.
Spy-points are set and removed by the following predicates, which are declared as prefix operators:
chr_spy Spec
already_in_store is in effect.
already_in_heads or the corresponding
pragmas are in effect.
| ?- chr_spy rules rule(3), transitivity, already_in_store. | ?- chr_spy constraints prime/1.If you set spy-points, the CHR debugger will be switched on.
chr_nospy Spec
chr_spy Spec.
There is no chr_nospyall/0. To remove all CHR spy-points use
chr_nospy _.
The options available when you arrive at a spy-point are described later. See section CHR Debugging Options.
All trace messages are output to the standard error stream. This allows you to trace programs while they are performing file I/O. The basic format is as follows:
S 3 1 try eratosthenes:absorb(10) @ prime(9)#<c4>, prime(10)#<c2> ?
S is a spy-point indicator. It is printed as ` ' if there is no spy-point, as `r', indicating that there is a spy-point on this rule, or as `c' if one of the involved constraints has a spy-point.
The first number indicates the current depth of the execution; i.e. the number of direct ancestors the currently active constraint has.
The second number indicates the head position of the currently active constraint at rule ports.
The next item tells you which port is currently traced.
A constraint or a matching rule are printed next.
Constraints print as Term#Id, where Id is a unique
identifier pointing into the constraint store.
Rules are printed as Handler:Name @, followed by the constraints
matching the heads.
The final `?' is the prompt indicating that you should type in one of the debug options (see section CHR Debugging Options).
This section describes the options available when the system prompts you after printing out a debugging message. Most of them you know from the standard Prolog debugger. All the options are one letter mnemonics, some of which can be optionally followed by a decimal integer. They are read from the standard input stream up to the end of the line (Return, <cr>). Blanks will be ignored.
The only option which you really have to remember is `h'. This provides help in the form of the following list of available options.
CHR debugging options:
<cr> creep c creep
l leap
s skip s <i> skip (ancestor i)
g ancestors
& constraints & <i> constraints (details)
n nodebug = debugging
+ spy this
- nospy this . show rule
< reset printdepth < <n> set printdepth
a abort b break
? help h help
exit port or the fail port). This includes
ports with spy-points set; they will be masked out during the skip.
The command can be used with a numeric argument to skip the execution
up to and including the ancestor indicated by the argument.
Example:
...
4 - exit prime(8)#<c6> ? g
Ancestors:
1 1 apply eratosthenes:rule(2) @ primes(10)#<c1>
2 1 apply eratosthenes:rule(2) @ primes(9)#<c3>
3 1 apply eratosthenes:rule(2) @ primes(8)#<c5>
4 - call prime(8)#<c6>
4 - exit prime(8)#<c6> ? s 2
2 - exit primes(9)#<c3> ?
call entries in the stack.
The subsequent application of a rule replaces the call entry
in the stack with an apply entry. Later the constraint
shows again as redo or fail entry.
Example:
0 - call primes(10)#<c1> ?
1 1 try eratosthenes:rule(2) @ primes(10)#<c1> ? g
Ancestors:
1 - call primes(10)#<c1>
1 1 try eratosthenes:rule(2) @ primes(10)#<c1> ?
1 1 apply eratosthenes:rule(2) @ primes(10)#<c1> ?
1 - call prime(10)#<c2> ?
2 - insert prime(10)#<c2>
2 - exit prime(10)#<c2> ? g
Ancestors:
1 1 apply eratosthenes:rule(2) @ primes(10)#<c1>
2 - call prime(10)#<c2>
chr_debugging/0
8 1 apply era:absorb(8) @ prime(4)#<c14> \ prime(8)#<c6> ? .
absorb(8) @
prime(4)#<c14> \
prime(8)#<c6> <=>
8 mod 4=:=0
|
true.
abort/0.
break/0, thus putting
you at a recursive top-level. When you end the break
(entering ^D) you will be
re-prompted at the port at which you broke. The CHR debugger is
temporarily switched off as you call the break and will be switched
on again when you finish the break and go back to the old execution.
Any changes to the CHR leashing or to spy-points during the break
will remain in effect.
This section gives you some programming hints for CHR. For maximum efficiency of your constraint handler, see also the previous subsections on declarations and options.
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. CHR 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 do not occur in the application can be ignored.
It is important to find the right granularity of the constraints.
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 n*n inequality
constraints between each pair of different variables. However, the
extreme case of having a single constraint modeling the whole constraint
store will usually be inefficient.
Starting from an executable specification, the rules can then be refined and adapted to the specifics of the application. Efficiency can be improved by weakening the guards to perform simplification as early as needed and by strengthening the guards to do the just right amount of propagation. Propagation rules can be expensive, because no constraints are removed.
The more heads a rule has, the more expensive it is. Rules with several heads are more efficient, if the heads of the rule share a variable (which is usually the case). Then the search for a partner constraint has to consider less candidates. In the current implementation, constraints are indexed by their functors, so that the search is only performed among the constraints containing the shared variable. 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.
As guards are tried frequently, they should be simple tests
not involving side-effects. Head matching is more efficient than
explicitly checking equalities in the ask-part of the guard. In the
tell part of a guard, it should be made sure that variables from the
head are never touched (e.g. by using nonvar or ground if
necessary). For efficiency and clarity reasons, one should also avoid
using constraints in guards. Besides conjunctions, disjunctions are
allowed in the guard, but they should be used with care. The use of
other control built-in predicates in the guard is
discouraged. Negation and if-then-else in the ask part of a guard can
give wrong results, since e.g. failure of the negated goal may be due to
touching its variables.
Several handlers can be used simultaneously if they do not share constraints with the same name. The 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.
The CHR library comes with plenty of constraint handlers written in CHR. The most recent versions of these are maintained at:
http://www.pst.informatik.uni-muenchen.de/~fruehwir/chr-solver.html
functor/3, arg/3, =../2 as constraints
You can consult or compile a constraint handler from the CHR library using e.g.:
?- [library('chr/examples/gcd')].
?- compile(library('chr/examples/gcd')).
If you want to learn more about the handlers, look at their documented source code.
In addition, there are files with example queries for some handlers, their file name starts with `examples-' and the file extension indicates the handler, e.g. `.bool':
examples-adder.bool examples-benchmark.math examples-deussen.bool examples-diaz.bool examples-fourier.math examples-holzbaur.math examples-lim1.math examples-lim2.math examples-lim3.math examples-puzzle.bool examples-queens.bool examples-queens.domain examples-stuckey.math examples-thom.math
In this section, we discuss backward compatibility with the CHR library of Eclipse Prolog.
option(rule_ordering,heuristic). option(revive_scheme,old).
already_in_store,
already_in_head and guard_bindings options
are still around, but there are CHR syntax extensions: section Constraint Handling Rules, Syntax
and pragmas section Pragmas
offering better grained control.
label_with declaration. Since it was not widely used
and can be easily simulated, built-in labeling was dropped.
The same effect can be achieved
by replacing the declaration label_with Constraint
if Guard by the simplification rule chr_labeling, Constraint <=>
Guard | Constraint', chr_labeling and by renaming the head in each
clause Constraint :- Body into Constraint' :- Body where
Constraint' is a new predicate. Efficiency can be improved by
declaring Constraint to be passive: chr_labeling,
Constraint#Id <=> Guard | Constraint', chr_labeling pragma passive(Id).
This translation will not work if option(already_in_heads,on).
In that case use e.g. chr_labeling(_), Constraint <=> Guard |
Constraint', chr_labeling(_) to make the new call to
chr_labeling differ from the head occurrence.
Go to the first, previous, next, last section, table of contents.