SPLASH 2022
Mon 5 - Sat 10 December 2022 Auckland, New Zealand
Fri 9 Dec 2022 11:30 - 12:00 at Seminar Room G007 - Semantics and Security Chair(s): Derek Dreyer

In 1995, Launchbury and Peyton Jones extended Haskell with an ST monad that allows the programmer to use higher-order mutable state. They informally argued that these state computations were safely encapsulated, and as such, that the rich reasoning principles stemming from the purity of the language, were not threatened.

In this paper, we give a formal account of the preservation of purity after adding an ST monad to a simply-typed call-by-value recursive lambda calculus. We state and prove full abstraction when embedding the pure language into its extension with ST; contextual equivalences from the pure language continue to hold in the presence of ST.

Proving full abstraction of compilers is usually done by emulating or back-translating the target features (here: ST computations) into the source language, a well-known challenge in the secure compilation community. We employ a novel proof technique for proving our full abstraction result that allows us to use a semantically (but not syntactically) typed back-translation into an intermediate language. We believe that this technique provides additional insight into our proof and that it is of general interest to researchers studying programming languages and compilers using full abstraction.

The results presented here are fully formalized in the Coq proof assistant using the Iris framework.

Fri 9 Dec

Displayed time zone: Auckland, Wellington change

10:30 - 12:00
Semantics and SecurityOOPSLA at Seminar Room G007
Chair(s): Derek Dreyer MPI-SWS
10:30
30m
Research paper
Le Temps des Cerises: Efficient Temporal Stack Safety on Capability Machines using Directed CapabilitiesDistinguished Paper
OOPSLA
Aina Linn Georges Aarhus University, Alix Trieu ANSSI, Lars Birkedal Aarhus University
DOI
11:00
30m
Research paper
Plausible sealing for gradual parametricity
OOPSLA
Elizabeth Labrada University of Chile, Matías Toro University of Chile, Éric Tanter University of Chile, Dominique Devriese KU Leuven
DOI
11:30
30m
Research paper
Purity of an ST monad: full abstraction by semantically typed back-translation
OOPSLA
Koen Jacobs KU Leuven, Dominique Devriese KU Leuven, Amin Timany Aarhus University
DOI