# Towards Denotational Semantics of AD for Higher-Order, Recursive, Probabilistic Languages

Source: [Towards Denotational Semantics of AD for Higher-Order, Recursive, Probabilistic Languages](<https://www.sota2.com/research/paper/68fa6b651e209131cea2e0a7>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T23:48:06.915Z

Authors: Alexander K. Lew, Mathieu Huot, Vikash K. Mansinghka

Published: 2021-11-30T14:55:11.000Z

## Abstract

Automatic differentiation (AD) aims to compute derivatives of user-defined functions, but in Turing-complete languages, this simple specification does not fully capture AD's behavior: AD sometimes disagrees with the true derivative of a differentiable program, and when AD is applied to non-differentiable or effectful programs, it is unclear what guarantees (if any) hold of the resulting code. We study an expressive differentiable programming language, with piecewise-analytic primitives, higher-order functions, and general recursion. Our main result is that even in this general setting, a version of Lee et al. \[2020\]'s correctness theorem (originally proven for a first-order language without partiality or recursion) holds: all programs denote so-called $\\omega$PAP functions, and AD computes correct intensional derivatives of them. Mazza and Pagani \[2021\]'s recent theorem, that AD disagrees with the true derivative of a differentiable recursive program at a measure-zero set of inputs, can be derived as a straightforward corollary of this fact. We also apply the framework to study probabilistic programs, and recover a recent result from Mak et al. \[2021\] via a novel denotational argument.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2111.15456>)

[PDF](<https://arxiv.org/pdf/2111.15456.pdf>)
