Reference. A denotationally-based program logic for higher-order store

Separation logic is used to reason locally about stateful programs. State of the art program logics for higher-order store are usually built on top of untyped operational semantics, in part because traditional denotational methods have struggled to simultaneously account for general references and parametric polymorphism. The recent discovery of simple denotational semantics for general references and polymorphism in synthetic guarded domain theory has enabled us to develop TULIP, a higher-order separation logic over the typed equational theory of higher-order store for a monadic version of System F{mu,ref}. The Tulip logic differs from operationally-based program logics in two ways: predicates range over the meanings of typed terms rather than over the raw code of untyped terms, and they are automatically invariant under the equational congruence of higher-order store, which applies even underneath a binder. As a result, “pure” proof steps that conventionally require focusing the Hoare triple on an operational redex are replaced by a simple equational rewrite in Tulip. We have evaluated Tulip against standard examples involving linked lists in the heap, comparing our abstract equational reasoning with more familiar operational-style reasoning. Our main result is the soundness of Tulip, which we establish by constructing a BI-hyperdoctrine over the denotational semantics of F{mu,ref} in an impredicative version of synthetic guarded domain theory.

Cite

Cite as @aagaard-2023-a (helia, typst) · \cite{aagaard-2023-a} (LaTeX)
BibTeX
bibtex · 1 line
@article{aagaard-2023-a, title={A denotationally-based program logic for higher-order store}, volume={3}, ISSN={2969-2431}, url={http://dx.doi.org/10.46298/entics.12232}, DOI={10.46298/entics.12232}, journal={Electronic Notes in Theoretical Informatics and Computer Science}, publisher={Centre pour la Communication Scientifique Directe (CCSD)}, author={Aagaard, Frederik Lerbjerg and Sterling, Jonathan and Birkedal, Lars}, year={2023}, month=Nov }
hayagriva YAML (typst)
yaml · 17 lines
aagaard-2023-a:
  type: article
  title: A denotationally-based program logic for higher-order store
  author:
  - Aagaard, Frederik Lerbjerg
  - Sterling, Jonathan
  - Birkedal, Lars
  date: 2023-11
  url: http://dx.doi.org/10.46298/entics.12232
  serial-number:
    doi: 10.46298/entics.12232
    issn: 2969-2431
  parent:
    type: periodical
    title: Electronic Notes in Theoretical Informatics and Computer Science
    publisher: Centre pour la Communication Scientifique Directe (CCSD)
    volume: 3
Cites 47 works (4 here)
With notes (4)

Iris from the ground up: A modular foundation for higher-order concurrent separation logic jung_etal_iris_ground_up_2018

Iris is a framework for higher-order concurrent separation logic, which has been implemented in the Coq proof assistant and deployed very effectively in a wide variety of verification projects. Iris was designed with the express goal of simplifying and consolidating the foundations of modern separation logics, but it has evolved over time, and the design and semantic foundations of Iris itself have yet to be fully written down and explained together properly in one place. Here, we attempt to fill this gap, presenting a reasonably complete picture of the latest version of Iris (version 3.1), from first principles and in one coherent narrative.
PDF · DOI · pldb

Verified Software Toolchain appel_vst_2011

BI-hyperdoctrines, higher-order separation logic, and abstraction biering-2007-bi

We present a precise correspondence between separation logic and a simple notion of predicate BI, extending the earlier correspondence given between part of separation logic and propositional BI. Moreover, we introduce the notion of a BI hyperdoctrine, show that it soundly models classical and intuitionistic first- and higher-order predicate BI, and use it to show that we may easily extend separation logic to higher-order . We also demonstrate that this extension is important for program proving, since it provides sound reasoning principles for data abstraction in the presence of aliasing.
PDF · DOI · pldb

Categorical Logic and Type Theory jacobs-1999

This book is an attempt to give a systematic presentation of both logic and type theory from a categorical perspective, using the unifying concept of fibred category. Its intended audience consists of logicians, type theorists, category theorists and (theoretical) computer scientists.

External (43)
aagaard-2023-a reference entries/refs/aagaard-2023-a/aagaard-2023-a.hel