Handling Exceptions and Effects with Automatic Resource Analysis DOI: 10.1145/3798207 Journal: PACMPL Volume: 10 OOPSLA1 99 4 CCS: Theory of computation Control primitives CCS: Theory of computation Program analysis CCS: Theory of computation Type theory CCS: Theory of computation Abstract machines CCS: Theory of computation Operational semantics

Ethan Chu, Yiyang Guo, Jan Hoffmann · 2026

Read Handling Exceptions and Effects with Automatic Resource Analysis DOI: 10.1145/3798207 Journal: PACMPL Volume: 10 OOPSLA1 99 4 CCS: Theory of computation Control primitives CCS: Theory of computation Program analysis CCS: Theory of computation Type theory CCS: Theory of computation Abstract machines CCS: Theory of computation Operational semantics by Ethan Chu, Yiyang Guo, Jan Hoffmann (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-02260.txt.

Introduction

Ethan Chu, Yiyang Guo, and Jan Hoffmann extend automatic cost analysis to programs that jump around in this 2026 paper. Many tools can read code and derive bounds on time or memory use. They struggle when control jumps far, as with exceptions or effect handlers. A handler can catch a thrown effect from deep inside a program.

Their analysis is the first to bound costs across such jumps. It extends a type-based method built on amortized analysis, where costs are prepaid by data. New type rules cover exceptions and handlers, and a soundness proof checks them against a stack machine. Tests show the method handles programs older tools cannot. Overhead from supporting handlers stays low in their trials.

Catalog record

CREATOREthan Chu, Yiyang Guo, Jan Hoffmann
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE148850
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.02260

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Handling Exceptions and Effects with Automatic Resource Analysis DOI: 10.1145/3798207 Journal: PACMPL Volume: 10 OOPSLA1 99 4 CCS: Theory of computation Control primitives CCS: Theory of computation Program analysis CCS: Theory of computation Type theory CCS: Theory of computation Abstract machines CCS: Theory of computation Operational semantics Ethan Chu, Yiyang Guo, Jan Hoffmann Abstract . 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. † † cc-license: by 1. Introduction The goal of automatic resource bound analysis is to statically and automatically infer information on the resource use of a program. In this context, resources are quantities used during the execution of the program, such as time, energy, or memory. Such information is useful for users of a software library ( 63 ) , to schedule jobs in a data center, to ensure safety and security in resource constraint settings such as embedded systems ( 108 ; 20 ) and smart contracts ( 33 ; 6 ) , and to automatically detect performance bugs ( 38 ) . There are many existing methods for inferring resource information, including type systems ( 61 ; 102 ; 26 ; 10 ; 105 ; 49 ) , deriving and solving recurrence relations ( 107 ; 43 ; 2 ; 72 ; 29 ) , and other static analyses ( 47 ; 13 ; 19 ) . Most techniques are designed to derive (worst-case) upper bounds. However, some analyses focus on (best-case) lower bounds ( 8 ; 41 ; 86 ) and expected cost ( 85 ; 12 ; 24 ) . Automatic resource bound analysis is an undecidable problem, but the work in the area continues to expand the class of bounds that can be derived, to improve the efficiency of analyses, and to expand the set of supported language features. Non-Local Control Some of the most challenging programming language features for automatic resource analysis involve non-local transfer of control, such as exception handlers, continuations ( 39 ; 92 ) , and effect handlers ( 90 ; 15 ) . Exceptions are a popular language feature that can redirect control flow by dynamically transferring control to an exception handler , which often resides in a previously called function. It is comparatively straightforward to support errors or exceptions without handlers ( 56 ) when deriving worst-case bounds. The reason is that early termination with an error reduces the resource cost in comparison to the non-error case. Exception handlers are challenging because resource analyses are generally designed around regular control-flow patterns such as structural recursion or simple for loops. We are only aware of one resource analysis that has limited support for intraprocedural exceptions handlers ( 2 ) , that is, handlers that catch exceptions raised in the same function call. We are not aware of a resource analysis that supports general exceptions where raised exceptions cannot be statically linked to a handler in the same function. Algebraic effects and the associated paradigm of programming with effect handlers have gained popularity in the programming language community in the past few years ( 98 ; 101 ; 36 ; 35 ) . They can be seen as a generalization of exceptions where the user defines a set of operations (or effects), whose implementation is context-dependent and provided by an effect handler. Compared to exception handlers, effect handlers provide additional difficulties for resource analysis: they can access a delimited continuation ( 73 ; 39 ) to resume the computation at an operations’ call site or to provide a new effect handler for the deferred computation. Analyzing programs with continuations is hard because it is difficult to predict the dynamic control-flow. To the best of our knowledge there are no resource analyses that support continuations, delimited continuations, or effect handlers. Resource Bounds for Programs with Exception and Effects This paper introduces the first resource bound analysis for computational effects and their handlers. In addition, it is the first resource bound analysis that fully supports exception handlers and exceptions that can transfer control between different functions. We extend a type-based technique called automatic amortized resource analysis (AARA) ( 57 ) , which was introduced by Hofmann and Jost ( 61 ) . In AARA, types constitute resource bounds, and type derivations are certificates of the soundness of the bound with respect to an operational cost semantics. It is parametric in the resource and derives high-water mark bounds for non-monotone resource metrics. The analysis supports recursive types ( 45 ) , higher-order functions ( 64 ) , arrays, and references ( 81 ) . AARA can be seen as an automation of the potential methods of amortized analysis, and the use of potential functions is crucial for the treatment of exception handlers. Contributions We conservatively extend AARA with typing rules for exceptions, computational effects, and handlers supporting one-shot continuations so that we can account for resource cost that depends on the non-local transfer of control. The cost of executing exception or effect handlers is bounded by a function of the payload of exceptions or effects. The analysis is parametric in the type of this payload. In a nutshell, the idea is that a handler establishes a contract that consists of a potential function, which specifies the amount of potential that needs to be provided by an exception or effect. In this article, we focus on linear worst-case bounds for a simple call-by-value language with computational effects with handlers, higher-order functions, lists, sums, and products. However, extending the techniques to more language features and a larger set of bounds is orthogonal. In fact, we implemented the technique for recursive types and polynomial bounds. We also show how exceptions, exception handlers, and their respective typing rules can be derived from effects and effect handlers. Besides the design of the resource-aware type system, the main technical contributions are the soundness proof, the implementation, and an experimental evaluation. Soundness Proof A technical innovation of this work is a novel proof technique for establishing the soundness of the derived bounds with respect to a stack-based abstract machine that specifies the cost and behavior of programs. Almost all past soundness proofs are based on big-step cost

Read the complete text