Separation logic

In computer science, separation logic^[1] is an extension of Hoare logic, a way of reasoning about programs. It was developed by John C. Reynolds, Peter O'Hearn, Samin Ishtiaq and Hongseok Yang,^[1]^[2]^[3]^[4] drawing upon early work by Rod Burstall.^[5] The assertion language of separation logic is a special case of the logic of bunched implications (BI).^[6]

Separation logic facilitates reasoning about:

programs that manipulate pointer data structures — including information hiding in the presence of pointers;
"transfer of ownership" (avoidance of semantic frame axioms); and
virtual separation (modular reasoning) between concurrent modules.

Separation logic supports the developing field of research described by Peter O'Hearn and others as local reasoning, whereby specifications and proofs of a program component mention only the portion of memory used by the component, and not the entire global state of the system. Applications include automated program verification (where an algorithm checks the validity of another algorithm) and automated parallelization of software.

Assertions: Operators and semantics

Separation logic assertions describe "states" consisting of a store and a heap, roughly corresponding to the state of local (or stack-allocated) variables and dynamically-allocated objects in common programming languages such as C and Java. A store $s$ is a function mapping variables to values. A heap $h$ is a partial function mapping memory addresses to values. Two heaps $h$ and $h'$ are disjoint (denoted $h \,\bot\, h'$ ) if their domains do not overlap (i.e., if for every memory address $\ell$ , at least one of $h(\ell)$ and $h'(\ell)$ is undefined).

The logic allows to prove judgements of the form $s, h \models P$ , where $s$ is a store, $h$ is a heap, and $P$ is an assertion over the given store and heap. Separation logic assertions (denoted as $P$ , $Q$ , $R$ ) contain the standard boolean connectives and, in addition, $\mathbf{e}\mathbf{m}\mathbf{p}$ , $e \mapsto e'$ , $P \ast Q$ , and $P {-\!\!\ast}\, Q$ , where $e$ and $e'$ are expressions.

The constant $\mathbf{e}\mathbf{m}\mathbf{p}$ asserts that the heap is empty, i.e., $s, h \models \mathbf{e}\mathbf{m}\mathbf{p}$ when $h$ is undefined for all addresses.
The binary operator $\mapsto$ takes an address and a value and asserts that the heap is defined at exactly one location, mapping the given address to the given value. I.e., $s, h \models e \mapsto e'$ when $h([\![e]\!]_{s}) = [\![e']\!]_{s}$ (where $[\![e]\!]_{s}$ denotes the value of expression $e$ evaluated in store $s$ ) and $h$ is otherwise undefined.
The binary operator $\ast$ (pronounced star or separating conjunction) asserts that the heap can be split into two disjoint parts where its two arguments hold, respectively. I.e., $s, h \models P \ast Q$ when there exist $h_1, h_2$ such that $h_1 \,\bot\, h_2$ and $h = h_1 \cup h_2$ and $s, h_1 \models P$ and $s, h_2 \models Q$ .
The binary operator $-\!\!\ast$ (pronounced magic wand or separating implication) asserts that extending the heap with a disjoint part that satisfies its first argument results in a heap that satisfies its second argument. I.e,. $s, h \models P -\!\!\ast\, Q$ when for every heap $h' \,\bot\, h$ such that $s, h' \models P$ , also $s, h \cup h' \models Q$ holds.

The operators $\ast$ and $-\!\!\ast$ share some properties with the classical conjunction and implication operators. They can be combined using an inference rule similar to modus ponens

\frac{s, h \models P \ast (P -\!\!\ast\, Q)}{s, h \models Q}

and they form an adjunction, i.e., $s, h \cup h' \models P \ast Q \Rightarrow R$ if and only if $s, h \models P \Rightarrow Q -\!\!\ast\, R$ for $h \,\bot\, h'$ ; more precisely, the adjoint operators are $\_ \ast Q$ and $Q -\!\!\ast\, \_$ .

Reasoning about programs: triples and proof rules

In separation logic, Hoare triples have a slightly different meaning than in Hoare logic. The triple $\{P\}\ C\ \{Q\}$ asserts that if the program, $C$ , executes from an initial state satisfying the precondition, $P$ , then the program will not go wrong (e.g., have undefined behaviour), and if it terminates, then the final state will satisfy the postcondition, $Q$ . In essence, during its execution, $C$ may access only memory locations whose existence is asserted in the precondition or that have been allocated by $C$ itself.

In addition to the standard rules from Hoare logic, separation logic supports the following very important rule:

$\frac{ \{P\}\ C\ \{Q\} }{ \{P \ast R\}\ C\ \{Q \ast R\} }~\mathsf{mod}(C) \cap \mathsf{fv}(R) =\emptyset$

This is known as the frame rule (named after the frame problem) and enables local reasoning. It says that a program that executes safely in a small state (satisfying $P$ ), can also execute in any bigger state (satisfying $P \ast R$ ) and that its execution will not affect the additional part of the state (and so $R$ will remain true in the postcondition). The side condition enforces this by specifying that none of the variables modified by $C$ occur free in $R$ , i.e. none of them are in the 'free variable' set $\mathsf{fv}$ of $R$ .

Implementations

The Ynot^[7] library for the Coq proof assistant contains an implementation.

References

↑ 1.0 1.1 Separation Logic: A Logic for Shared Mutable Data Structures. John C. Reynolds. LICS 2002.
↑ Intuitionistic Reasoning about Shared Mutable Data Structure. John Reynolds. Millennial Perspectives in Computer Science, Proceedings of the 1999 Oxford-Microsoft Symposium in Honour of Sir Tony Hoare
↑ BI as an Assertion Language for Mutable Data Structures. Samin Ishtiaq, Peter O'Hearn. POPL 2001.
↑ Local Reasoning about Programs that Alter Data Structures. Peter O'Hearn, John Reynolds, Hongseok Yang. CSL 2001
↑ Some techniques for proving programs which alter data structures. R.M. Burstall. Machine Intelligence 7, 1972.
↑ The Logic of Bunched Implications P.W. O'Hearn and D. J. Pym. Bulletin of Symbolic Logic , 5(2), June 1999, pp215-244
↑ The Ynot Project homepage