(To appear in Theory and Practice of Logic Programming (TPLP)) We introduce a systematic, concurrent execution scheme for Constraint Handling Rules (CHR) based on a previously proposed sequential goal-based CHR semantics. We establish strong correspondence results to the abstract CHR semantics, thus guaranteeing that any answer in the concurrent, goal-based CHR semantics is reproducible in the abstract CHR semantics. Our work provides the foundation to obtain efficient, parallel CHR execution schemes.
Parallel execution models of forward chaining production rule based languages (e.g. OPS5 @cite_18 ) have been widely studied in the context of production rule systems. A production rule system is defined by a set of multi-headed production rules (analogous to CHR rules) and a set of assertions (analogous to the CHR store). Production rule systems are richer than the CHR language, consisting of user definable execution strategies and negated rule heads. This makes parallelizing production rule execution extremely difficult, because rule application is not monotonic (rules may not be applied in a larger context). As such, many previous works in parallel production rule systems focuses on efficient means of maintaining correctness of parallel rule execution (e.g. data dependency analysis @cite_7 , sequential to parallel program transformation @cite_22 ), with respect to such user specified execution strategies. These works can be classified under two approaches, namely synchronous and asynchronous parallel production systems.
@cite_18 @cite_22 @cite_7
1553764325 2085596514
It has been claimed that production systems have several advantages over other representational schemes. These include the potential for general self-augmentation (i.e., learning of new behavior) and the ability to function in complex environments. The production system language, OPS, was implemented to test these claims. In this paper we explore some of the issues that bear on the design of production system languages and try to show the adequacy of OPS for its intended purpose. Conflict resolution is a form of global control used in production systems to achieve an efficient sequential execution of a rule-based program. This type of control is not used in parallel production system models[6, 13]. Instead, only those programs are executed which make no assumptions regarding conflict resolution. Therefore, the initial sequential rule-based programs are either executed in parallel without their conflict resolution strategy, which normally results in incorrect behavior, or the programs are transformed in an ad hoc manner to execute on a particular parallel production system model. As a result, these programs do not exhibit the parallelism hoped for [10, 13]. We believe that a second reason behind the lack of parallelism is that no formal methods of verifying the correctness of rule-based programs are utilized. Correctness is especially important when conflict resolution is no longer utilized, because it necessary to transform sequential rule-based programs into equivalent programs without conflict resolution. Also, the parallel execution of a rule-based program is more complex and demands these formal methods even more than its sequential counterpart. We are concerned with designing and developing correct rule-based programs for parallel execution. In this paper, we show the difficulty in transforming a simple sequential rule-based program to a new version of the program with no conflict resolution. Also, we show that the use of a new programming paradigm and language may result in more efficient programs which are provably correct, and can be executed in parallel.