We observe that the various formulations of the operational semantics of Constraint Handling Rules proposed over the years fall into a spectrum ranging from the analytical to the pragmatic. While existing analytical formulations facilitate program analysis and formal proofs of program properties, they cannot be implemented as is. We propose a novel operational semantics ω!, which has a strong analytical foundation, while featuring a terminating execution model. We prove its soundness and completeness with respect to existing analytical formulations and we provide an implementation in the form of a source-to-source transformation to CHR with rule priorities.
@cite_21: Bottom-up logic programming can be used to declaratively specify many algorithms in a succinct and natural way, and McAllester and Ganzinger have shown that it is possible to define a cost semantics that enables reasoning about the running time of algorithms written as inference rules. Previous work with the programming language Lollimon demonstrates the expressive power of logic programming with linear logic in describing algorithms that have imperative elements or that must repeatedly make mutually exclusive choices. In this paper, we identify a bottom-up logic programming language based on linear logic that is amenable to efficient execution and describe a novel cost semantics that can be used for complexity analysis of algorithms expressed in linear logic.
Our proposed operational semantics @math is related to LLA @cite_21 , but displays significant differences: Firstly, the notion of a constraint theory with built-in constraints is absent in LLA. Secondly, LLA rules are restricted such that persistent propositions cannot be derived multiple times, whereas @math makes no such restriction and solves this problem via the irreflexive transition system. Thirdly, LLA requires a strict separation of propositions into linear and persistent ones. In @math a CHR constraint can occur in the linear store, in the persistent store, or both.