POPL 2024
Sun 14 - Sat 20 January 2024 London, United Kingdom
Wed 17 Jan 2024 16:10 - 16:30 at Turing Lecture - Separation Logic Chair(s): Azalea Raad

A thunk is a mutable data structure that offers a simple memoization service: it stores either a suspended computation or the result of this computation. Okasaki (1999) presents many data structures that exploit thunks to achieve good amortized time complexity. He analyzes their complexity by associating a debit with every thunk. A debit can be paid off in several increments; a thunk whose debit has been fully paid off can be forced. Quite strikingly, a debit is associated also with future thunks, which do not yet exist in memory. Some of the debit of a faraway future thunk can be transferred to a nearer future thunk. We present a complete machine-checked reconstruction of Okasaki’s reasoning rules in Iris$, a rich separation logic with time credits. We demonstrate the applicability of the rules by verifying a few operations on streams as well as several of Okasaki’s data structures, namely the physicist’s queue, implicit queues, and the banker’s queue.

Wed 17 Jan

Displayed time zone: London change

15:10 - 16:30
Separation LogicPOPL at Turing Lecture
Chair(s): Azalea Raad Imperial College London
15:10
20m
Talk
An Iris Instance for Verifying CompCert C Programs
POPL
William Mansky University of Illinois Chicago, Ke Du
Pre-print
15:30
20m
Talk
The Logical Essence of Well-Bracketed Control Flow
POPL
Amin Timany Aarhus University, Armaël Guéneau Université Paris-Saclay - CNRS - ENS Paris-Saclay - Inria, Lars Birkedal Aarhus University
15:50
20m
Talk
Asynchronous Probabilistic Couplings in Higher-Order Separation Logic
POPL
Simon Oddershede Gregersen Aarhus University, Alejandro Aguirre Aarhus University, Philipp G. Haselwarter Aarhus University, Joseph Tassarotti NYU, Lars Birkedal Aarhus University
DOI Pre-print
16:10
20m
Talk
Thunks and Debits in Separation Logic with Time Credits
POPL
François Pottier Inria, Armaël Guéneau Université Paris-Saclay - CNRS - ENS Paris-Saclay - Inria, Jacques-Henri Jourdan CNR, LMF, Glen Mével