Exorcis: Decoupling Angels from Demons in a High-Level Logic for Effect-Dependent Program Transformations
Type-and-effect systems are a well-known method of “taming effects” in higher-order imperative languages. One of the main benefits of such systems is that they are believed to validate useful program transformations (such as hoisting, deduplicating, and reordering) which are not valid in the presence of arbitrary effects but are valid under effect constraints. While there is a large body of work on semantic models and proof techniques for formally establishing the validity of such transformations, we are still lacking a high-level, mechanized logic for reasoning about them effectively in the presence of rich language features like higher-order state.
In this paper, we present Exorcis, a relational logic, implemented in the Iris/Rocq framework, for machine-checked verification of effect-dependent program transformations at a much higher level of abstraction than was previously possible. To support high-level reasoning about a rich feature set (including non-determinism and dynamically allocated higher-order state), Exorcis builds closely on prior Iris-based approaches to this problem. In those approaches, the simulation relation on expressions is \emph{decoupled}, so that angelic reasoning about the specification expression can be performed separately from demonic reasoning about the implementation expression, thus enabling proofs of reorderings for \emph{observably pure} expressions. Exorcis goes a step further, fully decoupling angelic heaps/values from demonic heaps/values in order to support proofs of reorderings for \emph{observably effectful} expressions as well. As a bonus, this approach enables us to show compatibility of our relation with a semantic interpretation—à la Benton et al.—of effect typing.