research-article

Open access

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

Authors:

Barak A. Pearlmutter,

Jeffrey Mark SiskindAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 30, Issue 2

Article No.: 7, Pages 1 - 36

https://doi.org/10.1145/1330017.1330018

Published: 14 March 2008 Publication History

Abstract

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, in that the new operator can be applied to any expression in the augmented language, yielding an expression in that language. This requires the resolution of two major technical issues: (a) how to transform nested lambda expressions, including those with free-variable references, and (b) how to support self application of the AD machinery. AD transformations preserve certain complexity properties, among them that the reverse phase of the reverse-mode AD transformation of a function have the same temporal complexity as the original untransformed function. First-class unrestricted AD operators increase the expressive power available to the numeric programmer, and may have significant practical implications for the construction of numeric software that is robust, modular, concise, correct, and efficient.

References

[1]

Appel, A. W. 1998. SSA is functional programming. ACM SIGPLAN Notices 33, 4 (Apr.), 17--20.

Digital Library

[2]

Christianson, B. 1992. Automatic Hessians by reverse accumulation. IMA J. Numer. Anal. 12, 135--150.

[3]

Corliss, G., Faure, C., Griewank, A., Hascoët, L., and Naumann, U. 2001. Automatic Differentiation: From Simulation to Optimization. Springer-Verlag, New York.

Digital Library

[4]

Griewank, A. 2000. Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. Number 19 in Frontiers in Applied Mathematics. SIAM, Philadelphia, PA.

Digital Library

[5]

Griewank, A., Juedes, D., and Utke, J. 1996. Adol-C, a package for the automatic differentiation of algorithms written in C/C++. ACM Trans. Math. Softw. 22, 2, 131--167.

Digital Library

[6]

Hascoët, L. and Pascual, V. 2004. Tapenade 2.1 user's guide. Rapport technique 300, INRIA, Sophia Antipolis.

[7]

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

Digital Library

[8]

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

[9]

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

[10]

Karczmarczuk, J. 2000a. Adjoint codes in functional framework. http://users.info.unicaen.fr/~karczma/arpap/revdiff.ps.

[11]

Karczmarczuk, J. 2000b. Lazy time reversal, and automatic differentiation. http://users.info.unicaen.fr/~karczma/arpap/revpearl.pdf.

[12]

Karczmarczuk, J. 2001a. Calcul des adjoints et programmation paresseuse. http://users.info. unicaen.fr/~karczma/arpap/jflarev.pdf.

[13]

Karczmarczuk, J. 2001b. Functional differentiation of computer programs. Higher-Ord. Symbol. Comput. 14, 35--57.

Digital Library

[14]

Kedem, G. 1980. Automatic differentiation of computer programs. ACM Trans. Mathemat. Softw. 6, 2, 150--165.

Digital Library

[15]

Kelsey, R., Clinger, W., and Rees, J. 1998. Revised report on the algorithmic language Scheme. Higher-Ord. Symbol. Computat. 11, 1 (Sept.), 7--105.

Digital Library

[16]

Kelsey, R. A. 1995. A correspondence between continuation passing style and static single assignment form. ACM SIGPLAN Notices, Papers from the 1995 ACM SIGPLAN Workshop on Intermediate Representations 30, 3 (Mar.), 13--22.

Digital Library

[17]

Pearlmutter, B. A. 1994. Fast exact multiplication by the Hessian. Neural Computat. 6, 1, 147--160.

Digital Library

[18]

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

Digital Library

[19]

Press, W. H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. P. 1992. Numerical Recipes in C, 2nd ed. Cambridge University Press, New York.

Digital Library

[20]

Rall, L. B. 1981. Automatic Differentiation: Techniques and Applications. Lecture Notes in Computer Science, vol. 120. Springer-Verlag, New York.

[21]

Rumelhart, D. E., Hinton, G. E., and Williams, R. J. 1986. Learning representations by back-propagating errors. Nature 323, 533--536.

[22]

Sabry, A. and Felleisen, M. 1993. Reasoning about programs in continuation-passing style. LISP Symbol. Computat. 6, 3--4, 289--360.

Digital Library

[23]

Siskind, J. M. 1999. Flow-directed lightweight closure conversion. Tech. Rep. 99-190R, NEC Research Institute, Inc.

[24]

Siskind, J. M. and Pearlmutter, B. A. 2005. Perturbation confusion and referential transparency: Correct functional implementation of forward-mode AD. In Implementation and Application of Functional Languages---17th International Workshop, IFL'05, A. Butterfield, Ed. Dublin, Ireland, 1--9. Trinity College Dublin Computer Science Department Tech. Rep. TCD-CS-2005-60.

[25]

Siskind, J. M. and Pearlmutter, B. A. 2008. Nesting forward-mode AD in a functional framework. Higher-Ord. Symb. Computat. To appear.

Digital Library

[26]

Speelpenning, B. 1980. Compiling fast partial derivatives of functions given by algorithms. Ph.D. dissertation, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL.

Digital Library

[27]

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

Digital Library

[28]

Wengert, R. E. 1964. A simple automatic derivative evaluation program. Commun. ACM 7, 8, 463--644.

Digital Library

[29]

Werbos, P. J. 1992. Neural networks, system identification, and control in the chemical process industries. In Handbook of Intelligent Control---Neural, Fuzzy, and Adaptive Approaches, D. A. White and D. A. Sofge, Eds. Van Norstrand Reinhold, Chap. 10. 283--356.

Cited By

Ullrich MHack SLeißa RKluss DAchour SPalsberg J(2025)MimIrADe: Automatic Differentiation in MimIRProceedings of the 34th ACM SIGPLAN International Conference on Compiler Construction10.1145/3708493.3712685(70-80)Online publication date: 25-Feb-2025
https://dl.acm.org/doi/10.1145/3708493.3712685
Leißa RUllrich MMeyer JHack S(2025)MimIR: An Extensible and Type-Safe Intermediate Representation for the DSL AgeProceedings of the ACM on Programming Languages10.1145/37048409:POPL(95-125)Online publication date: 9-Jan-2025
https://dl.acm.org/doi/10.1145/3704840
Bragg NFoster JZucker PEdwards JTaeumel M(2024)Scimitar: Functional Programs as Optimization ProblemsProceedings of the 2024 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3689492.3690051(96-112)Online publication date: 17-Oct-2024
https://dl.acm.org/doi/10.1145/3689492.3690051
Show More Cited By

Index Terms

Reverse-mode AD in a functional framework: Lambda the ultimate backpropagator
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Automatic differentiation
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Functional languages

Recommendations

Deriving interpretations of the gradually-typed lambda calculus
PEPM '14: Proceedings of the ACM SIGPLAN 2014 Workshop on Partial Evaluation and Program Manipulation

Siek and Garcia (2012) have explored the dynamic semantics of the gradually-typed lambda calculus by means of definitional interpreters and abstract machines. The correspondence between the calculus's mathematically described small-step reduction ...
Deriving the full-reducing Krivine machine from the small-step operational semantics of normal order
PPDP '13: Proceedings of the 15th Symposium on Principles and Practice of Declarative Programming

We derive by program transformation Pierre Crégut's full-reducing Krivine machine KN from the structural operational semantics of the normal order reduction strategy in a closure-converted pure lambda calculus. We thus establish the correspondence ...
Mechanized meta-reasoning using a hybrid HOAS/de bruijn representation and reflection
ICFP '06: Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming

We investigate the development of a general-purpose framework for mechanized reasoning about the meta-theory of programming languages. In order to provide a standard, uniform account of a programming language, we propose to define it as a logic in a ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 30, Issue 2

March 2008

217 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/1330017

Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 March 2008

Accepted: 01 September 2007

Revised: 01 May 2007

Received: 01 September 2005

Published in TOPLAS Volume 30, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

63
Total Citations
View Citations
1,431
Total Downloads

Downloads (Last 12 months)337
Downloads (Last 6 weeks)63

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ullrich MHack SLeißa RKluss DAchour SPalsberg J(2025)MimIrADe: Automatic Differentiation in MimIRProceedings of the 34th ACM SIGPLAN International Conference on Compiler Construction10.1145/3708493.3712685(70-80)Online publication date: 25-Feb-2025
https://dl.acm.org/doi/10.1145/3708493.3712685
Leißa RUllrich MMeyer JHack S(2025)MimIR: An Extensible and Type-Safe Intermediate Representation for the DSL AgeProceedings of the ACM on Programming Languages10.1145/37048409:POPL(95-125)Online publication date: 9-Jan-2025
https://dl.acm.org/doi/10.1145/3704840
Bragg NFoster JZucker PEdwards JTaeumel M(2024)Scimitar: Functional Programs as Optimization ProblemsProceedings of the 2024 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3689492.3690051(96-112)Online publication date: 17-Oct-2024
https://dl.acm.org/doi/10.1145/3689492.3690051
Kerjean MPédrot PSobocinski PLago UEsparza J(2024)δ is for DialecticaProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662106(1-13)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662106
Smeding TVákár M(2024)Efficient CHADProceedings of the ACM on Programming Languages10.1145/36328788:POPL(1060-1088)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632878
Schüle MHornung J(2024)Higher-Order SQL Lambda Functions2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00450(5622-5628)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00450
Hakimi MShriraman A(2024)TapeFlow: Streaming Gradient Tapes in Automatic Differentiation2024 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)10.1109/CGO57630.2024.10444805(81-92)Online publication date: 2-Mar-2024
https://doi.org/10.1109/CGO57630.2024.10444805
Shaikhha AHuot MHashemian SGrosser TDubach CSteuwer MXue JOttoni GQuintão Pereira F(2024)A Tensor Algebra Compiler for Sparse DifferentiationProceedings of the 2024 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO57630.2024.10444787(1-12)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1109/CGO57630.2024.10444787
Lucatelli Nunes FVákár M(2024)Automatic differentiation for ML-family languages: Correctness via logical relationsMathematical Structures in Computer Science10.1017/S0960129524000215(1-60)Online publication date: 21-Oct-2024
https://doi.org/10.1017/S0960129524000215
van den Berg BSchrijvers TMcKinna JVandenbroucke A(2024)Forward- or reverse-mode automatic differentiationScience of Computer Programming10.1016/j.scico.2023.103010231:COnline publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1016/j.scico.2023.103010
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents