  We apply program verification technology to the problem of specifying and
verifying automatic differentiation (AD) algorithms. We focus on define-by-run,
a style of AD where the program that must be differentiated is executed and
monitored by the automatic differentiation algorithm. We begin by asking, "what
is an implementation of AD?" and "what does it mean for an implementation of AD
to be correct?" We answer these questions both at an informal level, in precise
English prose, and at a formal level, using types and logical assertions. After
answering these broad questions, we focus on a specific implementation of AD,
which involves a number of subtle programming-language features, including
dynamically allocated mutable state, first-class functions, and effect
handlers. We present a machine-checked proof, expressed in a modern variant of
Separation Logic, of its correctness. We view this result as an advanced
exercise in program verification, with potential future applications to the
verification of more realistic automatic differentiation systems and of other
software components that exploit delimited-control effects.
