Later Credits: Resourceful Reasoning for the Later Modality
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 \emph{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 \emph{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.
Tue 13 SepDisplayed time zone: Belgrade, Bratislava, Budapest, Ljubljana, Prague change
10:30 - 12:10 | |||
10:30 20mTalk | Later Credits: Resourceful Reasoning for the Later Modality ICFP Papers and Events Simon Spies MPI-SWS & Saarland University, Lennard Gäher MPI-SWS & Saarland University, Joseph Tassarotti NYU, Ralf Jung MPI-SWS, Robbert Krebbers Radboud University Nijmegen, Lars Birkedal Aarhus University, Derek Dreyer MPI-SWS DOI | ||
10:50 20mTalk | Introduction and Elimination, Left and Right ICFP Papers and Events Klaus Ostermann University of Tübingen, David Binder University of Tübingen, Ingo Skupin University of Tübingen, Tim Süberkrüb University of Tübingen, Paul Downen University of Massachusetts Lowell DOI Pre-print | ||
11:10 20mTalk | Normalization for Fitch-style Modal CalculiDistinguished Paper ICFP Papers and Events Nachiappan Valliappan Chalmers University of Technology, Fabian Ruch Unaffiliated, Carlos Tomé Cortiñas Chalmers University of Technology DOI Media Attached | ||
11:30 20mTalk | Multiparty GV: Functional Multiparty Session Types With Certified Deadlock Freedom ICFP Papers and Events Jules Jacobs Radboud University, Stephanie Balzer Carnegie Mellon University, Robbert Krebbers Radboud University Nijmegen DOI | ||
11:50 20mTalk | Back to futuresJFP Presentation ICFP Papers and Events |