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.
Common linear logic programming languages such as LO @cite_3 , Lolli @cite_9 , LinLog @cite_17 , and Lygon @cite_7 rely on generalizations of backward-chaining backtracking resolution of horn clauses.
@cite_9 @cite_7 @cite_3 @cite_17
1963779317 2163058466 1492862327 1502855507
Lolli is a logic programming language based on the asynchronous propositions of intuitionistic linear logic. It uses a backward chaining, backtracking operational semantics. In this paper we extend Lolli with the remaining connectives of intuitionistic linear logic restricted to occur inside a monad, an idea taken from the concurrent logical framework (CLF). The resulting language, called LolliMon, has a natural forward chaining, committed choice operational semantics inside the monad, while retaining Lolli's semantics outside the monad. LolliMon thereby cleanly integrates both concurrency and saturation with logic programming search. We illustrate its expressive power through several examples including an implementation of the pi-calculus, a call-by-need lambda-calculus, and several saturating algorithms presented in logical form. A set of Horn clauses, augmented with a ‘guard’ mechanism, is shown to be a simple and yet powerful parallel logic programming language. For many given systems of logic, it is possible to identify, via systematic proof-theoretic analyses, a fragment which can be used as a basis for a logic programming language. Such analyses have been applied to linear logic, a logic of resource-consumption, leading to the definition of the linear logic programming language Lygon. It appears that (the basis of) Lygon can be considered to be the largest possible first-order linear logic programming language derivable in this way. In this paper, we describe the design and application of Lygon. We give examples which illustrate the advantages of resource-oriented logic programming languages. 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.