Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-28T19:52:13.753Z Has data issue: false hasContentIssue false
  • English
  • Français

Partial hyperdoctrines: categorical models for partial function logic and Hoare logic

Published online by Cambridge University Press:  04 March 2009

Peter Knijnenburg  and
Frank Nordemann
Peter Knijnenburg
Affiliation:
Department of Computer Science, Utrecht University, Padualaan 14, 3584 CH Utrecht, the Netherlands
Frank Nordemann
Affiliation:
Department of Computer Science, Utrecht University, Padualaan 14, 3584 CH Utrecht, the Netherlands
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we provide a categorical interpretation of the first-order Hoare logic of a small programming language by giving a weakest precondition semantics for the language. To this end, we extend the well-known notion of a (first-order) hyperdoctrine to include partial maps. The most important new aspect of the resulting partial (first-order) hyperdoctrine is a different notion of morphism between the fibres. We also use this partial hyperdoctrine to give a model for Beeson's Partial Function Logic such that (a version of) his axiomatization is complete with respect to this model. This shows the usefulness of the notion, independent of its intended use as a model for Hoare logic.

Type
Research Article
Information
Mathematical Structures in Computer Science , Volume 4 , Issue 2 , June 1994 , pp. 117 - 146
Copyright
Copyright © Cambridge University Press 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Apt, K. R. (1981) Ten years of Hoare's logic. ACM Trans, on Programming Languages and Systems 3 431–483.CrossRefGoogle Scholar
Beeson, M. J. (1986) Proving programs and programming proofs. In: Marcus, B.et al. (eds.) Logic, Methodology and Philosophy of Science VII, Elsevier, Amsterdam51–82.Google Scholar
Cousot, P. (1990) Methods and logics for proving programs. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science B, Elsevier, Amsterdam.Google Scholar
DiPaola, R. and Heller, A. (1987) Dominical categories: Recursion theory without elements. J.Symbolic Logic 52 594–635.CrossRefGoogle Scholar
Dijkstra, E. W. (1976) A Discipline of Programming, Prentice Hall, Englewood Cliffs.Google Scholar
Freyd, P. and Scedrov, A. (1991) Categories, Allegories, North-Holland, Amsterdam.Google Scholar
Hoare, C. A. R. (1969) An axiomatic basis for computer programming. Comm. ACM 12 (10)576–580.Google Scholar
Hoehnke, H. J. (1977) On partial algebras. Colloq. Math. Soc. János Bolyai 29 373–412.Google Scholar
Hyland, J. M. E., Johnstone, P. T. and Pitts, A. M. (1980) Tripos theory. Math. Proc. Camb. Phil. Soc. 88 205–232.Google Scholar
Johnstone, P. T. (1982) Stone Spaces, Cambridge Studies in Advanced Mathematics 3, Cambridge University Press, Cambridge.Google Scholar
Mac Lane, S. (1971) Categories for the Working Mathematician, Graduate Texts in Mathematics 5, Springer Verlag, Berlin.CrossRefGoogle Scholar
Lawvere, F. W. (1969) Adjointness in foundations. Dialectica 23 281–296.CrossRefGoogle Scholar
Lawvere, F. W. (1970) Equality in hyperdoctrines and the comprehension schema as an adjoint functor. In: Heller, A. (ed.) Proc. New York Symp. on Applications of Categorical Algebra, Amer. Math. Soc. 1–14.Google Scholar
Makkai, M. and Reyes, G. E. (1977) First-order Categorical Logic. Springer-Verlag Lecture Notes in Mathematics 611.Google Scholar
Moggi, E. (1991) Notions of computations and monads. Information and Computation 93 (1)55–93.Google Scholar
Obtulowicz, A. (1986) The logic of categories of partial functions and its applications. Dissertationes Mathematicae, CCXLI Państwowe Wydawnictwo Naukowe.Google Scholar
Pitts, A. M. (1989a) Conceptual completeness for first-order intuitionistic logic: an application of categorical logic. Ann. of Pure and Applied Logic 41 (1) 33–82.CrossRefGoogle Scholar
Pitts, A. M. (1989b) Notes on categorical logic. Technical report, Computer Laboratory, University of Cambridge.Google Scholar
Pitts, A. M. (1990) Evaluation Logic. In: Birtwistle, G. (ed.) Higher Order Workshop, Banff 1990, Springer-Verlag, Berlin.Google Scholar
Robinson, E. and Rosolini, G. (1988) Categories of partial maps. Information and Computation 79 95–130.CrossRefGoogle Scholar
Rosolini, G. (1986) Continuity and effectiveness in topoi, PhD thesis, Univ. of Oxford.Google Scholar
Scott, D. S. (1979) Identity and existence in intuitionistic logic. In: Fourman, M. P., Mulvey, C. J. and Scott, D. S. (eds.) Applications of Sheaves.Google Scholar
Tennent, R. D. (1987) A note on undefined expression values in programming logics. Information Processing Letters 24 331–333.CrossRefGoogle Scholar
Van Dalen, D. and Troelstra, A. S. (1988) Constructivism in Mathematics. Studies in Logic and the Foundations of Mathematics 121, North-Holland, Amsterdam.Google Scholar
Wagner, E. G. (1987) A categorical treatment of pre- and post-conditions. Theoretical Computer Science 53 3–24.CrossRefGoogle Scholar