# λS: Computable Semantics for Differentiable Programming with Higher-Order Functions and Datatypes

arXiv: https://arxiv.org/abs/2007.08017 · HTML: https://mlsanity.com/paper/2007.08017/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jul 2020.

## Built on by (most cited first, 8 of 8)

- [Differentiable Physics: A Position Piece](https://mlsanity.com/paper/2109.07573/) (2021)
- [Storchastic: A Framework for General Stochastic Automatic Differentiation](https://mlsanity.com/paper/2104.00428/) (2021)
- [Smoothing Methods for Automatic Differentiation Across Conditional Branches](https://mlsanity.com/paper/2310.03585/) (2023)
- [Probabilistic Programming with Programmable Variational Inference](https://mlsanity.com/paper/2406.15742/) (2024)
- [Automatic Functional Differentiation in JAX](https://mlsanity.com/paper/2311.18727/) (2023)
- [Coarsening Optimization for Differentiable Programming](https://mlsanity.com/paper/2110.02307/) (2021)
- [Differentiable Quantum Programming with Unbounded Loops](https://mlsanity.com/paper/2211.04507/) (2022)
- [Differentiate the Evaluator, Not the Program: An Efficient Runtime Representation for Neuro-Symbolic Learning](https://mlsanity.com/paper/2607.03574/) (2026)

## Abstract (arXiv)

Deep learning is moving towards increasingly sophisticated optimization objectives that employ higher-order functions, such as integration, continuous optimization, and root-finding. Since differentiable programming frameworks such as PyTorch and TensorFlow do not have first-class representations of these functions, developers must reason about the semantics of such objectives and manually translate them to differentiable code. We present a differentiable programming language, λS, that is the first to deliver a semantics for higher-order functions, higher-order derivatives, and Lipschitz but nondifferentiable functions. Together, these features enable λS to expose differentiable, higher-order functions for integration, optimization, and root-finding as first-class functions with automatically computed derivatives. λS's semantics is computable, meaning that values can be computed to arbitrary precision, and we implement λS as an embedded language in Haskell. We use λS to construct novel differentiable libraries for representing probability distributions, implicit surfaces, and generalized parametric surfaces -- all as instances of higher-order datatypes -- and present case studies that rely on computing the derivatives of these higher-order functions and datatypes. In addition to modeling existing differentiable algorithms, such as a differentiable ray tracer for implicit surfaces, without requiring any user-level differentiation code, we demonstrate new differentiable algorithms, such as the Hausdorff distance of generalized parametric surfaces.