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.
The earliest approach at defining a linear-logic semantics for a committed-choice programming language that we are aware of has been proposed in @cite_16 . The corresponding language is indeed a fragment of pure CHR without multiple heads and with substantial restrictions on the use of built-in constraints.
@cite_16
1534027338 1502855507 2152131859 58578906
The paper deals with the relationship of committed-choice logic programming languages and their proof-theoretic semantics based on linear logic. Fragments of linear logic are used in order to express various aspects of guarded clause concurrent programming and behavior of the system. The outlined translation comprises structural properties of concurrent computations, providing a sound and complete model wrt. to the interleaving operational semantics based on transformation systems. In the presence of variables, just asynchronous properties are captured without resorting to special proof-generating strategies, so the model is only correct for deadlock-free programs. 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. Logic programming with the stable model semantics is put forward as a novel constraint programming paradigm. This paradigm is interesting because it bring advantages of logic programming based knowledge representation techniques to constraint programming and because implementation methods for the stable model semantics for ground (variabledfree) programs have advanced significantly in recent years. For a program with variables these methods need a grounding procedure for generating a variabledfree program. As a practical approach to handling the grounding problem a subclass of logic programs, domain restricted programs, is proposed. This subclass enables efficient grounding procedures and serves as a basis for integrating builtdin predicates and functions often needed in applications. It is shown that the novel paradigm embeds classical logical satisfiability and standard (finite domain) constraint satisfaction problems but seems to provide a more expressive framework from a knowledge representation point of view. The first steps towards a programming methodology for the new paradigm are taken by presenting solutions to standard constraint satisfaction problems, combinatorial graph problems and planning problems. An efficient implementation of the paradigm based on domain restricted programs has been developed. This is an extension of a previous implementation of the stable model semantics, the Smodels system, and is publicly available. It contains, e.g., builtdin integer arithmetic integrated to stable model computation. The implementation is described briefly and some test results illustrating the current level of performance are reported. Ordered Choice Logic Programming (OCLP) allows for preference-based decision-making with multiple alternatives and without the burden of any form of negation. This complete absence of negation does not weaken the language as both forms (classical and as-failure) can be intuitively simulated in the language. The semantics of the language is based on the preference between alternatives, yielding both a skeptical and a credulous approach. In this paper we discuss the theoretical basis for the implementation of an OCLP front-end for answer set solvers that can compute both semantics in an efficient manner. Both the basic algorithm and the proposed optimizations can be used in general and are not tailored towards any particular answer set solver.