article

Nesting forward-mode AD in a functional framework

Authors:

Jeffrey Mark Siskind,

Barak A. PearlmutterAuthors Info & Claims

Higher-Order and Symbolic Computation, Volume 21, Issue 4

Pages 361 - 376

https://doi.org/10.1007/s10990-008-9037-1

Published: 01 December 2008 Publication History

Abstract

We discuss the augmentation of a functional-programming language with a derivative-taking operator implemented with forward-mode automatic differentiation (AD). The primary technical difficulty in doing so lies in ensuring correctness in the face of nested invocation of that operator, due to the need to distinguish perturbations introduced by distinct invocations. We exhibit a series of implementations of a referentially-transparent forward-mode-AD derivative-taking operator, each of which uses a different non-referentially-transparent mechanism to distinguish perturbations. Even though the forward-mode-AD derivative-taking operator is itself referentially transparent, we hypothesize that one cannot correctly formulate this operator as a function definition in current pure dialects of Haskell .

References

[1]

Church, A.: The Calculi of Lambda Conversion. Princeton University Press, Princeton (1941).

Crossref

Google Scholar

[2]

Claessen, K., Sands, D.: Observable sharing for functional circuit description. In: Proc. of Asian Computer Science Conference (ASIAN). Springer, New York (1999).

Google Scholar

[3]

Clifford, W.K.: Preliminary sketch of Bi-quaternions. Proc. Lond. Math. Soc. 4 , 381-95 (1873).

Crossref

Google Scholar

[4]

Flatt, M.: PLT MzScheme: language manual. Technical Report PLT-TR05-1-v300, PLT Scheme Inc. (2005).

Google Scholar

[5]

Karczmarczuk, J.: Functional differentiation of computer programs. In: Proceedings of the III ACM SIGPLAN International Conference on Functional Programming. Baltimore, MD, pp. 195-203 (1998).

Crossref

Google Scholar

[6]

Karczmarczuk, J.: Lazy differential algebra and its applications. In: Workshop, III International Summer School on Advanced Functional Programming. Braga, Portugal (1998).

Google Scholar

[7]

Karczmarczuk, J.: Functional coding of differential forms. In: Scottish Workshop on FP (1999).

Google Scholar

[8]

Karczmarczuk, J.: Functional differentiation of computer programs. Higher-Order Symb. Comput. 14 , 35-57 (2001).

Digital Library

Google Scholar

[9]

Leibnitz, G.W.: A new method for maxima and minima as well as tangents, which is impeded neither by fractional nor irrational quantities, and a remarkable type of calculus for this. Acta Eruditorum (1664).

Google Scholar

[10]

Newton, I.: De quadratura curvarum. In Optiks, 1704 edition. Appendix.

Google Scholar

[11]

Nilsson, H.: Functional automatic differentiation with Dirac impulses. In: Proceedings of the Eighth ACM SIGPLAN International Conference on Functional Programming. Uppsala, Sweden, pp. 153-164. ACM Press, New York (2003).

Digital Library

Google Scholar

[12]

Pearlmutter, B.A., Siskind, J.M.: Lazy multivariate higher-order forward- mode AD. In: Proceedings of the 2007 Symposium on Principles of Programming Languages. Nice, France, pp. 155-160 (2007).

Crossref

Google Scholar

[13]

Sussman, G.J., Wisdom, J., Mayer, M.E.: Structure and Interpretation of Classical Mechanics. MIT Press, Cambridge (2001).

Crossref

Google Scholar

[14]

Wengert, R.E.: A simple automatic derivative evaluation program. Commun. ACM 7 (8), 463-464 (1964).

Digital Library

Google Scholar

Cited By

View all

Vicini DSpeierer SJakob W(2021)Path replay backpropagationACM Transactions on Graphics10.1145/3450626.345980440:4(1-14)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459804
Abadi MPlotkin G(2019)A simple differentiable programming languageProceedings of the ACM on Programming Languages10.1145/33711064:POPL(1-28)Online publication date: 20-Dec-2019
https://dl.acm.org/doi/10.1145/3371106
Shaikhha AFitzgibbon AVytiniotis DPeyton Jones S(2019)Efficient differentiable programming in a functional array-processing languageProceedings of the ACM on Programming Languages10.1145/33417013:ICFP(1-30)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3341701
Show More Cited By

Index Terms

Nesting forward-mode AD in a functional framework
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language types
        Functional languages
2. Theory of computation
  1. Semantics and reasoning
    1. Program reasoning
      1. Program analysis
    2. Program semantics

Recommendations

Exception Handlers in Functional Programming Languages

Constructs for expressing exception handling can greatly help to avoid clutter in code by allowing the programmer to separate the code to handle unusual situations from the code for the normal case. The author proposes a new approach to embed exception ...
Reverse-mode AD in a functional framework: Lambda the ultimate backpropagator

We show that reverse-mode AD (Automatic Differentiation)—a generalized gradient-calculation operator—can be incorporated as a first-class function in an augmented lambda calculus, and therefore into a functional-programming language. Closure is achieved,...
Aspects of applicative programming for file systems (Preliminary Version)
Proceedings of an ACM conference on Language design for reliable software

This paper develops the implications of recent results in semantics for applicative programming. Applying suspended evaluation (call-by-need) to the arguments of file construction functions results in an implicit synchronization of computation and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Higher-Order and Symbolic Computation

Higher-Order and Symbolic Computation Volume 21, Issue 4

December 2008

82 pages

ISSN:1388-3690

Issue’s Table of Contents

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 December 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Vicini DSpeierer SJakob W(2021)Path replay backpropagationACM Transactions on Graphics10.1145/3450626.345980440:4(1-14)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459804
Abadi MPlotkin G(2019)A simple differentiable programming languageProceedings of the ACM on Programming Languages10.1145/33711064:POPL(1-28)Online publication date: 20-Dec-2019
https://dl.acm.org/doi/10.1145/3371106
Shaikhha AFitzgibbon AVytiniotis DPeyton Jones S(2019)Efficient differentiable programming in a functional array-processing languageProceedings of the ACM on Programming Languages10.1145/33417013:ICFP(1-30)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3341701
Wang FZheng DDecker JWu XEssertel GRompf T(2019)Demystifying differentiable programming: shift/reset the penultimate backpropagatorProceedings of the ACM on Programming Languages10.1145/33417003:ICFP(1-31)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3341700
Wang FDecker JWu XEssertel GRompf T(2018)Backpropagation with continuation callbacksProceedings of the 32nd International Conference on Neural Information Processing Systems10.5555/3327546.3327682(10201-10212)Online publication date: 3-Dec-2018
https://dl.acm.org/doi/10.5555/3327546.3327682
Elliott C(2018)The simple essence of automatic differentiationProceedings of the ACM on Programming Languages10.1145/32367652:ICFP(1-29)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1145/3236765
Baydin APearlmutter BRadul ASiskind J(2017)Automatic differentiation in machine learningThe Journal of Machine Learning Research10.5555/3122009.324201018:1(5595-5637)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.5555/3122009.3242010
Elliott C(2017)Compiling to categoriesProceedings of the ACM on Programming Languages10.1145/31102711:ICFP(1-27)Online publication date: 29-Aug-2017
https://dl.acm.org/doi/10.1145/3110271
Hoffmann P(2016)A Hitchhiker's Guide to Automatic DifferentiationNumerical Algorithms10.1007/s11075-015-0067-672:3(775-811)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s11075-015-0067-6
Alnæs MLogg AØlgaard KRognes MWells G(2014)Unified form languageACM Transactions on Mathematical Software10.1145/256663040:2(1-37)Online publication date: 5-Mar-2014
https://dl.acm.org/doi/10.1145/2566630
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Exception Handlers in Functional Programming Languages

Reverse-mode AD in a functional framework: Lambda the ultimate backpropagator

Aspects of applicative programming for file systems (Preliminary Version)

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations