Evolving the Incremental {\lambda} Calculus into a Model of Forward Automatic Differentiation (AD)

Preprint, Conference object English OPEN
Kelly, Robert ; Pearlmutter, Barak A. ; Siskind, Jeffrey Mark (2016)
  • Subject: Computer Science - Programming Languages | Computer Science - Logic in Computer Science

Formal transformations somehow resembling the usual derivative are surprisingly common in computer science, with two notable examples being derivatives of regular expressions and derivatives of types. A newcomer to this list is the incremental $\lambda$-calculus, or ILC... View more
  • References (9)

    [1] Janusz A. Brzozowski. Derivatives of regular expressions. Journal of the ACM (JACM), 11(4):481, 1964.

    [2] Conor McBride. The derivative of a regular type is its type of one-hole contexts, 2001. URL http://strictlypositive.org/diff.pdf. Available online.

    [3] Michael Abbott, Neil Ghani, Thorsten Altenkirch, and Conor Mcbride. ∂ for data: Differentiating data structures. Fundamenta Informaticae, 65(1-2):1-28, August 2004. URL http://strictlypositive.org/dfordata.pdf.

    [4] Yufei Cai, Paolo G. Giarrusso, Tillmann Rendel, and Klaus Ostermann. A theory of changes for higher-order languages: Incrementalizing λ-calculi by static differentiation. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 145-55, 2014. doi: 10.1145/2594291.2594304. URL https://inc-lc.github.io/resources/pldi14-ilc-author-final.pdf. See arXiv:1312.0658.

    [5] Oleksandr Manzyuk. A simply typed λ-calculus of forward automatic differentiation. In Mathematical Foundations of Programming Semantics Twenty-eighth Annual Conference, pages 259-73, Bath, UK, June 6-9 2012. URL http://dauns.math.tulane.edu/~mfps/mfps28proc.pdf.

    [6] Thomas Ehrhard and Laurent Regnier. The differential lambda-calculus. Theoretical Computer Science, 309(1-3):1-41, December 2003.

    [7] William Kingdon Clifford. Preliminary sketch of bi-quaternions. Proceedings of the London Mathematical Society, 4:381-95, 1873.

    [8] Jeffrey Mark Siskind and Barak A. Pearlmutter. Nesting forward-mode AD in a functional framework. Higher-Order and Symbolic Computation, 21(4):361-76, 2008. doi: 10.1007/s10990-008-9037-1.

    [9] Oleksandr Manzyuk, Barak A. Pearlmutter, Alexey Andreyevich Radul, David R. Rush, and Jeffrey Mark Siskind. Confusion of tagged perturbations in forward automatic differentiation of higher-order functions. Higher-Order and Symbolic Computation, 2015. To appear. See also arXiv:1211.4892.

  • Metrics
    No metrics available