Lune

POPL2023Top-tier venue

Efficient Dual-Numbers Reverse AD via Well-Known Program Transformations

Tom Smeding, Matthijs Vákár

Abstract

Where dual-numbers forward-mode automatic differentiation (AD) pairs each scalar value with its tangent value, dual-numbers reverse-mode AD attempts to achieve reverse AD using a similarly simple idea: by pairing each scalar value with a backpropagator function. Its correctness and efficiency on higher-order input languages have been analysed by Brunel, Mazza and Pagani, but this analysis used a custom operational semantics for which it is unclear whether it can be implemented efficiently. We take inspiration from their use of linear factoring to optimise dual-numbers reverse-mode AD to an algorithm that has the correct complexity and enjoys an efficient implementation in a standard functional language with support for mutable arrays, such as Haskell. Aside from the linear factoring ingredient, our optimisation steps consist of well-known ideas from the functional programming community. We demonstrate the use of our technique by providing a practical implementation that differentiates most of Haskell98. Where previous work on dual numbers reverse AD has required sequentialisation to construct the reverse pass, we demonstrate that we can apply our technique to task-parallel source programs and generate a task-parallel derivative computation.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

4 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • JAX Autodiff from a Linear Logic Perspective cites Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiation
  • JAX Autodiff from a Linear Logic Perspective cites Automatic differentiation in PCF
  • JAX Autodiff from a Linear Logic Perspective cites Backpropagation in the simply typed lambda-calculus with linear negation
  • JAX Autodiff from a Linear Logic Perspective cites A simple differentiable programming language
  • JAX Autodiff from a Linear Logic Perspective cites Efficient CHAD
  • On the Correctness of Automatic Differentiation for Neural Networks with Machine-Representable Parameters cites Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiation
  • On the Correctness of Automatic Differentiation for Neural Networks with Machine-Representable Parameters cites ωPAP Spaces: Reasoning Denotationally About Higher-Order, Recursive Probabilistic and Differentiable Programs
  • On the Correctness of Automatic Differentiation for Neural Networks with Machine-Representable Parameters cites Automatic differentiation in PCF
  • On the Correctness of Automatic Differentiation for Neural Networks with Machine-Representable Parameters cites Backpropagation in the simply typed lambda-calculus with linear negation
  • On the Correctness of Automatic Differentiation for Neural Networks with Machine-Representable Parameters cites A simple differentiable programming language
  • Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiation cites Automatic differentiation in PCF
  • Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiation cites Backpropagation in the simply typed lambda-calculus with linear negation
  • Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiation cites A simple differentiable programming language
  • ωPAP Spaces: Reasoning Denotationally About Higher-Order, Recursive Probabilistic and Differentiable Programs cites Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiation
  • ωPAP Spaces: Reasoning Denotationally About Higher-Order, Recursive Probabilistic and Differentiable Programs cites Automatic differentiation in PCF
  • ωPAP Spaces: Reasoning Denotationally About Higher-Order, Recursive Probabilistic and Differentiable Programs cites Backpropagation in the simply typed lambda-calculus with linear negation
  • Automatic differentiation in PCF cites Backpropagation in the simply typed lambda-calculus with linear negation
  • Automatic differentiation in PCF cites A simple differentiable programming language
  • Efficient CHAD cites Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiation
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers4

  1. On the Correctness of Automatic Differentiation for Neural Networks with Machine-Representable ParametersWonyeol Lee, Sejun Park, Alex AikenICML 2023 · 6 citations
  2. Efficient CHADTom Smeding, Matthijs VákárPOPL 2024 · 6 citations
  3. ωPAP Spaces: Reasoning Denotationally About Higher-Order, Recursive Probabilistic and Differentiable ProgramsMathieu Huot, Alexander K. Lew, Vikash K. Mansinghka, Sam StatonLICS 2023 · 5 citations
  4. JAX Autodiff from a Linear Logic PerspectiveGiulia Giusti, Michele PaganiPOPL 2026

Builds on8

  1. A simple differentiable programming languageMartín Abadi, Gordon D. PlotkinPOPL 2020 · 49 citations
  2. Automatic differentiation in PCFDamiano Mazza, Michele PaganiPOPL 2021 · 47 citations
  3. Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiationFaustyna Krawiec, Simon Peyton Jones, Neel Krishnaswami, Tom Ellis et al.POPL 2022 · 27 citations
  4. Backpropagation in the simply typed lambda-calculus with linear negationAloïs Brunel, Damiano Mazza, Michele PaganiPOPL 2020 · 24 citations
  5. Purity of an ST monad: full abstraction by semantically typed back-translationKoen Jacobs, Dominique Devriese, Amin TimanyOOPSLA 2022 · 13 citations

Related papers

  1. AD for an Array Language with Nested ParallelismRobert Schenck, Ola Rønning, Troels Henriksen, Cosmin E. OanceaSC 2022 · 11 citations
  2. You Only Linearize Once: Tangents Transpose to GradientsAlexey Radul, Adam Paszke, Roy Frostig, Matthew J. Johnson et al.POPL 2023 · 13 citations
  3. Reverse-mode automatic differentiation and optimization of GPU kernels via enzymeWilliam S. Moses, Valentin Churavy, Ludger Paehler, Jan Hückelheim et al.SC 2021 · 50 citations
  4. Compositional Taylor expansion in cartesian differential categoriesAymeric WalchLICS 2025
  5. ParDiff: Efficiently Parallelizing Reverse-Mode Automatic Differentiation with Direct IndexingShuhong Huang, Shizhi Tang, Yuan Wen, Huanqi Cao et al.PPoPP 2026
Dusk over the sea between two cliffs drawn in fine vertical lines