Bunched logic is a variety of substructural logic proposed by Peter O'Hearn and David Pym. Bunched logic provides primitives for reasoning about resource composition, which aid in the compositional analysis of computer and other systems. It has category-theoretic and truth-functional semantics which can be understood in terms of an abstract concept of resource, and a proof theory in which the contexts Γ in an entailment judgements Γ |- A are tree-like structures (bunches) rather than lists or (multi)sets as in most proof calculi. Bunched logic has an associated type theory, and its first application was in providing a way to control the aliasing and other forms of interference in imperative programs The logic has seen further applications in program verification, where it is the basis of the assertion language of separation logic, and in systems modelling, where it provides a way to decompose the resources used by components of a system.
Contents
Foundations
The deduction theorem of traditional logic relates conjunction and implication
Bunched logic has two versions of the deduction theorem at once:
Truth Functional Semantics (Resource Semantics)
The easiest way to understand these formulae is in terms of its truth-functional semantics. In this semantics a formula is true or false with respect to given resources.
The foundation for this reading of formulae was provided by a forcing semantics
where
This semantics of bunched logic draws on prior work in Relevant Logic (especially the operational semantics of Routley-Meyer), but differs from it my not requiring
Categorical Semantics (Doubly Closed Categories)
The double version of the deduction theorem of bunched logic has a corresponding category theoretic structure. Proofs in intuitionistic logic can be interpreted in cartesian closed categories, that is, categories with finite products satisfying the (natural in A and C) adjunction correspondence relating hom sets:
Bunched logic can be interpreted in categories possessing two such structures
A host of categorial models can be given using Day's tensor product construction. Additionally, implicational fragment of bunched logic has been given a games semantics.
Algebraic Semantics
The algebraic semantics of bunched logic is a special case of its categorical semantics, but is simple to state and can be more approachable.
The boolean version of bunched logic has models as follows.
Proof Theory and Type Theory (Bunches)
The proof theory of bunched logic differs from usual proof calculi in having a tree-like context of hypotheses instead of a flat list-like structure. In its sequent-based proof theories, the context
The difference between the two composition rules comes from additional rules that apply to them.
The structural rules and other operations on bunches are often applied deep within a tree-context, and not only at the top level: it is thus in a sense a calculus of deep inference.
Corresponding to bunched logic is a type theory having two kinds of function type. Following the Curry–Howard correspondence, introduction rules for implications correspond to introduction rules for function types.
Here, there are two distinct binders,
The proof theory of bunched logic has an historical dept to the use of bunches in Relevance logic. But the bunched structure can in a sense be derived from the categorical and algebraic semantics: to formulate an introduction rule for
Brotherston has done further significant work on a unified proof theory for bunched logic and variants, employing Belnap's notion of display logic.
Galmiche, Méry, and Pym have provided a comprehensive treatment of bunched logic, including completeness and other meta-theory, based on labelled tableaux.
Decision Problems
TODO
Modal Extensions
TODO
Interference Control
In perhaps the first use of substructural type theory to control resources, John C. Reynolds showed how to use an affine type theory to control aliasing and other forms of interference in Algol-like programming languages. O'Hearn used bunched type theory to extend Reynolds system by allowing interference and non-interference to be more flexibly mixed . This resolved open problems concerning recursion and jumps in Reynolds's system.
Separation Logic
Separation logic is an extension of Hoare logic which facilitates reasoning about mutable data structures that use pointers. Following Hoare logic the formulae of separation logic are of the form
It is the undefinedness of the composition on overlapping heaps that models the separation idea. This is a model of the boolean variant of bunched logic.
Separation logic was used originally to prove sequential programs, but then was extended to concurrency using a proof rule
that divides the storage accessed by parallel threads.
Later, the greater generality of the resource semantics was utilized: an abstract version of separation logic works for Hoare triples where the preconditions and oostconditions are formulae interpreted over an arbitrary partial commutative monoid instead of a particular heap model. By suitable choice of commutative monoid, it was surprisingly found that the proofs rules of abstract versions of concurrent separation logic could be used to reason about interfering concurrent processes, for example by encoding rely-guarantee and trace-based reasoning.
Separation logic is the basis of a number of tools for automatic and semi-automatic reasoning about programs, and is used in the Infer program analyzer currently deployed at Facebook.
Resources and Processes
Bunched logic has been used in connection with the (synchronous) resource-process calculus SCRP in order to give a (modal) logic which characterizes, in the sense of Hennessey-Milner, the compositional structure of concurrent systems.
SCRP is notable for interpreting
TODO
The system SCRP is based directly on bunched logic's resource semantics; that is, on ordered monoids of resource elements. While direct and intuitively appealing, this choice leads to a specific technical problem: the Hennessy-Milner completeness theorem holds only for fragments of the modal logic that exclude the multiplicative implication and multiplicative modalities. This problem is solved by basing resource-process calculus on a resource semantics in which resource elements are combined using two combinators, one corresponding to concurrent composition and one corresponding to choice.
Systems Modelling
TODO
Spatial Logics
Cardelli, Caires, Gordon and others have investigated a series of logics of process calculi, where a conjunction is interpreted in terms of parallel composition. [References, to add] Unlike the work of Pym et al. in SCRP, they do not distinguish between parallel composition of systems and composition of resources accessed by the systems. Their logics are based on instances of the resource semantics which give rise to models of the boolean variant of bunched logic. Although these logics give rise to instances of boolean bunched logic, they appear to have been arrived at independently, and in any case have significant additional structure in the way of modalities and binders. Related logics have been proposed as well for modelling XML data.