Segment Logic

O’Hearn, Reynolds and Yang introduced local Hoare reasoning about mutable data structures using separation logic. They reason about the local parts of the memory accessed by programs, and thus construct their smallest complete specifications. Gardner et al. generalised their work, using context logic to reason about structured data at the same level of abstraction as the data itself. In particular, we developed a formal specification of the Document Object Model (DOM), a W3C XML update library. Whilst we kept to the spirit of local reasoning, we were not able to retain small specifications for all of the commands of DOM: for example, our specification of the appendChild command was not small. We show how to obtain such small specifications by developing a more fine-grained context structure, allowing us to work with arbitrary segments of a data structure. We introduce segment logic, a logic for reasoning about such segmented data struc-tures, staring at first with a simple tree structure, but then showing how to generalise our approach to arbitrary structured data