Later credits: resourceful reasoning for the later modality
Open Access
- 29 August 2022
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 6 (ICFP) , 283-311
Abstract
In the past two decades, step-indexed logical relations and separation logics have both come to play a major role in semantics and verification research. More recently, they have been married together in the form of step-indexed separation logics like VST, iCAP, and Iris, which provide powerful tools for (among other things) building semantic models of richly typed languages like Rust. In these logics, propositions are given semantics using a step-indexed model, and step-indexed reasoning is reflected into the logic through the so-called “later” modality. On the one hand, this modality provides an elegant, high-level account of step-indexed reasoning; on the other hand, when used in sufficiently sophisticated ways, it can become a nuisance, turning perfectly natural proof strategies into dead ends. In this work, we introduce later credits , a new technique for escaping later-modality quagmires. By leveraging the second ancestor of these logics—separation logic—later credits turn “the right to eliminate a later” into an ownable resource, which is subject to all the traditional modular reasoning principles of separation logic. We develop the theory of later credits in the context of Iris, and present several challenging examples of proofs and proof patterns which were previously not possible in Iris but are now possible due to later credits.Keywords
Funding Information
- Dutch Research Council (016.Veni.192.259)
- NSF (2123864)
This publication has 53 references indexed in Scilit:
- Step-Indexed Kripke Model of Separation Logic for Storable LocksElectronic Notes in Theoretical Computer Science, 2011
- Logical Step-Indexed Logical RelationsLogical Methods in Computer Science, 2011
- Semantic foundations for typed assembly languagesACM Transactions on Programming Languages and Systems, 2010
- Simplifying Linearizability Proofs with Reduction and Abstraction2010
- Resources, concurrency, and local reasoningTheoretical Computer Science, 2007
- A semantics for concurrent separation logicTheoretical Computer Science, 2007
- Reading, Writing and RelationsLecture Notes in Computer Science, 2006
- An indexed model of recursive types for foundational proof-carrying codeACM Transactions on Programming Languages and Systems, 2001
- Local Reasoning about Programs that Alter Data Structures2001
- Linearizability: a correctness condition for concurrent objectsACM Transactions on Programming Languages and Systems, 1990