Specifications using multiple-conclusion logic programs

Multiset rewriting has proved to be a useful presentation of process synchronization [1, 2, 3, 6]. Since sequent calculus presentations of logics that do not use the structural rules of contractions and weakening are based on using multisets of formulas as left and right contexts, it is natural to identify processes with formulas, multisets with sequent contexts, and multiset rewriting as an inference rule. Given earlier work on using sequent calculus to describe logic programming as goal-directed search for proofs [8], it is most natural to use right-hand contexts of sequents to represent multisets of processes. This choice requires the identification of the multiset constructor and the empty multiset with the multiplicative disjunction and false (the (Formula presented) and ⊥ of linear logic [4]), and backchaining with a single step of multiset rewriting. While the logic programming language λProlog [10] and its linear logic refinement Lolli [5] contain rich sources of abstraction (such as modular programming, abstract data types, and higher-order programming), they contain no primitives for specifying concurrency, communications, or synchronization. If multiset rewriting is added to Lolli via the logical connectives (Formula presented) and ⊥, the result is a language that contains primitives for both abstraction and concurrency. Surprisingly, the resulting logic, called Forum [7], is a presentation of all of linear logic in the sense that all of the connectives of linear logic can be defined via logical equivalences using only the connectives of Forum. Thus the rich meta-theory of linear logic, for example, the de Morgan dualities and cut-elimination, can be applied to the analysis of Forum programs. Several examples to illustrate the expressiveness of this presentation of linear logic will be given. These examples will involve a specification of sequent calculi for object-level logics, a specification of the π-calculus [9], and a specification of a functional programming language that contains side-effects and concurrency operators. In each of these examples, we shall argue that the specification is perspicuous and modular and that the meta-theory of linear logic can be used to derive properties of the specification.