CS Paper Radar

Categorical Models of Amortized Cost: An Adjoint Relationship between Cost and Potential

David Binder, David Corfield, Dominic Orchard, Vineet Rajani

cs.PL cs.LO ·submitted 2026-08-10 14:14 UTC · v1

Abstract

Various type systems have been developed to track the cost $κ$ of a computation using a cost-tracking monad $M\ κτ$. On its own, this only tracks the worst-case cost of a computation. If we also want to track amortized cost, then we can add a type $[κ]τ$ which stores potential $κ$ with a type $τ$, together with operations for storing and releasing potential. In this work, we build on one such system, $λ$-amor: $λ$-amor allows to track cost and potential in the type system and subsumes effect and coeffect-based systems, call-by-value and call-by-name based languages. In this paper, we identify the abstract properties that denotational models of type theories for cost and potential have to satisfy: Cost and potential must be modelled by an adjoint pair of graded functors, where the functor modelling cost forms both a graded monad and a compatible graded comonad. We present three concrete instances of this general abstract scheme: (1) A simple set-theoretic model that ignores the cost tracked by the type system, (2) the Kripke logical relations model in the original $λ$-amor paper (which we show can be turned into an instance of the adjoint model), and (3) a novel model based on copresheaves on a monoidal category of costs, where we model pairs and functions by Day convolution and its right-adjoint.

Comment
25 pages, 5 pages appendix

Closest papers

Nearest neighbours by meaning across the whole index.

An Algebraic Perspective on Operational Semantics

cs.PL ·2026-11-12 ·Eric Bond, Max New
theory similarity 0.67
Abstract

Languages with effects are typically given two independently specified semantic accounts: a denotational semantics based on (free) models, and an operational semantics defined by effect-specific reduction rules. This separation leads to two independently constructed semantic structures whose relationship must then be established a posteriori. We present a unified construction in which both denotational interpretation and operational reduction are constructed from an algebraic theory specifying the effects. We work with call-by-push-value extended by the operations of an algebraic theory. We prove equational canonicity and give a tree-based operational semantics that reduces every closed computation to a tree of operations. When the free model monad is a monadic container, we derive from it a configuration-based small-step semantics. Configurations are elements of the free model. Every step preserves the denotation. Under a condition we call affinity, every reduction terminates and at ground types computes the denotation. We instantiate the framework with state, errors, writer, and weighted and pre-convex probabilistic choice. For errors, writer and weighted choice we recover the familiar rules. For state we get a machine that runs the program from every initial state at once.

0.30

Two-Sided Amortized Resource Analysis: Verifying Resource Lower Bounds via Ill-Typing

cs.PL ·2026-11-01 ·Zimu Chen, Di Wang
theory similarity 0.63
Abstract · 56 pages. Reproduction artifact: https://doi.org/10.5281/zenodo.23662529

We present a two-sided type system with potential for verifying resource lower bounds of functional programs. Automatic amortized resource analysis (AARA) verifies upper bounds: types carry potential, and typing certifies sufficient resources. 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. Matching upper and lower bounds characterize a program's cost exactly. Our 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. Typing formulas may constrain arbitrary terms and 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 interpret types by semantic typing over value states, pairs of values and remaining resources, 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. In 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.

0.36

Finitary Semantics for Full Ground Local State

cs.PL ·2026-08-21 ·Orpheas van Rooij, Ohad Kammar, Sam Lindley, Cristina Matache
similarity 0.62
Abstract

Full ground local state (FGLS) refers to dynamically allocated mutable state that allows storing ground values and references. It is a key ingredient in many imperative algorithms as it enables (cyclic) data structures. In this work, we treat full ground local state as a computational effect, focusing on one particular denotational model: Kammar et al.'s possible worlds monad on sets indexed over sets of locations. We resolve an outstanding question regarding this FGLS monad: is it finitary? We show that the FGLS monad is not finitary by showing the existence of non-finitary computations in the monad. We then introduce a finitary submonad of Kammar et al.'s monad, give it a concrete description and show that it provides an adequate semantics for FGLS. The submonad we construct paves the way to understanding FGLS in the future via an equational axiomatization suitable for program reasoning.

0.30

Internal Languages for Thin Epsilon-Hyperdoctrines: Soundness, Completeness, and Rocq Formalization

cs.LO math.LOmath.CT ·2026-10-10 ·Zoltán Gábor Molnár, Csaba Tóth
code/data similarity 0.60
Abstract · 41 pages, 1 figure. Rocq formalization: https://github.com/mozow01/HyperLogic

We present a typed proof-term calculus for intuitionistic intensional first-order logic with Hilbert's epsilon-operator and prove its soundness and completeness with respect to hyperdoctrinal models with thin bicartesian closed setoid categories (BiCCCs) as fibres and formula-indexed witness selections. The calculus provides an explicit internal language for these epsilon-hyperdoctrines: for each fixed typed signature, its syntactic term model is initial for syntax-indexed, interpretation-preserving model morphisms, with uniqueness up to setoid equality. The nested epsilon syntax is organized by a well-founded dependency relation on formula labels. Concrete countermodels exhibit failure of excluded middle and show that formula conversion need not identify the selected witnesses. We also compare the full calculus with its epsilon-free and epsilon-only fragments. The principal constructions and metatheorems are formalized in Rocq. With setoid BiCCCs, proof irrelevance is a choice of equality, not the erasure of proofs: the proofs and their categorical operations remain available as the basis for a future proof-relevant categorical semantics.

0.43

A monadic interpreter and type-and-effect checker

cs.PL ·2026-09-07 ·Stefano Raviola, Paola Giannini, Francesco Dagnino
similarity 0.60
Abstract

We present a concrete implementation in Haskell of a monadic framework that includes both a small-step interpreter and a type-and-effect checker for the corresponding language. Our approach separates the language syntax from the semantics of its effects. This design allows the interpreter to remain parametric over the underlying monad, while the static checker approximates effects independently of their concrete implementation. The theoretical foundation of this framework-applied to a call-by-value lambda calculus with generic effects represented by operations that produce monadic values and are managed through handlers-was introduced in previous work, where the focus was on proving the soundness of the approach. In contrast, the present work leverages Haskell's support for modular programming and monads to demonstrate that the framework is practically implementable and usable. We illustrate the approach with examples using the monad of exceptions and the one of nondeterminism and expressions both with and without handlers.

0.10

Logical Relations on Display

cs.PL cs.LO ·2026-11-16 ·Steven Schaefer, Johnson He, Max S. New
top venue similarity 0.59
Abstract · 31 pages, 3 figures, to appear at POPL 2027

The metatheory of programming languages suffers from a lack of reuse. Researchers develop individual calculi and prove standard properties, but very few results are truly reused across papers. The problem is worse in proof assistants, where developments routinely duplicate code from prior work or rebuild it from scratch. Category theory provides the most promising path toward reusable programming language semantics. Universal properties capture the type connectives---products, functions, sums---together with their $β$/$η$ laws. Free categorical structures identify syntactic calculi. \emph{Displayed} categories provide a uniform language for specifying logical relations, and general theorems about fibrations allow their structure to be assembled compositionally. In this work we develop a library of formalized category theory in the Cubical Agda proof assistant directly applicable to programming language metatheory. We develop theories of universal properties and free categorical structures, apply them to define denotational semantics and logical relations for simply typed calculi, and identify encodings of the categorical constructions that make typechecking them tractable. From the same categorical components, we construct several familiar results via a logical relations construction---canonicity,parametricity,conservativity---and provide a proof of coherence for monoidal categories.

0.52

Arbitrary Functors as Modalities in a Linear Calculus

cs.PL ·2026-10-16 ·Jean-Philippe Bernardy, Andreas Abel
similarity 0.59
Abstract

We study modalities in the linear lambda calculus, by interpreting them as endofunctors in monoidal closed categories. We support functors that do not distribute over products, including (co)monads. We also support arbitrary natural transformations as conversion between modalities. We provide a generic categorical semantics, which we then specialise to a sound and complete resource semantics. We use this resource semantics to derive normalisation by evaluation. Along the way, we describe several applications of such models. This work aims at providing a foundation for future programming languages with modalities. The paper is backed by a mechanisation in Agda.

0.15

Fibered Separation Logic: Weakest Preconditions, Universal Constructions, and Local Independence

cs.PL cs.LO ·2026-11-05 ·John M. Li, Ryan Doenges, Pedro H. Azevedo de Amorim
similarity 0.58
Abstract · 41 pages, 5 figures

This paper introduces a categorical framework for models of higher-order separation logic including the weakest precondition modality. Weakest preconditions are interpreted by strong monads on a category fibered over a model of Moggi's computational lambda calculus. The fibered categories in question are termed bunched fibrations and shown to be equivalent to BI hyperdoctrines. Well-known heuristic techniques for obtaining weakest preconditions are shown to be expressible in categorical terms and are proved sound. The ``baking in the frame rule'' trick is shown to satisfy a universal property. Constructions are given for extending a program logic with cost credits. Our largest case study is parametrized by a category having local independent product (LIP) structure, a notion due to Simpson that axiomatizes name generation, randomness, and local state. From an LIP category, we construct an allocation monad, a bunched fibration, and a monad lifting. We instantiate our construction to obtain a novel probabilistic separation logic for measure-theoretic probability that both simplifies and clarifies prior work.

0.31