  How does one compile derivatives of tensor programs, such that the resulting
code is purely functional (hence easier to optimize and parallelize) and
provably efficient relative to the original program? We show that naively
differentiating tensor code---as done in popular systems like Tensorflow and
PyTorch---can cause asymptotic slowdowns in pathological cases, violating the
Cheap Gradients Principle. However, all existing automatic differentiation
methods that guarantee this principle (for variable size data) do so by relying
on += mutation through aliases/pointers---which complicates downstream
optimization. We provide the first purely functional, provably efficient,
adjoint/reverse-mode derivatives of array/tensor code by explicitly accounting
for sparsity. We do this by focusing on the indicator function from Iverson's
APL. We also introduce a new "Tensor SSA" normal form and a new derivation of
reverse-mode automatic differentiation based on the universal property of
inner-products.
