ACM SIGPLAN Notices · 2013 · 14 citations · 13 references
ComputingComputer ScienceAlgorithmsData StructuresFormal MethodsAbstract Syntax TreesData-flow AnalysisDeductive VerificationEquivalence CheckingProof AssistantsTheorem ProvingCompositional ReasoningCompositional VerificationCorrectness CheckingMechanized ProofsModular Verification
Programs manipulating mutable data structures with intrinsic sharing present a challenge for modular verification. Deep aliasing inside data structures dramatically complicates reasoning in isolation over parts of these objects because changes to one part of the structure (say, the left child of a dag node) can affect other parts (the right child or some of its descendants) that may point into it. The result is that finding intuitive and compositional proofs of correctness is usually a struggle. We propose a compositional proof system that enables local reasoning in the presence of sharing. While the AI "frame problem" elegantly captures the reasoning required to verify programs without sharing, we contend that natural reasoning about programs with sharing instead requires an answer to a different and more challenging AI problem, the "ramification problem": reasoning about the indirect consequences of actions. Accordingly, we present a RAMIFY proof rule that attacks the ramification problem head-on and show how to reason with it. Our framework is valid in any separation logic and permits sound compositional and local reasoning in the context of both specified and unspecified sharing. We verify the correctness of a number of examples, including programs that manipulate dags, graphs, and overlaid data structures in nontrivial ways.
13
Jan Lucassen, David K. Gifford · 1988 · 480 citations
A nonrecursive list compacting algorithm
C. J. Cheney · Communications of the ACM · 1970 · 392 citations · Full text
BI as an assertion language for mutable data structures
Samin Ishtiaq, Peter W. O’Hearn · 2001 · 281 citations
Local Action and Abstract Separation Logic
Cristiano Calcagno, Peter W. O’Hearn, Hongseok Yang · 2007 · 262 citations
Alasdair Urquhart · Journal of Symbolic Logic · 1972 · 254 citations
Humanities, Philosophy, Logic +14