Two-Sided Amortized Resource Analysis: Verifying Resource Lower Bounds via Ill-Typing
This paper presents a \emph{two-sided type system with potential}, a type-based technique for verifying resource lower bounds of functional programs. Automatic amortized resource analysis (AARA) verifies upper bounds: types carry potential, and a typing derivation certifies that the available resources are sufficient for evaluation. A lower bound, however, is a necessity statement—the program evaluates only if enough resources are available—and prior type-based approaches obtain it by switching the substructural discipline of potential, so that upper and lower bounds live in separate type systems. Yet the two kinds of bounds complement each other: a matching pair characterizes a program’s cost exactly, and the gap between them limits how much the cost can vary across inputs of the same size.
Our type system combines AARA-style potential with the two-sided type systems of Ramsay and Walpole, whose central guarantee is that ill-typed programs do not evaluate. In a two-sided judgment, typing formulas may constrain arbitrary terms and may appear on both sides of the turnstile; the judgment $t : A \vdash q$ states that if $t$ evaluates to a result of type $A$, then at least $q$ units of resource must be available—that is, $q$ is a lower bound. Because potential makes typing formulas non-replicable, our system follows an affine discipline instead of the replicable contexts of the original framework. We define the meaning of types by semantic typing over \emph{value states}, pairs of a value and a remaining resource amount, and we prove soundness on a safety fragment; corollaries recover the classical two-sided guarantees and the soundness of both kinds of bounds in a single proof system. A prototype type checker in OCaml verifies, on a suite of 19 benchmarks, matching pairs of bounds that characterize costs exactly, as well as lower bounds for programs whose upper bounds are unavailable. Finally, as a parallel exploration, we study a two-sided linear type system in which every value is a non-replicable resource; there, closures that capture linear resources call for dual typing formulas, and the exact accounting explains the affine design of the main system.