The Nextgen Modality: A Modality for Non-Frame-Preserving Updates in Separation Logic
Open Access
- 10 January 2025
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 83-97
Abstract
As separation logic is a logic of resources, the way in which resources can soundly change and be updated is a fundamental aspect. Such changes have typically been restricted to certain local or frame-preserving updates. However, recently we have seen separation logics where the restriction to frame-preserving updates seems to be a hindrance towards achieving the ideal program reasoning rules. In this, paper we propose a novel nextgen modality that enables reasoning across generations where each generational change can update resources in ways that are non-local and non-frame-preserving. We implement the idea as an extension to the Iris base logic, which enriches Iris with an entirely new capability: the ability to make non-frame-preserving updates to ghost state. We show that two existing Iris modalities are special cases of the nextgen modality. Our “extension” can thus also be seen as a generalization and simplification of the Iris base logic. To demonstrate the utility of the nextgen modality we use it to construct a separation logic for a programming language with explicit stack allocation and with a return operation that clears entire stack frames. The nextgen modality is used to great effect in the reasoning rule for return, where a modular and practical reasoning rule is otherwise out of reach. This is the first separation logic for a high-level programming language with stack allocation. We sketch ideas for future work in other domains where we think the nextgen modality can be useful.Keywords
This publication has 16 references indexed in Scilit:
- Transfinite Iris: resolving an existential dilemma of step-indexed separation logic2021
- Verifying concurrent, crash-safe systems with Perennial2019
- Mechanized relational verification of concurrent programs with continuationsProceedings of the ACM on Programming Languages, 2019
- Iris from the ground up: A modular foundation for higher-order concurrent separation logicJournal of Functional Programming, 2018
- A logical relation for monadic encapsulation of state: proving contextual equivalences in the presence of runSTProceedings of the ACM on Programming Languages, 2017
- Certifying a file system using crash hoare logicCommunications of the ACM, 2017
- The Essence of Higher-Order Concurrent Separation Logic2017
- Temporary Read-Only Permissions for Separation Logic2017
- Interactive proofs in higher-order concurrent separation logic2017
- Iris2015