Bunched logic

Bunched logic ^[1] 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 judgement Γ ⊢ 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. ^[2] The logic has seen further applications in program verification, where it is the basis of the assertion language of separation logic, ^[3] and in systems modelling, where it provides a way to decompose the resources used by components of a system. ^{[4] [5] [6]}

Foundations

The deduction theorem of classical logic relates conjunction and implication:

${\displaystyle A\wedge B\vdash C\quad {\mbox{iff}}\quad A\vdash B\Rightarrow C}$

Bunched logic has two versions of the deduction theorem:

${\displaystyle A*B\vdash C\quad {\mbox{iff}}\quad A\vdash B{-\!\!*}C\qquad {\mbox{and also}}\qquad A\wedge B\vdash C\quad {\mbox{iff}}\quad A\vdash B\Rightarrow C}$

${\displaystyle A*B}$ and ${\displaystyle B{-\!\!*}C}$ are forms of conjunction and implication that take resources into account (explained below). In addition to these connectives bunched logic has a formula, sometimes written I or emp, which is the unit of *. In the original version of bunched logic ${\displaystyle \wedge }$ and ${\displaystyle \Rightarrow }$ were the connectives from intuitionistic logic, while a boolean variant takes ${\displaystyle \wedge }$ and ${\displaystyle \Rightarrow }$ (and ${\displaystyle \neg }$) as from traditional boolean logic. Thus, bunched logic is compatible with constructive principles, but is in no way dependent on them.

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. ${\displaystyle A*B}$ asserts that the resource at hand can be decomposed into resources that satisfy ${\displaystyle A}$ and ${\displaystyle B}$. ${\displaystyle B{-\!\!*}C}$ says that if we compose the resource at hand with additional resource that satisfies ${\displaystyle B}$, then the combined resource satisfies ${\displaystyle C}$. ${\displaystyle \wedge }$ and ${\displaystyle \Rightarrow }$ have their familiar meanings.

The foundation for this reading of formulae was provided by a forcing semantics ${\displaystyle r\models A}$ advanced by Pym, where the forcing relation means 'A holds of resource r'. The semantics is analogous to Kripke's semantics of intuitionistic or modal logic, but where the elements of the model are regarded as resources that can be composed and decomposed, rather than as possible worlds that are accessible from one another. For example, the forcing semantics for the conjunction is of the form

${\displaystyle r\models A*B\quad {\mbox{iff}}\quad \exists r_{A}r_{B}.\,r_{A}\models A,\,r_{B}\models B,\,{\mbox{and}}\,r_{A}\bullet r_{B}\leq r}$

where ${\displaystyle r_{A}\bullet r_{B}}$ is a way of combining resources and ${\displaystyle \leq }$ is a relation of approximation.

This semantics of bunched logic draws on prior work in relevance logic (especially the operational semantics of Routley–Meyer), but differs from it by not requiring ${\displaystyle r\bullet r\leq r}$ and by accepting the semantics of standard intuitionistic or classical versions of ${\displaystyle \wedge }$ and ${\displaystyle \Rightarrow }$. The property ${\displaystyle r\bullet r\leq r}$ is justified when thinking about relevance but denied by considerations of resource; having two copies of a resource is not the same as having one, and in some models (e.g. heap models) ${\displaystyle r\bullet r}$ might not even be defined. The standard semantics of ${\displaystyle \Rightarrow }$ (or of negation) is often rejected by relevantists in their bid to escape the `paradoxes of material implication', which are not a problem from the perspective of modelling resources and so not rejected by bunched logic. The semantics is also related to the 'phase semantics' of linear logic, but again is differentiated by accepting the standard (even boolean) semantics of ${\displaystyle \wedge }$ and ${\displaystyle \Rightarrow }$, which in linear logic is rejected in a bid to be constructive. These considerations are discussed in detail in an article on resource semantics by Pym, O'Hearn and Yang. ^[7]

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:

${\displaystyle Hom(A\wedge B,C)\quad {\mbox{is isomorphic to}}\quad Hom(A,B\Rightarrow C)}$

Bunched logic can be interpreted in categories possessing two such structures

a categorical model of bunched logic is a single category possessing two closed structures, one symmetric monoidal closed the other cartesian closed.

A host of categorial models can be given using Day's tensor product construction. ^[8] Additionally, the implicational fragment of bunched logic has been given a game semantics. ^[9]

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.

An algebraic model of bunched logic is a poset that is a Heyting algebra and that carries an additional commutative residuated lattice structure (for the same lattice as the Heyting algebra): that is, an ordered commutative monoid with an associated implication satisfying ${\displaystyle A*B\leq C\quad {\mbox{iff}}\quad A\leq B{-\!\!*}C}$.

The boolean version of bunched logic has models as follows.

An algebraic model of boolean bunched logic is a poset that is a Boolean algebra and that carries an additional residuated commutative monoid structure.

Proof theory and type theory (bunches)

The proof calculus of bunched logic differs from usual sequent calculi in having a tree-like context of hypotheses instead of a flat list-like structure. In its sequent-based proof theories, the context ${\displaystyle \Delta }$ in an entailment judgement ${\displaystyle \Delta \vdash A}$ is a finite rooted tree whose leaves are propositions and whose internal nodes are labelled with modes of composition corresponding to the two conjunctions. The two combining operators, comma and semicolon, are used (for instance) in the introduction rules for the two implications.

${\displaystyle {\frac {\Gamma ,A\vdash B}{\Gamma \vdash A{-\!\!*}B}}\qquad \qquad {\frac {\Gamma ;A\vdash B}{\Gamma \vdash A{\Rightarrow }B}}}$

The difference between the two composition rules comes from additional rules that apply to them.

• Multiplicative composition ${\displaystyle \Delta ,\Gamma }$ denies the structural rules of weakening and contraction.
• Additive composition ${\displaystyle \Delta$ ;\Gamma } admits weakening and contraction of entire bunches.

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.

${\displaystyle {\frac {\Gamma ,x:A\vdash M:B}{\Gamma \vdash \lambda x.M:A{-\!\!*}B}}\qquad \qquad {\frac {\Gamma ;x:A\vdash M:B}{\Gamma \vdash \alpha x.M:A{\Rightarrow }B}}}$

Here, there are two distinct binders, ${\displaystyle \lambda }$ and ${\displaystyle \alpha }$, one for each kind of function type.

The proof theory of bunched logic has an historical debt to the use of bunches in relevance logic. ^[10] But the bunched structure can in a sense be derived from the categorical and algebraic semantics: to formulate an introduction rule for ${\displaystyle {-\!\!*}}$ we should mimick ${\displaystyle *}$ on the left in sequents, and to introduce ${\displaystyle \Rightarrow }$ we should mimick ${\displaystyle \wedge }$. This consideration leads to the use of two combining operators.

James Brotherston has done further significant work on a unified proof theory for bunched logic and variants, ^[11] employing Belnap's notion of display logic. ^[12]

Galmiche, Méry, and Pym have provided a comprehensive treatment of bunched logic, including completeness and other meta-theory, based on labelled tableaux. ^[13]

Applications

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. ^[14] O'Hearn used bunched type theory to extend Reynolds' system by allowing interference and non-interference to be more flexibly mixed. ^[2] This resolved open problems concerning recursion and jumps in Reynolds' system.

Separation logic

Separation logic is an extension of Hoare logic that facilitates reasoning about mutable data structures that use pointers. Following Hoare logic the formulae of separation logic are of the form ${\displaystyle \{Pre\}program\{Post\}}$, but the preconditions and postconditions are formulae interpreted in a model of bunched logic. The original version of the logic was based on models as follows:

• ${\displaystyle Heaps=L\rightharpoonup _{f}V\qquad }$ (finite partial functions from locations to values)
• ${\displaystyle h_{0}\bullet h_{1}=}$ union of heaps with disjoint domains, undefined when domains overlap.

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 properties of sequential programs, but then was extended to concurrency using a proof rule

${\displaystyle {\frac {\{P_{1}\}C_{1}\{Q_{1}\}\quad \{P_{2}\}C_{2}\{Q_{2}\}}{\{P_{1}*P_{2}\}C_{1}\parallel C_{2}\{Q_{1}*Q_{2}\}}}}$

that divides the storage accessed by parallel threads. ^[15]

Later, the greater generality of the resource semantics was utilized: an abstract version of separation logic works for Hoare triples where the preconditions and postconditions are formulae interpreted over an arbitrary partial commutative monoid instead of a particular heap model. ^[16] 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. ^{[17] [18]}

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. ^[19]

Resources and processes

Bunched logic has been used in connection with the (synchronous) resource-process calculus SCRP ^{[4] [5] [6]} in order to give a (modal) logic that characterizes, in the sense of Hennessy–Milner, the compositional structure of concurrent systems.

SCRP is notable for interpreting ${\displaystyle A*B}$ in terms of both parallel composition of systems and composition of their associated resources. The semantic clause of SCRP's process logic that corresponds to separation logic's rule for concurrency asserts that a formula ${\displaystyle A*B}$ is true in resource-process state ${\displaystyle R}$, ${\displaystyle E}$ just in case there are decompositions of the resource ${\displaystyle R=S\bullet T}$ and process ${\displaystyle E}$ ~ ${\displaystyle F\times G}$, where ~ denotes bisimulation, such that ${\displaystyle A}$ is true in the resource-process state ${\displaystyle S}$, ${\displaystyle F}$ and ${\displaystyle B}$ is true in the resource-process state ${\displaystyle T}$, ${\displaystyle G}$; that is ${\displaystyle R,E\models A}$ iff ${\displaystyle S,F\models A}$ and ${\displaystyle T,G\models B}$.

The system SCRP ^{[4] [5] [6]} 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. ^[20]

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.^{[ citation needed ]} 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 that 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.

See also

• Separation logic
• Relevance logic
• Linear logic

References

1. O'Hearn, Peter; Pym, David (1999). "The Logic of Bunched Implications" (PDF). Bulletin of Symbolic Logic . 5 (2): 215–244. CiteSeerX   10.1.1.27.4742 . doi:10.2307/421090. JSTOR   421090. S2CID   2948552.
2. O'Hearn, Peter (2003). "On Bunched Typing" (PDF). Journal of Functional Programming . 13 (4): 747–796. doi:10.1017/S0956796802004495.
3. Ishtiaq, Samin; O'Hearn, Peter (2001). "BI as an assertion language for mutable data structures" (PDF). POPL. 28th (3): 14–26. CiteSeerX   10.1.1.11.4925 . doi:10.1145/373243.375719.
4. Pym, David; Tofts, Chris (2006). "A Calculus and logic of resources and processes" (PDF). Formal Aspects of Computing. 8 (4): 495–517. doi:10.1007/s00165-006-0018-z. S2CID   16623194.
5. Collinson, Matthew; Pym, David (2009). "Algebra and Logic for Resource-based Systems Modelling". Mathematical Structures in Computer Science. 19 (5): 959–1027. CiteSeerX   10.1.1.153.3899 . doi:10.1017/S0960129509990077. S2CID   14228156.
6. Collinson, Matthew; Monahan, Brian; Pym, David (2012). A Discipline of Mathematical Systems Modelling. London: College Publications. ISBN   978-1-904987-50-5.
7. Pym, David; O'Hearn, Peter; Yang, Hongseok (2004). "Possible worlds and resources: The semantics of BI". Theoretical Computer Science . 315 (1): 257–305. doi: 10.1016/j.tcs.2003.11.020 .
8. Day, Brian (1970). "On closed categories of functors" (PDF). Reports of the Midwest Category Seminar IV. Lecture Notes in Mathematics. Vol. 137. Springer. pp. 1–38.
9. McCusker, Guy; Pym, David (2007). "A Games Model of Bunched Implications" (PDF). Computer Science Logic. Lecture Notes in Computer Science. Vol. 4646. Springer.
10. Read, Stephen (1989). Relevant Logic: A Philosophical Examination of Inference. Wiley-Blackwell.
11. Brotherston, James (2012). "Bunched logics displayed" (PDF). Studia Logica . 100 (6): 1223–1254. CiteSeerX   10.1.1.174.8777 . doi:10.1007/s11225-012-9449-0. S2CID   13634990.
12. Belnap, Nuel (1982). "Display logic". Journal of Philosophical Logic . 11 (4): 375–417. doi:10.1007/BF00284976. S2CID   41451176.
13. Galmiche, Didier; Méry, Daniel; Pym, David (2005). "The Semantics of BI and Resource Tableaux". Mathematical Structures in Computer Science. 15 (6): 1033–1088. CiteSeerX   10.1.1.144.1421 . doi:10.1017/S0960129505004858. S2CID   1700033.
14. Reynolds, John (1978). "Syntactic control of interference". Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '78. pp. 39–46. doi: 10.1145/512760.512766 . ISBN   9781450373487. S2CID   18716926.
15. O'Hearn, Peter (2007). "Resources, Concurrency and Local Reasoning" (PDF). Theoretical Computer Science. 375 (1–3): 271–307. doi: 10.1016/j.tcs.2006.12.035 .
16. Calcagno, Cristiano; O'Hearn, Peter W.; Yang, Hongseok (2007). "Local Action and Abstract Separation Logic" (PDF). 22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007). pp. 366–378. CiteSeerX   10.1.1.66.6337 . doi:10.1109/LICS.2007.30. ISBN   978-0-7695-2908-0. S2CID   1044254.
17. Dinsdale-Young, Thomas; Birkedal, Lars; Gardner, Philippa; Parkinson, Matthew; Yang, Hongseok (2013). "Views: Compositional Reasoning for Concurrent Programs" (PDF). Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 48: 287–300. doi:10.1145/2480359.2429104.
18. Sergey, Ilya; Nanevski, Aleksandar; Banerjee, Anindya (2015). "Specifying and Verifying Concurrent Algorithms with Histories and Subjectivity" (PDF). 24th European Symposium on Programming. arXiv: 1410.0306 . Bibcode:2014arXiv1410.0306S.
19. Calcagno, Cristiano; Distefano, Dino; O'Hearn, Peter (2015-06-11). "Open-sourcing Facebook Infer: Identify bugs before you ship".
20. Anderson, Gabrielle; Pym, David (2015). "A Calculus and Logic of Bunched Resources and Processes". Theoretical Computer Science. 614: 63–96. doi: 10.1016/j.tcs.2015.11.035 .