Type, Ability, and Effect Systems: Perspectives on Purity, Semantics, and Expressiveness
Programming benefits from a clear separation between pure, mathematical computation and impure, effectful interaction
with the world. Existing approaches to enforce this separation
include monads, type-and-effect systems, and capability systems.
All share a tension between precision and usability, and
each one has non-obvious strengths and weaknesses.
This paper aims to raise the bar in assessing such systems.
First, we propose a semantic definition of purity,
inspired by contextual equivalence, as a baseline for effect soundness
independent of any specific typing discipline.
Second, we propose that expressiveness should be measured by
the degree of completeness, i.e., how many semantically pure terms
can be typed as pure.
Using this measure, we focus on minimal meaningful effect and
capability systems and show that they are incomparable, i.e.,
neither subsumes the other in terms of expressiveness.
Based on this result, we
propose a synthesis and show that \emph{type, ability, and effect systems}
combine their respective strengths while
avoiding their weaknesses.
As part of our formal model, we provide a logical relation
to facilitate proofs of purity and other
properties for different effect typing disciplines.
Mon 5 OctDisplayed time zone: Pacific Time (US & Canada) change
15:30 - 17:00 | Effects, Capabilities, and ImmutabilityOOPSLA at East Hall 2 Chair(s): Alex Potanin Australian National University | ||
15:30 18mTalk | Revisiting Row Polymorphism for Set-Theoretic Types OOPSLA Mickaël Laurent Charles University, Pierre Donat-Bouillud Czech Technical University, Filip Křikava Czech Technical University, Jan Vitek Charles University DOI | ||
15:48 18mTalk | Type, Ability, and Effect Systems: Perspectives on Purity, Semantics, and Expressiveness OOPSLA DOI | ||
16:06 18mTalk | Transitive, Abstract, and Class Polymorphic ImmutabilityDistinguished Paper OOPSLA Aosen Xiong University of Waterloo, Yudi Bai University of Waterloo, Haifeng Shi University of Waterloo, Lian Sun University of Waterloo, Mier Ta University of Waterloo, Werner Dietl University of Waterloo DOI | ||
16:24 18mTalk | Handling Exceptions and Effects with Automatic Resource Analysis OOPSLA Ethan Chu Carnegie Mellon University, Yiyang Guo Carnegie Mellon University, Jan Hoffmann Carnegie Mellon University DOI | ||