Tom Smeding
(Co-)promotors: prof. dr. Gabriele K. Keller (UU) dr. Matthijs I. L. Vákár (UU)
Utrecht University
Date: 12 October 2026
Summary
Purely functional array programming languages, especially second-order ones, are a high-level tool for expressing parallel numerical computations; their explicit structure means that compilers can optimise them very effectively. If such numerical computations require derivatives of functions that are complicated or that are subject to changing requirements, the algorithm of choice for computing those derivatives is usually automatic differentiation (AD), and particularly reverse-mode AD. However, existing fast implementations of reverse-mode AD are generally written for first-order languages – imperative and functional. It turns out to be difficult to design a reverse-mode AD algorithm that not only supports parallel input languages with second-order array operations, but that furthermore has the right complexity and is efficient in practice.
In this thesis, we make progress on this topic by considering two candidate reverse-mode AD algorithms for parallel functional array languages: dual-numbers reverse AD and Combinatory Homomorphic Automatic Differentiation (CHAD). For both algorithms, we discuss theory, intuition, operational characteristics and how to extend them to higher-order parallel functional languages, and we provide perspectives on practical performance. An additional goal of this thesis is to provide a thorough discussion of common issues in reverse-mode AD for a functional programming audience.
As expected, we find an inherent tension between efficiency, simplicity and generalisability of reverse AD algorithms. It seems that dual-numbers reverse AD can be either simple and generalisable, or efficient – not both at the same time. CHAD shows promise for a better trade-off, but more research is needed, especially on the topic of practical efficiency.