Aarhus University Seal

Talk: Restrictable Effects: Handling Effects Case by Case by Edward Lee

Info about event

Time

Monday 7 December 2026,  at 13:00 - 14:00

Location

Nygaard 192

Abstract:

Type and effect systems track the effects that a computation may perform, and effect handlers intercept and handle them. Ideally, an effect would be as precise as a type: not merely Abort, but Abort[DivByZero]. Yet whether and how effects should be parameterized is not entirely settled. Parameterizing effects by types is the obvious choice, but since function types already carry effects, types and effects then become mutually dependent, with subtle consequences for inference and handling. Existing systems therefore make difficult trade-offs among precision, composability, and extensibility.

In this paper, we present restrictable effects: each effect belongs to an effect family and is indexed by the cases of that family, so types and effects stay separate. Every effect family, such as Abort, declares a set of cases, and each effect in the family, e.g. Abort[DivByZero] or Abort[i - DivByZero], is indexed by a Boolean formula over those cases. Each family is declared open or closed: an open family may later gain new cases, whereas the cases of a closed family are fixed. Accordingly, case indices form a powerset algebra for a closed family and a finite--cofinite algebra for an open one. A handler subtracts the cases it handles from the index: a partial handler that handles DivByZero turns Abort[i] into Abort[i - DivByZero], while a wildcard handler removes the entire family, including cases added later. A handler may resume the computation, or bind a caught effect as a value and re-raise it at its original case index, so no precision is lost.

We formalize restrictable effects in a call-by-value lambda calculus with effect handlers whose type and effect system is polymorphic in types, effects, and case indices. We prove type safety, i.e. progress and preservation, and effect safety: the effect of an expression is an upper bound on the effects its evaluation may leave unhandled. We further prove an extensibility theorem: a well-typed program remains well typed, with the same type and effect, when an open effect family gains new cases or when new effect families are added. We mechanize all proofs in the Rocq proof assistant.