ACM Transactions on Programming Languages and Systems · 2002 · 133 citations · 27 references
ComputingComputer ScienceFormal MethodsProgramming LanguagesSystems ProgrammingData AbstractionData-flow AnalysisDeductive VerificationSpecification LanguagesVerificationAbstractionAbstraction MechanismsData HidingInformation HidingModular VerificationProgram VerificationSoundnessSoundness Proofs
This article describes an approach for verifying programs in the presence of data abstraction and information hiding, which are key features of modern programming languages with objects and modules. This article draws on our experience building and using an automatic program checker, and focuses on the property of modular soundness : that is, the property that the separate verifications of the individual modules of a program suffice to ensure the correctness of the composite program. We found this desirable property surprisingly difficult to achieve. A key feature of our methodology for modular soundness is a new specification construct: the abstraction dependency , which reveals which concrete variables appear in the representation of a given abstract variable, without revealing the abstraction function itself. This article discusses in detail two varieties of abstraction dependencies: static and dynamic. The article also presents a new technical definition of modular soundness as a monotonicity property of verifiability with respect to scope and uses this technical definition to formally prove the modular soundness of a programming discipline for static dependencies.
27
Proof of correctness of data representations
C. A. R. Hoare · Acta Informatica · 1972 · 967 citations
Gary T. Leavens, Albert L. Baker, Clyde Ruby · ACM SIGSOFT Software Engineering Notes · 2006 · 787 citations
Robin Milner · 1976 · 743 citations