Reference. Recovering purity with comonads and capabilities
In this paper, we take a pervasively effectful (in the style of ML) typed lambda calculus, and show how to extend it to permit capturing pure expressions with types. Our key observation is that, just as the pure simply-typed lambda calculus can be extended to support effects with a monadic type discipline, an impure typed lambda calculus can be extended to support purity with a comonadic type discipline. We establish the correctness of our type system via a simple denotational model, which we call the capability space model. Our model formalises the intuition common to systems programmers that the ability to perform effects should be controlled via access to a permission or capability, and that a program is capability-safe if it performs no effects that it does not have a runtime capability for. We then identify the axiomatic categorical structure that the capability space model validates, and use these axioms to give a categorical semantics for our comonadic type system. We then give an equational theory (substitution and the call-by-value β and η laws) for the imperative lambda calculus, and show its soundness relative to this semantics. Finally, we give a translation of the pure simply-typed lambda calculus into our comonadic imperative calculus, and show that any two terms which are βη-equal in the STLC are equal in the equational theory of the comonadic calculus, establishing that pure programs can be mapped in an equation-preserving way into our imperative calculus.
Cite
Cites 41 works (4 here)
With notes (4)
Separation logic: A logic for shared mutable data structures reynolds_separation_2002
In joint work with Peter O’Hearn and others, based on early ideas of Burstall, we have developed an extension of Hoare logic that permits reasoning about low-level imperative programs that use shared mutable data structure. The simple imperative programming language is extended with commands (not expressions) for accessing and modifying shared structures, and for explicit allocation and deallocation of storage. Assertions are extended by introducing a “separating conjunction” that asserts that its subformulas hold for disjoint parts of the heap, and a closely related “separating implication”. Coupled with the inductive definition of predicates on abstract data structures, this extension permits the concise and flexible description of structures with controlled sharing. In this paper, we survey the current development of this program logic, including extensions that permit unrestricted address arithmetic, dynamically allocated arrays, and recursive procedures. We also discuss promising future directions.
A judgmental reconstruction of modal logic pfenning-2001-a
The logic of bunched implications ohearn_pym_bi_1999
We introduce a logic BI in which a multiplicative (or linear) and an additive (or intuitionistic) implication live side-by-side. The propositional version of BI arises from an analysis of the proof-theoretic relationship between conjunction and implication; it can be viewed as a merging of intuitionistic logic and multiplicative intuitionistic linear logic. The naturality of BI can be seen categorically: models of propositional BI’s proofs are given by bicartesian doubly closed categories, i.e., categories which freely combine the semantics of propositional intuitionistic logic and propositional multiplicative intuitionistic linear logic. The predicate version of BI includes, in addition to standard additive quantifiers, multiplicative (or intensional) quantifiers [inline image] and [inline image] which arise from observing restrictions on structural rules on the level of terms as well as propositions. We discuss computational interpretations, based on sharing, at both the propositional and predicate levels.
Linear logic girard_linear_1987
The familiar connective of negation is broken into two operations: linear negation which is the purely negative part of negation and the modality “of course” which has the meaning of a reaffirmation. Following this basic discovery, a completely new approach to the whole area between constructive logics and programmation is initiated.
External (37)
- Quantitative program reasoning with graded modal types (2019)
- Fitch-Style Modal Lambda Calculi (2018)
- Coeffects: a calculus of context-dependent computation (2014)
- A Core Quantitative Coeffect Calculus (2014)
- Higher-order functional reactive programming without spacetime leaks (2013)
- Object Capabilities and Isolation of Untrusted Web Applications (2010)
- Joe-E: A Security-Oriented Subset of Java (2010)
- Deny-Guarantee Reasoning (2009)
- Bounded Linear Logic, Revisited (2009)
- Light affine lambda calculus and polynomial time strong normalization (2007)
- A Capability Calculus for Concurrency and Determinism (2006)
- Fast and loose reasoning is morally correct (2006)
- Robust composition: towards a unified approach to access control and concurrency control (2006)
- Smallfoot: Modular Automatic Assertion Checking with Separation Logic (2006)
- L3: A Linear Language with Locations (2005)
- Linear types and non-size-increasing polynomial time computation (2003)
- Modelling environments in call-by-value programming languages (2003)
- Calculating Functional Programs (2002)
- Categorical and Kripke Semantics for Constructive S4 Modal Logic (2001)
- Type and Effect Systems (1999)
- Typed Memory Management in a Calculus of Capabilities (1999)
- What is a purely functional language? (1998)
- The marriage of effects and monads (1998)
- Monad as modality (1997)
- Categorical models for local names (1996)
- A model for syntactic control of interference (1993)
- Notions of computation and monads (1991)
- Deforestation: transforming programs to eliminate trees (1990)
- Proofs and Types (1989)
- Computational lambda-calculus and monads (1989)
- Integrating functional and imperative programming (1986)
- Capability-based computer systems (1984)
- On the duality of operating system structures (1979)
- Syntactic control of interference (1978)
- HYDRA: The Kernel of a Multiprocessor Operating System (1974)
- Programming semantics for multiprogrammed computations (1966)
- Some theorems about the sentential calculi of Lewis and Heyting (1948)