POPL 2025 (series) / LAFI 2025 (series) / LAFI 2025 /
Data-Parallel Differentiation by Optic Composition
We give data-parallel datastructures and algorithms for computing reverse derivatives by optic composition. Given a symmetric monoidal category presented by generators and operations as well as a choice of derivative for each operation, we give an algorithm to transform a morphism into its reverse derivative. This algorithm is data-parallel: it runs in time logarithmic in the size of the morphism on a PRAM machine, and linear time on a sequential machine.