Constraint Handling Rules (CHR) is a declarative committed-choice programming language with a strong relationship to linear logic. Its generalization CHR with Disjunction (CHRv) is a multi-paradigm declarative programming language that allows the embedding of horn programs. We analyse the assets and the limitations of the classical declarative semantics of CHR before we motivate and develop a linear-logic declarative semantics for CHR and CHRv. We show how to apply the linear-logic semantics to decide program properties and to prove operational equivalence of CHRv programs across the boundaries of language paradigms.
More recently, proposed the linear logic-based committed-choice programming language @cite_4 . While the language itself corresponds to a segment of pure CHR, the aim of the work is to define a cost semantics for algorithms that feature non-deteministic choices.
@cite_4
1502855507
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.