Binders by Day, Labels by Night: Effect Instances via Lexically Scoped Handlers
Handlers of algebraic effects aspire to be a practical and robust programming construct that allows one to define, use, and combine different computational effects. Interestingly, a critical problem that still bars the way to their popular adoption is how to combine different uses of the same effect in a program, particularly in a language with a static type-and-effect system. For example, it is rudimentary to define the “mutable memory cell” effect as a pair of operations, put and get, together with a handler, but it is far from obvious how to use this effect a number of times to operate a number of memory cells in a single context. In this paper, we propose a solution based on lexically scoped effects in which each use (an “instance”) of an effect can be singled out by name, bound by an enclosing handler and tracked in the type of the expression. Such a setting proves to be delicate with respect to the choice of semantics, as it depends on the explosive mixture of effects, polymorphism, and reduction under binders. Hence, we devise a novel approach to Kripke-style logical relations that can deal with open terms, which allows us to prove the desired properties of our calculus. We formalise our core results in Coq, and introduce an experimental surface-level programming language to show that our approach is applicable in practice.
Thu 23 JanDisplayed time zone: Saskatchewan, Central America change
10:30 - 11:35 | Types and EffectsResearch Papers at Ile de France II (IDF II) Chair(s): Dominique Devriese Vrije Universiteit Brussel | ||
10:30 21mTalk | Binders by Day, Labels by Night: Effect Instances via Lexically Scoped Handlers Research Papers Dariusz Biernacki University of Wrocław, Maciej Piróg University of Wrocław, Piotr Polesiuk University of Wrocław, Filip Sieczkowski University of Wrocław Link to publication DOI Media Attached | ||
10:51 21mTalk | The Fire Triangle: How to Mix Substitution, Dependent Elimination, and Effects Research Papers Link to publication DOI Media Attached | ||
11:13 21mTalk | SyTeCi: Automating Contextual Equivalence for Higher-Order Programs with References Research Papers Guilhem Jaber LS2N, Université de Nantes Link to publication DOI Media Attached |