The Nextgen Modality: A Modality for Non-Frame-Preserving Updates in Separation Logicdistinguished paper
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 has typically been restricted to certain \emph{local} or \emph{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 \emph{nextgen} modality that enables reasoning across \emph{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 and 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.
Tue 21 JanDisplayed time zone: Mountain Time (US & Canada) change
09:00 - 10:30 | |||
09:00 60mKeynote | CRIS: The power of imagination in specification and verification CPP | ||
10:00 30mTalk | The Nextgen Modality: A Modality for Non-Frame-Preserving Updates in Separation Logicdistinguished paper CPP Simon Friis Vindum Aarhus University, Aina Linn Georges Max Planck Institute for Software Systems (MPI-SWS), Lars Birkedal Aarhus University |