Handling Exceptions and Effects with Automatic Resource Analysis
There exist many techniques for automatically deriving parametric resource (or cost) bounds by analyzing the source code of a program. These techniques work effectively for a large class of programs and language features. However, non-local transfer of control as needed for exception or effect handlers has remained a challenge.
This paper presents the first automatic resource bound analysis that supports non-local control transfer between exceptions or effects and their handlers. The analysis is an extension of type-based automatic amortized resource analysis (AARA), which automates the potential method of amortized analysis. It is presented for a simple functional language with lists and linear potential functions. However, the ideas are directly applicable to richer settings and implemented for Standard ML and polynomial potential functions.
Apart from the new type system for exceptions and effects, a main contribution is a novel syntactic type- soundness theorem that establishes the correctness of the derived bounds with respect to a stack-based abstract machine. An experimental evaluation shows that the new analysis is capable of analyzing programs that cannot be analyzed by existing methods and that the efficiency overhead of supporting exception and effect handlers is low.
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 | ||