Constraint Logic Programming - Constraint Handling Rules

Constraint Handling Rules

Constraint handling rules were initially defined as a stand-alone formalism for specifying constraint solvers, and were later embedded in logic programming. There are two kinds of constraint handling rules. The rules of the first kind specify that, under a given condition, a set of constraints is equivalent to another one. The rules of the second kind specify that, under a given condition, a set of constraints implies another one. In a constraint logic programming language supporting constraint handling rules, a programmer can use these rules to specify possible rewritings of the constraint store and possible additions of constraints to it. The following are example rules:

A(X) <=> B(X) | C(X) A(X) ==> B(X) | C(X)

The first rule tells that, if B(X) is entailed by the store, the constraint A(X) can be rewritten as C(X). As an example, N*X>0 can be rewritten as X>0 if the store implies that N>0. The symbol <=> resembles equivalence in logic, and tells that the first constraint is equivalent to the latter. In practice, this implies that the first constraint can be replaced with the latter.

The second rule instead specifies that the latter constraint is a consequence of the first, if the constraint in the middle is entailed by the constraint store. As a result, if A(X) is in the constraint store and B(X) is entailed by the constraint store, then C(X) can be added to the store. Differently from the case of equivalence, this is an addition and not a replacement: the new constraint is added but the old one remains.

Equivalence allows for simplifying the constraint store by replacing some constraints with simpler ones; in particular, if the third constraint in an equivalence rule is true, and the second constraint is entailed, the first constraint is removed from the constraint store. Inference allows for the addition of new constraints, which may lead to proving inconsistency of the constraint store, and may generally reduce the amount of search needed to establish its satisfiability.

Logic programming clauses in conjunction with constraint handling rules can be used to specify a method for establishing the satisfiability of the constraint store. Different clauses are used to implement the different choices of the method; the constraint handling rules are used for rewriting the constraint store during execution. As an example, one can implement backtracking with unit propagation this way. Let holds(L) represents a propositional clause, in which the literals in the list L are in the same order as they are evaluated. The algorithm can be implemented using clauses for the choice of assigning a literal to true or false, and constraint handling rules to specify propagation. These rules specify that holds can be removed if l=true follows from the store, and it can be rewritten as holds(L) if l=false follows from the store. Similarly, holds can be replaced by l=true. In this example, the choice of value for a variable is implemented using clauses of logic programming; however, it can be encoded in constraint handling rules using an extension called disjunctive constraint handling rules or CHR∨.

Read more about this topic:  Constraint Logic Programming

Famous quotes containing the words constraint, handling and/or rules:

    In America a woman loses her independence for ever in the bonds of matrimony. While there is less constraint on girls there than anywhere else, a wife submits to stricter obligations. For the former, her father’s house is a home of freedom and pleasure; for the latter, her husband’s is almost a cloister.
    Alexis de Tocqueville (1805–1859)

    Many more children observe attitudes, values and ways different from or in conflict with those of their families, social networks, and institutions. Yet today’s young people are no more mature or capable of handling the increased conflicting and often stimulating information they receive than were young people of the past, who received the information and had more adult control of and advice about the information they did receive.
    James P. Comer (20th century)

    Unfortunately, we cannot rely solely on employers seeing that it is in their self-interest to change the workplace. Since the benefits of family-friendly policies are long-term, they may not be immediately visible or quantifiable; companies tend to look for success in the bottom line. On a deeper level, we are asking those in power to change the rules by which they themselves succeeded and with which they identify.
    Anne C. Weisberg (20th century)