__Simplification Rules__

In this tutorial, we will discuss the first form of rules in CHR which is Simplification. As we said before, CHR offers a rule based

programming style. Each rule in CHR has a Head which is a set of posted constraints, a Guard which is a set of conditions,

and a Body which is a set of constraints to be posted. We say that a rule can fire if all conditions in the guard can be satisfied

and if the posted constraints have the same type and number of constraints as in the head. When a rule fires, the constraints

in the body are posted.

Simplification rules have the following format:

If a simplification rule fires, then constraints in the head are discarded, and the constraints in the body are posted.

To understand how a simplification rule functions, let us start with a simple example. We are to write a

program that sums up all numbers in a list. Each number can be represented by a

Assuming we have the list of numbers [-2, 4, 1, 8], we can represent this problem by posting the constraints as follows:

number(-2), number(4), number(-1), number(8).

We need to implement a rule that sums all the numbers in the posted

each two posted numbers are summed up, and a new

will use a simplification rule, the two old constraints will be discarded. The rule can be implemented as in the listing below.

In order to use CHR, a

that every defined constraint has to be declared at the beginning of the program by using the

directive, specifying the name and the arity of the constraint.

programming style. Each rule in CHR has a Head which is a set of posted constraints, a Guard which is a set of conditions,

and a Body which is a set of constraints to be posted. We say that a rule can fire if all conditions in the guard can be satisfied

and if the posted constraints have the same type and number of constraints as in the head. When a rule fires, the constraints

in the body are posted.

Simplification rules have the following format:

**Head <=> Guard | Body.**If a simplification rule fires, then constraints in the head are discarded, and the constraints in the body are posted.

To understand how a simplification rule functions, let us start with a simple example. We are to write a

program that sums up all numbers in a list. Each number can be represented by a

*number/1*constraint.Assuming we have the list of numbers [-2, 4, 1, 8], we can represent this problem by posting the constraints as follows:

number(-2), number(4), number(-1), number(8).

We need to implement a rule that sums all the numbers in the posted

*number/1*constraints. The rule can work as follows,each two posted numbers are summed up, and a new

*number/1*constraint is posted with the new number. Since wewill use a simplification rule, the two old constraints will be discarded. The rule can be implemented as in the listing below.

In order to use CHR, a

*”:- use module(library(chr))”*directive has to be added at the beginning of the file. Please notethat every defined constraint has to be declared at the beginning of the program by using the

*”:- chr constraint”*directive, specifying the name and the arity of the constraint.

:- use_module ( library ( chr )). :- chr_constraint number /1. number (X), number (Y) <=> Z is X+Y | number (Z).

Depending on the posted constraints, CHR will try to find the rules that can fire (i.e. rules that have satisfiable guards).

Since the constraints number(-2),number(4) satisfy the head and the guard of the rule, the rule fires and posts a

new constraint number(2). The rule fires again with the constraints number(2),number(-1), and a new constraint is

posted number(1). Finally, number(1) and number(8) sum up to produce the resultant constraint number(9). Now,

since there exists only one

our final solution. The execution steps of the posted constraints is illustrated in the figure below.

Since the constraints number(-2),number(4) satisfy the head and the guard of the rule, the rule fires and posts a

new constraint number(2). The rule fires again with the constraints number(2),number(-1), and a new constraint is

posted number(1). Finally, number(1) and number(8) sum up to produce the resultant constraint number(9). Now,

since there exists only one

*number/1*constraint, the rule stops firing (since it needs two), and CHR terminates withour final solution. The execution steps of the posted constraints is illustrated in the figure below.