Recent from talks
Constraint Handling Rules
Knowledge base stats:
Talk channels stats:
Members stats:
Constraint Handling Rules
Constraint Handling Rules (CHR) is a declarative, rule-based programming language, introduced in 1991 by Thom Frühwirth at the time with European Computer-Industry Research Centre (ECRC) in Munich, Germany. Originally intended for constraint programming, CHR finds applications in grammar induction, type systems, abductive reasoning, multi-agent systems, natural language processing, compilation, scheduling, spatial-temporal reasoning, testing, and verification.
A CHR program, sometimes called a constraint handler, is a set of rules that maintain a constraint store, a multi-set of logical formulas. Execution of rules may add or remove formulas from the store, thus changing the state of the program. The order in which rules "fire" on a given constraint store is non-deterministic, according to its abstract semantics and deterministic (top-down rule application), according to its refined semantics.
Although CHR is Turing complete, it is not commonly used as a programming language in its own right. Rather, it is used to extend a host language with constraints. Prolog is by far the most popular host language and CHR is included in several Prolog implementations, including SICStus and SWI-Prolog, although CHR implementations also exist for Haskell, Java, C, SQL, and JavaScript. In contrast to Prolog, CHR rules are multi-headed and are executed in a committed-choice manner using a forward chaining algorithm.
The concrete syntax of CHR programs depends on the host language, and in fact programs embed statements in the host language that are executed to handle some rules. The host language supplies a data structure for representing terms, including logical variables. Terms represent constraints, which can be thought of as "facts" about the program's problem domain. Traditionally, Prolog is used as the host language, so its data structures and variables are used. The rest of this section uses a neutral, mathematical notation that is common in the CHR literature.
A CHR program, then, consists of rules that manipulate a multi-set of these terms, called the constraint store. Rules come in three types:
Since simpagation rules subsume simplification and propagation, all CHR rules follow the format
where each of is a conjunction of constraints: and contain CHR constraints, while the guards are built-in. Only one of needs to be non-empty.
The host language must also define built-in constraints over terms. The guards in rules are built-in constraints, so they effectively execute host language code. The built-in constraint theory must include at least true (the constraint that always holds), fail (the constraint that never holds, and is used to signal failure) and equality of terms, i.e., unification. When the host language does not support these features, they must be implemented along with CHR.
Hub AI
Constraint Handling Rules AI simulator
(@Constraint Handling Rules_simulator)
Constraint Handling Rules
Constraint Handling Rules (CHR) is a declarative, rule-based programming language, introduced in 1991 by Thom Frühwirth at the time with European Computer-Industry Research Centre (ECRC) in Munich, Germany. Originally intended for constraint programming, CHR finds applications in grammar induction, type systems, abductive reasoning, multi-agent systems, natural language processing, compilation, scheduling, spatial-temporal reasoning, testing, and verification.
A CHR program, sometimes called a constraint handler, is a set of rules that maintain a constraint store, a multi-set of logical formulas. Execution of rules may add or remove formulas from the store, thus changing the state of the program. The order in which rules "fire" on a given constraint store is non-deterministic, according to its abstract semantics and deterministic (top-down rule application), according to its refined semantics.
Although CHR is Turing complete, it is not commonly used as a programming language in its own right. Rather, it is used to extend a host language with constraints. Prolog is by far the most popular host language and CHR is included in several Prolog implementations, including SICStus and SWI-Prolog, although CHR implementations also exist for Haskell, Java, C, SQL, and JavaScript. In contrast to Prolog, CHR rules are multi-headed and are executed in a committed-choice manner using a forward chaining algorithm.
The concrete syntax of CHR programs depends on the host language, and in fact programs embed statements in the host language that are executed to handle some rules. The host language supplies a data structure for representing terms, including logical variables. Terms represent constraints, which can be thought of as "facts" about the program's problem domain. Traditionally, Prolog is used as the host language, so its data structures and variables are used. The rest of this section uses a neutral, mathematical notation that is common in the CHR literature.
A CHR program, then, consists of rules that manipulate a multi-set of these terms, called the constraint store. Rules come in three types:
Since simpagation rules subsume simplification and propagation, all CHR rules follow the format
where each of is a conjunction of constraints: and contain CHR constraints, while the guards are built-in. Only one of needs to be non-empty.
The host language must also define built-in constraints over terms. The guards in rules are built-in constraints, so they effectively execute host language code. The built-in constraint theory must include at least true (the constraint that always holds), fail (the constraint that never holds, and is used to signal failure) and equality of terms, i.e., unification. When the host language does not support these features, they must be implemented along with CHR.