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
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.
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.
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)
- Classifying topoi in synthetic guarded domain theory (2023)
- Denotational semantics of general store and polymorphism (2022)
- On Hofmann-Streicher universes (2022)
- Lecture notes on Iris: Higher-order concurrent separation logic (2022)
- Denotational semantics for guarded dependent type theory (2020)
- Local Local Reasoning: A BI-Hyperdoctrine for Full Ground Store (2020)
- Interaction trees: representing recursive and impure programs in Coq (2019)
- Impredicative Encodings of (Higher) Inductive Types (2018)
- On Models of Higher-Order Separation Logic (2018)
- A monad for full ground reference cells (2017)
- Practical Foundations for Programming Languages (2016)
- Natural models of homotopy type theory (2016)
- Guarded Dependent Type Theory with Coinductive Types (2016)
- The Coq Proof Assistant Reference Manual (2016)
- A Model of PCF in Guarded Type Theory (2015)
- TaDA: A Logic for Time and Data Abstraction (2014)
- Intensional Type Theory with Guarded Recursive Types qua Fixed Points on Universes (2013)
- HOLCF '11: A Definitional Domain Theory for Verifying Functional Programs (2012)
- First Steps in Synthetic Guarded Domain Theory: Step-Indexing in the Topos of Trees (2011)
- A relational modal logic for higher-order stateful ADTs (2010)
- Completeness for Algebraic Theories of Local State (2010)
- Realisability semantics of parametric polymorphism, general references and recursive types (2010)
- Logical Step-Indexed Logical Relations (2009)
- Propositions as [Types] (2004)
- Notions of Computation Determine Monads (2002)
- Possible World Semantics for General Storage in Call-By-Value (2002)
- An indexed model of recursive types for foundational proof-carrying code (2001)
- Distributors at work (2000)
- From LCF to HOL: A short history (2000)
- Lifting Grothendieck universes (1997)
- Computation and Reasoning: A Type Theory for Computer Science (1994)
- A type-theoretical alternative to ISWIM, CUCH, OWHY (1993)
- Sheaves in Geometry and Logic: A First Introduction to Topos Theory (1992)
- Notions of computation and monads (1991)
- Logic and computation—Interactive proof with Cambridge LCF (1988)
- An analysis of Girard's paradox (1986)
- Type algebras, functor categories and block structure (1986)
- The effective topos (1982)
- A unified treatment of transfinite constructions for free algebras, free monoids, colimits, associated sheaves, and so on (1980)
- Edinburgh LCF: A Mechanised Logic of Computation (1979)
- LCF considered as a programming language (1977)
- An embedding theorem for closed categories (1974)
- On closed categories of functors (1970)