About Hoare Logics for Higher-Order Store | SpringerLink
Skip to main content
Springer Nature Link
Log in

About Hoare Logics for Higher-Order Store

  • Conference paper
Automata, Languages and Programming (ICALP 2005)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3580))

Included in the following conference series:

Abstract

We present a Hoare logic for a simple imperative while-language with stored commands, ie. stored parameterless procedures. Stores that may contain procedures are called higher-order. Soundness of our logic is established by using denotational rather than operational semantics. The former is employed to elegantly account for an inherent difficulty of higher-order store, namely that assertions necessarily describe recursive predicates on a recursive domain. In order to obtain proof rules for mutually recursive procedures, assertions have to explicitly refer to the code of the procedures.

Both authors have been partially supported by APPSEM II (Applied Semantics), a thematic network funded by the IST programme of the European Union, IST-2001-38957.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Abadi, M., Cardelli, L.: A Theory of Objects. Springer, Heidelberg (1996)

    MATH  Google Scholar 

  2. Abadi, M., Leino, K.R.M.: A logic of object-oriented programs. In: Dershowitz, N. (ed.) Verification: Theory and Practice, pp. 11–41. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  3. Abramsky, S., Honda, K., McCusker, G.: A fully abstract game semantics for general references. In: LICS 1998: Proceedings of the 13th Annual IEEE Symposium on Logic in Computer Science, p. 334. IEEE Computer Society, Los Alamitos (1998)

    Google Scholar 

  4. Apt, K.R.: Ten Years of Hoare’s Logic: A Survey – Part I. TOPLAS 3(4), 431–483 (1981)

    Article  MATH  Google Scholar 

  5. Calcagno, C., O’Hearn, P.W.: A logic for objects. Slides of a Talk (2001)

    Google Scholar 

  6. Hense, A.V.: Wrapper semantics of an object-oriented programming language with state. In: Ito, T., Meyer, A.R. (eds.) TACS 1991. LNCS, vol. 526, pp. 548–568. Springer, Heidelberg (1991)

    Google Scholar 

  7. Hoare, C.A.R.: An axiomatic basis for computer programming. Comm. ACM 12, 576–583 (1969)

    Article  MATH  Google Scholar 

  8. Honda, K., Yoshida, N., Berger, M.: An observationally complete program logic for imperative higher-order functions. In: 20th Symp. on Logics in Computer Science, LICS. IEEE, Los Alamitos (2005) (to appear)

    Google Scholar 

  9. Kamin, S.N., Reddy, U.S.: Two semantic models of object-oriented languages. In: Gunter, C.A., Mitchell, J.C. (eds.) Theoretical Aspects of Object-Oriented Programming: Types, Semantics, and Language Design, pp. 464–495. The MIT Press, Cambridge (1994)

    Google Scholar 

  10. Laird, J.: A categorical semantics of higher-order store. Electronic notes in Theoretical Computer Science 69 (2002)

    Google Scholar 

  11. Laird, J.: Locally boolean domains (2004) (submitted)

    Google Scholar 

  12. O’Hearn, P.W., Reynolds, J.C., Yang, H.: Local reasoning about programs that alter data structures. In: Fribourg, L. (ed.) CSL 2001 and EACSL 2001. LNCS, vol. 2142, pp. 1–19. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  13. Pitts, A.M.: Relational properties of domains. Information and Computation 127, 66–90 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  14. Reus, B.: Modular semantics and logics of classes. In: Baaz, M., Makowsky, J.A. (eds.) CSL 2003. LNCS, vol. 2803, pp. 456–469. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  15. Reus, B., Schwinghammer, J.: Denotational semantics for Abadi and Leino’s logic of objects. In: Sagiv, M. (ed.) ESOP 2005. LNCS, vol. 3444, pp. 263–278. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  16. Reus, B., Streicher, T.: Semantics and logics of objects. In: Proceedings of the 17th Symp. Logic in Computer Science, pp. 113–122 (2002)

    Google Scholar 

  17. Reus, B., Streicher, T.: Semantics and logic of object calculi. TCS, . 316, 191–213 (2004)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Sussex, Brighton, BN1 9QH, UK

    Bernhard Reus

  2. TU Darmstadt, 64298, Darmstadt, Germany

    Thomas Streicher

Authors
  1. Bernhard Reus
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Thomas Streicher
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. CITI / Departamento de Informática, Universidade Nova de Lisboa, Portugal

    Luís Caires

  2. Dipartimento di Informatica, Sistemi e Produzione, Università di Roma “Tor Vergata”, via del Politecnico 1, 00133, Roma, Italy

    Giuseppe F. Italiano

  3. Departamento de Informatica, Universidade Nova de Lisboa, 2829-516, Caparica, Portugal

    Luís Monteiro

  4. Ecole Polytechnique, Rue de Saclay, 91128, Palaiseau Cedex, France

    Catuscia Palamidessi

  5. Computer Science Department, Google Inc. and Columbia University, 1214 Amsterdam Avenue, NY 10027, New York, USA

    Moti Yung

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Reus, B., Streicher, T. (2005). About Hoare Logics for Higher-Order Store. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds) Automata, Languages and Programming. ICALP 2005. Lecture Notes in Computer Science, vol 3580. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11523468_108

Download citation

  • DOI: https://doi.org/10.1007/11523468_108

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-27580-0

  • Online ISBN: 978-3-540-31691-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation