BI-hyperdoctrines, higher-order separation logic, and abstraction

Bodil Biering, Lars Birkedal, Noah Torp-Smith

ACM Transactions on Programming Languages and Systems · 2007 · 80 citations · 28 references

DOIFull text

Open access

Concepts

Abstract

We present a precise correspondence between separation logic and a simple notion of predicate BI, extending the earlier correspondence given between part of separation logic and propositional BI. Moreover, we introduce the notion of a BI hyperdoctrine, show that it soundly models classical and intuitionistic first- and higher-order predicate BI, and use it to show that we may easily extend separation logic to higher-order . We also demonstrate that this extension is important for program proving, since it provides sound reasoning principles for data abstraction in the presence of aliasing.

References

28