Fernando Lucatelli Nunes

Fernando Lucatelli Nunes, Diogo Simm, Matthijs Vákár

Reverse-mode automatic differentiation is commonly given a denotational account in which each source type has a single cotangent type. Variant types obstruct this simply typed representation because the valid cotangent space depends on the branch selected at run time. Existing correctness results therefore use primal-indexed families of cotangent spaces, whose natural internal language is dependently typed. We show that the same dependency can be represented in an ordinary nondependent target. The cotangent fibres of each source type are embedded in a common ambient type, and a primal-indexed idempotent selects the valid fibre. Semantically, this amounts to passing from the constant-family model to its Karoubi completion. For a category $\mathcal C$ and a regular infinite cardinal $κ$, we prove that the constant-family inclusion extends to an equivalence $\mathrm{Kar}(\mathrm{Copow}*κ(\mathcal C)) \simeq \mathrm{Fam}*κ(\mathcal C)$ precisely when $\mathcal C$ is Cauchy complete and every $κ$-small family admits a common retract host. We also construct the resulting coproducts explicitly. Applying this theorem, we obtain a bicartesian closed semantics for reverse-mode automatic differentiation with variants using only ordinary target types, projectors, and backpropagators. Splitting the generated idempotents recovers the established dependent semantics. Thus dependent cotangent families and simply typed ambient cotangents equipped with projectors are equivalent presentations of the same denotational transformation.

Diogo Simm, Fernando Lucatelli Nunes, Matthijs Vákár

We analyse reverse-mode automatic differentiation (AD) for discrete probabilistic programs. Our construction is formulated in the framework of Combinatory Homomorphic Automatic Differentiation (CHAD), treating AD as a structure-preserving transformation of programs, guided by a denotational semantics. The main case study is the finite atomic distribution monad, whose computations have finite support and differentiable weights. The key point is that differentiating probabilistic programs requires cotangents to flow backwards not only through deterministic computations, but also through the probabilistic structure itself. We define the corresponding reverse-mode code transformation and prove its correctness, for handled real-output programs, by a categorical logical-relations argument. Although the paper focuses on finite discrete probability, the construction gives a reusable pattern for differentiating discrete-output algebraic effects, including finite multiset non-determinism (e.g., from fork-join parallelism), exceptions, and writer-style accumulation (e.g., for in-place accumulation of high-dimensional vectors). More broadly, we view this work as a foundational step towards extending CHAD to richer probabilistic languages and to other algebraic effects with handlers.

Fernando Lucatelli Nunes, Matthijs Vákár

We study the composite free completion Dist(C) := Fam(Fam(C^op)^op), obtained by first freely adjoining small products and then freely adjoining small coproducts. A natural pseudodistributive law equips this endo-pseudofunctor with a composite pseudomonad structure. Its pseudoalgebras are precisely the categories with small products and small coproducts in which small products distribute over small coproducts. We call such categories doubly-infinitary distributive. This condition is natural, but does not seem to have been systematically isolated in the literature. Thus Dist(C) is the free doubly-infinitary distributive category on C. Our main result is that Dist(C) is cartesian closed. Finally, we compare doubly-infinitary distributivity with extensivity, ordinary infinitary distributivity, and cartesian closedness by means of separating examples.

Fernando Lucatelli Nunes, Gordon Plotkin, Matthijs Vákár

Combinatory Homomorphic Automatic Differentiation (CHAD) was originally formulated as a semantics-driven source-to-source transformation for reverse-mode AD of total (terminating) functional programs. In this work, we extend CHAD to encompass programs featuring constructs such as partial (potentially non-terminating) operations, data-dependent conditionals (e.g., real-valued tests), and iteration constructs (i.e. while-loops), while maintaining CHAD's core principle of structure-preserving semantics. A central contribution is the introduction of iteration-extensive indexed categories, which provide a principled integration of iteration into dependently typed programming languages. This integration is achieved by requiring that iteration in the base category lifts to parameterized initial algebras in the indexed category, yielding an op-fibred iterative structure that models while-loops and other iteration constructs in the total category, which corresponds to the category of containers of our dependently typed language. Through the idea of iteration-extensive indexed categories, we extend the CHAD transformation to looping programs as the unique structure-preserving functor in a suitable sense. Specifically, it is the unique iterative Freyd category morphism from the iterative Freyd category corresponding to the source language to the category of containers obtained from the target language, such that each primitive operation is mapped to its (transposed) derivative. We establish the correctness of this extended transformation via the universal property of the syntactic categorical model of the source language, showing that the differentiated programs compute correct reverse-mode derivatives of their originals.