March 2009

Appeared in ICFP 2009

Abstract

Automatic differentiation (AD) is a precise, efficient, and convenient method for computing derivatives of functions. Its forward-mode implementation can be quite simple even when extended to compute all of the higher-order derivatives as well. The higher-dimensional case has also been tackled, though with extra complexity. This paper develops an implementation of higher-dimensional, higher-order, forward-mode AD in the extremely general and elegant setting of calculus on manifolds and derives that implementation from a simple and precise specification.

In order to motivate and discover the implementation, the paper poses the question “What does AD mean, independently of implementation?” An answer arises in the form of naturality of sampling a function and its derivative. Automatic differentiation flows out of this naturality condition, together with the chain rule. Graduating from first-order to higher-order AD corresponds to sampling all derivatives instead of just one. Next, the setting is expanded to arbitrary vector spaces, in which derivative values are linear maps. The specification of AD adapts to this elegant and very general setting, which even simplifies the development.

Versions:

See also:

BibTex

@InProceedings{Elliott2009-beautiful-differentiation,
  author    = {Conal Elliott},
  title     = {Beautiful differentiation},
  booktitle = "International Conference on Functional Programming (ICFP)",
  year      = 2009,
  url       = {http://conal.net/papers/beautiful-differentiation},
}

Errata

Errors and corrections are listed here as they’re reported and fixed.

Version 2009/02/23

Thanks to Anonymous, Barak Pearlmutter, Mark Rafter, and Paul Liu.

Version 2009/02/27

Thanks to Freddie Manners and Jared Updike.

Version 2009/03/01

Thanks to Vincent Kraeutler.

Version 2010/12/22

Thanks to Yrogirg

Version 2010/03/16

Version 2010/04/21

Version 2010/03/16

Thanks to Kirstin Rhys.