A logical analysis of aliasing in imperative higher-order functions
Authors:
Open Access
- 12 September 2005
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 40 (9) , 280-293
Abstract
We present a compositional program logic for call-by-value imperative higher-order functions with general forms of aliasing, which can arise from the use of reference names as function parameters, return values, content of references and parts of data structures. The program logic extends our earlier logic for alias-free imperative higher-order functions with new modal operators which serve as building blocks for clean structural reasoning about programs and data structures in the presence of aliasing. This has been an open issue since the pioneering work by Cartwright-Oppen and Morris twenty-five years ago. We illustrate usage of the logic for description and reasoning through concrete examples including a higher-order polymorphic Quicksort. The logical status of the new operators is clarified by translating them into (in)equalities of reference names. The logic is observationally complete in the sense that two programs are observationally indistinguishable if they satisfy the same set of assertions.Keywords
This publication has 19 references indexed in Scilit:
- Elimination of spatial connectives in static spatial logicsTheoretical Computer Science, 2005
- A calculus of mobile processes, IIInformation and Computation, 1992
- Algebraic laws for nondeterminism and concurrencyJournal of the ACM, 1985
- Ten Years of Hoare's Logic: A Survey—Part IACM Transactions on Programming Languages and Systems, 1981
- Specifying the Semantics of while Programs: A Tutorial and Critique of a Paper by Hoare and LauerACM Transactions on Programming Languages and Systems, 1981
- The logic of aliasingActa Informatica, 1981
- Assignment and Procedure Call Proof RulesACM Transactions on Programming Languages and Systems, 1980
- Verification of Array, Record, and Pointer Operations in PascalACM Transactions on Programming Languages and Systems, 1979
- An axiomatic basis for computer programmingCommunications of the ACM, 1969
- Assigning meanings to programs1967