| Home | - | Documentation | - | Sources | - | Contributors | - | Related Links |
A CHR constraint handler (also called constraint solver or constraint program) basically consists of rules which define the behavior of one or more constraints. The rules need to be defined in JCHR. These rules are translated with the JCHR compiler into a Java class which provides the rules as class members. This constraint handler class can be loaded into a constraint system, which can use the rules to solve constraint problems (see Section Interface JCHR - Java). In addition to rules, goals can be given. Then, the constraint handler class can be executed as a stand-alone program. This is mainly useful for small programs or for testing purposes. A tracer is available.
handler followed by the name of the handler and the code
of the handler written in curly brackets (enclosing blocks as known from Java):
handler leq {
...
}
A JCHR constraint handler consists of three sections: declarations,
rules and goals (in that order). Goals for constraints are
optional, while a handler without declaring constraints and rules
for them would not make much sense.
There are two ways of using a constraint handler written in JCHR: Calling it from Java (see Section Interface JCHR - Java) or running it stand-alone using goals. The former will be the usual case in full-fledged applications, while the latter will be helpful for testing and small examples that do not require search. (Search is provided by the JASE library). When used from Java, the goals of the constraint handler will be ignored.
A class import is defined by the keyword class
followed by the class name as it can be found in the class path. All
classes used in the following need to be imported, including the
classes mentioned in the constraint signatures.
A constraint is declared by the keyword constraint
followed by the name of the constraint and its argument types (much
like a Java method):
handler leq {
class java.lang.Integer;
class IntUtil;
constraint leq(java.lang.Integer, java.lang.Integer, java.lang.Integer);
Variables that appear in constraints are called logical
variables. Logical variables and class instances must be declared at
the beginning of the rules section and at the beginning of each goal
in the goals section.
Logical variables are defined by the keyword variable
followed by a type and variable names:
handler leq {
rules {
variable java.lang.Integer X, Y, Z;
...
}
}
JCHR can only handle objects. That means, simple Java types like
int need to be used in wrapper classes like
java.lang.Integer. The JCHR-Compiler currently
supports the following simple types. All other types/objects are
declared as usual in Java.
| Type | Example in JCHR |
| boolean | true | false |
| string | "abc" |
| character | 'a' |
| integer | 512 |
| float | 3.4 |
variable Boolean X;
...
X = new Boolean(true)
...
Note that type names are not case sensitive. When true oder
false is used without the Java constructor, these
keywords are interpreted as built-in constraints. X =
123 is possible (the number 123 is interpreted as an
integer), but X = new Integer(123) is recommended.
Type casting is allowed for all objects, except for method calls or logical variables.
variable Float Y;
variable Boolean X;
X = IntUtil.le(1,(Integer)1.2) // allowed
Y = (Float)IntUtil.min(1,1) // not allowed
X = (Boolean)Y // not allowed
if
Guard
{
Head
}
==>
{
Body
}
RuleName
;
if
Guard
{
Head
}
<=>
{
Body
}
RuleName
;
if
Guard
{
Head1
&\&
Head2
}
<=>
{
Body
}
RuleName
;
true and false, the first always holds,
the second never holds. Moreover, syntactical equality =
as provided as a built-in constraint, it can be applied to
constants and logical variables, regardless of their type. As long has
both arguments have the same type. If a method is called on the right
hand side of the equality symbol =, the return type
needs to be equal to the type of the object on the left hand side.
A rule consists of an optional guard, a head
(left hand side) and a body (right hand side). These parts are all
conjunctions using the infix operator &&.
The head Head is a conjunction of user-defined
constraints. The guard is optional. If present the guard is a
conjunction of built-in constraints and Java methods. If the guard is
not present, it has the same meaning as the guard true.
The body Body is a conjunction of user-defined
constraints, built-in constraints and Java methods.
When used as a conjunct of a rule or goal, a method always has to
return a boolean value.
Finally, a rule has an optional name, RuleName, which is a Java
identifier.
le of the class IntUtil is defined by:
public boolean le(Integer i1, Integer i2) {
return ( i1.IntValue() <= i2.IntValue() );
}
Methods calls may take logical variables as arguments. But only if
these variables are known, i.e. if they are bound to a value, the
execution of the method makes sense. Otherwise, the method
call will cause an interrupt. When the interrupt occurs during the
execution of the guard of the rule, the guard will simply fail and
execution will proceed with the next rule.
With this behavior, a method which tests whether a variable is
bound (ground) can be implemented easily:
public boolean ground(Integer i) {
return true;
}
When this method is called in the guard of a rule with a
variable as an argument, this method is executed when the variable
is bound. Then true is returned. Otherwise, when the variable is
not bound to a value, the execution of the method
ground is interrupted and the guard fails. So the
semantics of testing a variable to be ground is achieved.
if (X=IntUtil.min(List) && IntUtil.gt(X,2)) {
fdEnu(Y, List)
} <=> ...
In this example, the variable List occurs in the
head and the variable X is bound to the
minimum of this list. So this guard is correct. The
following example is not correct:
if (IntUtil.gt(X,2)) {
fdEnu(Y, List)
} <=> ...
The variable X is not bound to a value and does not
occur in the head of the rule. This will result in a run-time error.
In a body, one may use variables from the head, bound variables from the guard or introduce new variables.
if ( N=3 && IntUtil.lt(M,N) ) {
p(M,L)
} <=> {
p(N,L)
} r1;
goal. A goal
consists of declarations for the variables and class instances
followed by the goal itself. A JCHR goal is a conjunction of
constraints and Java methods, for example (also see next section):
goal Circular {
variable java.lang.integer A, B, C;
leq(A, B) && leq(B, C) && leq(C, A)
}
goal Big {
...
}
back
leq.
handler leq {
class IntUtil;
constraint leq(java.lang.Integer, java.lang.Integer);
rules {
variable java.lang.Integer X, Y, Z;
if (X=Y) { leq(X, Y) } <=> { true } reflexivity;
{ leq(X, Y) && leq(Y, X) } <=> { X=Y } antisymmetry;
{ leq(X, Y) &\& leq(X, Y) } <=> { leq(X, Y) } idempotence;
{ leq(X, Y) && leq(Y, Z) } ==> { leq(X, Z)} transitivity;
if (IntUtil.ground(X) && IntUtil.ground(Y))
{ leq(X, Y) } <=> { IntUtil.le(X, Y) } ground;
}
goal Circular {
variable java.lang.integer A, B, C;
leq(A, B) && leq(B, C) && leq(C, A)
}
}
The first line states that this is the definition of the constraint
handler leq. The handler can be divided into three main
sections, for declarations, rules and goals.
leq is
defined by the keyword constraint. Here, the constraint
leq expects two arguments of the type
java.lang.Integer.
X, Y and Z of the type
java.lang.Integer are declared. The following rules
implement reflexivity, antisymmetry, idempotence and transitivity of
leq in a straightforward way.
The reflexivity rule states that leq(X,Y) is
logically true if X=Y. Operationally, this means such a
leq constraint will be replaced by the built-in
constraint true, i.e. it will be removed.
The antisymmetry rule means that if we find the
constraints leq(X,Y) as well as leq(Y,X) in
the current goal, we can replace them by the logically
equivalent built-in constraint X=Y.
The idempotence rule absorbs multiple
occurrences of the same constraint. It is conviniently expressed as a
simpagation rule.
The transitivity rule propagates constraints. It
states that the conjunction leq(X,Y) &&
leq(Y,Z) implies leq(X,Z). Operationally, we
add the constraint leq(X,Z) without removing any constraints.
The last rule states that if the values of X and
Y are known (ground), then the constraint leq(X,Y)
can be replaced by the Java method IntUtil.le(X,Y) that
ensures the right relationship between the integers. Note that the
class IntUtil was declared in the declaration section.
goal. The identifier Circular is the identifier
the goal leq(A,B) && leq(C,A) && leq(B,C).
The example is continued in the next section, where compilation of the constraint handler and execution of the goal are shown.
back
.jchr. Then this file
can be compiled by the JCHR compiler to an executable Java class.
Let the above defined leq handler be saved in a file
called leq.jchr. The compiler is called as follows:
java jchrc leq.jchr
The output is:
jchrc (JCHR to JCHRCore Compiler) Version 0.0.1
./LEQConstraint.java was created!
./INTUTILLE2Method.java was created!
./INTUTILGROUND1Method.java was created!
./leqHandler.java was created!
./leqHandler.java compiled! Class file generated!
For each declared constraint the compiler will generate a new
class with the right number of arguments. For the constraint
leq a class with the name
LEQConstraint.java will be created. The same is done
for each method. Last but not least a file
leqHandler.java is generated. In this file all rules
and all goals are declared in Java syntax. The execution of the
main method of this file will evaluate all defined goals:
java leqHandler
calling goal: leq(A, B), leq(B, C), leq(C, A)
variable table: {}
yes!
variable table: {A<-B, C<-B}
user defined memory:
The variable table consists of variable bindings and the user-defined
memory consists of the remaining user-defined constraints after
simplification and propagation.
The use of the option -t will output an evaluation
trace of the current goal.
java leqHandler -t
calling goal: leq(A, B), leq(C, A), leq(B, C)
variable table: {}
--------------------------------
Variables: {}
User-defined constraints: leq(A, B), leq(C, A), leq(B, C)
--------------------------------
active constraint: leq(A, B)
trying rule: reflexivity @ leq(X, Y) <=> X = Y | true
guard failed
failing constraint: X = Y
constraint type: Equality
failure reason: can't bind a non-local variable in a guard
could not find partner constraints
the rule does not fire
trying rule: antisymmetry @ leq(X, Y), leq(Y, X) <=> X = Y
could not find partner constraints
could not find partner constraints
the rule does not fire
trying rule: idempotence @ leq(X, Y) \ leq(X, Y) <=> true
could not find partner constraints
could not find partner constraints
the rule does not fire
trying rule: transitivity @ leq(X, Y), leq(Y, Z) ==> leq(X, Z)
found partner constraints
rule fires
--------------------------------
Variables: {}
User-defined constraints: leq(A, B), leq(C, A), leq(B, C), leq(A, C)
--------------------------------
.
.
.
The first and third constraints of the goal leq(A,B) && leq(C,A) &&
leq(B,C) cause the transitivity rule to fire and add
leq(A,C). This new constraint together with
leq(C,A) matches the head of the antisymmetry rule. So,
the two constraints are replaced by A=C. The built-in
equality is applied to the rest of the goal, leq(A,B) &&
leq(B,C), resulting in leq(A,B) && leq(B,A). The
antisymmetry rule applies resulting in A=B. The goal
contains no more user-defined constraints, the process stops and the
result of the goal is A=B && B=C.
The basic work, which has to be done, is the creation of an
instances of the classes ConstraintSystem and the
particular constraint handler which is to be used. The handler
class owns a method defineRules, which expects an
instance of the class ConstraintSystem. Calling this method
inserts the rules of the constraint handler into the constraint
system.
Continuing the example of the constraint handler
leqHandler one proceeds as follows:
leqHandler lq = new leqHandler();
ConstraintSystem cs = new ConstraintSystem();
...
lq.defineRules(cs);
...
The next steps are to create and call a goal.
init provided by the class
ConstraintSystem, initializes a constraint system for
evaluation:
cs.init();As an example, we will create the goal
Circular for
the leq handler that we used directly in the handler:
goal Circular {
variable java.lang.integer A, B, C;
leq(A, B) && leq(B, C) && leq(C, A)
}
As in the handler, we will first declare the variables
A, B and C. On the Java level a
variable is a simple Java object of the class
java.lang.Object. But each of these objects need to be
assigned to a Java class, in order to keep the system well typed.
After a logical variable is created, it is registered in the
constraint system with the method addVariable, provided
by the class ConstraintSystem. The last argument of the
method, which names the variable, is optional.
Object A = new Object(); cs.addVariable(A, "java.lang.Integer", "A");
Object B = new Object(); cs.addVariable(B, "java.lang.Integer", "B");
Object C = new Object(); cs.addVariable(C, "java.lang.Integer", "C");
Next, we add the constraints that comprise the conjuncts of the goal
to the constraint system.
The compiler has generated a new name for
the method associated with each constraint, it consists of the name
of the constraint in upper case letters followed by Constraint.
For example, a new constraint instance for the leq constraint
will be created as follows:
new LEQConstraint(new Integer(1), new Integer(2))
If in doubt about the name of a constraint, consult the table in the
compiler generated file ...Handler.java. For example,
in the file leqHandler.java one finds:
// ---------------------------------------------
// created constraints:
//
// leq (LEQConstraint)
This means that class LEQConstraint was generated
for the leq constraint.
The built-in constraint for equality is declared with the
constructor Equality, which is expecting two Java
objects as arguments.
Each constraint of the goal is added to the
constraint system with the method addGoalConstraint:
cs.addGoalConstraint(new LEQConstraint(A, B));
cs.addGoalConstraint(new LEQConstraint(B, C));
cs.addGoalConstraint(new LEQConstraint(C, A));
The evaluation of the goal is
started by calling the method callGoal, provided by the
class ConstraintSystem. It expects an additional
boolean argument: true causes the
evaluator to print the evaluation trace, false
suppresses the trace.
ConstraintSystem provides several methods for
accessing constraints and logical variables.
The keyword csref returns a reference to the current Object of the
class ConstraintSystem (like Java's this). With this reference the
programmer gets access to variables and constraint stores.
| Method | Description |
boolean hasVarValue(Object var) |
returns true, if variable is bound to a value |
void setVarValue(Object var, Object val) |
binds a variable to a value |
Object getVarValue(Object var) |
returns the value, to which the variable is bound |
ObjectContainer getInstances(UDConstraint c) |
returns a collection of constraints, which match
the user-defined constraint c |
ObjectContainer getUsedVariables(Constraint c) |
returns a collection of all variables, which are arguments
of the constraint c |
ObjectContainer getVariableObservers(Object var) |
returns a collection of constraints which have the
variable var as an argument |
String getVariableName(Object var) |
returns the name of the variable object |
Object getVariableObject(String v) |
returns the variable object, with the given name v |
back