Views: compositional reasoning for concurrent programs
File(s)Dinsdale-Young2013Views.pdf (363.11 KB)
Accepted version
Author(s)
Dinsdale-Young, T
Birkedal, L
Gardner, P
Parkinson, M
Yang, H
Type
Conference Paper
Abstract
Compositional abstractions underly many reasoning principles for concurrent programs: the concurrent environment is abstracted in order to reason about a thread in isolation; and these abstractions are composed to reason about a program consisting of many threads. For instance, separation logic uses formulae that describe part of the state, abstracting the rest; when two threads use disjoint state, their specifications can be composed with the separating conjunction. Type systems abstract the state to the types of variables; threads may be composed when they agree on the types of shared variables.
In this paper, we present the "Concurrent Views Framework", a metatheory of concurrent reasoning principles. The theory is parameterised by an abstraction of state with a notion of composition, which we call views. The metatheory is remarkably simple, but highly applicable: the rely-guarantee method, concurrent separation logic, concurrent abstract predicates, type systems for recursive references and for unique pointers, and even an adaptation of the Owicki-Gries method can all be seen as instances of the Concurrent Views Framework. Moreover, our metatheory proves each of these systems is sound without requiring induction on the operational semantics.
In this paper, we present the "Concurrent Views Framework", a metatheory of concurrent reasoning principles. The theory is parameterised by an abstraction of state with a notion of composition, which we call views. The metatheory is remarkably simple, but highly applicable: the rely-guarantee method, concurrent separation logic, concurrent abstract predicates, type systems for recursive references and for unique pointers, and even an adaptation of the Owicki-Gries method can all be seen as instances of the Concurrent Views Framework. Moreover, our metatheory proves each of these systems is sound without requiring induction on the operational semantics.
Date Issued
2013-01-23
Date Acceptance
2013-01-23
Citation
Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 2013), 2013, pp.287-300
ISBN
978-1-4503-1832-7
Publisher
ACM
Start Page
287
End Page
300
Journal / Book Title
Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 2013)
Copyright Statement
© ACM 2013. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 2013), http://dx.doi.org/10.1145/2429069.2429104
Source
40th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 2013)
Subjects
Science & Technology
Technology
Computer Science, Software Engineering
Computer Science
COMPUTER SCIENCE, SOFTWARE ENGINEERING
Theory
Verification
concurrency
axiomatic semantics
compositional reasoning
SEPARATION LOGIC
LANGUAGE
Software Engineering
Publication Status
Published
Start Date
2013-01-23
Finish Date
2013-01-25
Coverage Spatial
Rome, Italy