Document Open Access Logo

Analytical Differential Calculus with Integration

Authors Han Xu, Zhenjiang Hu

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.143.pdf
  • Filesize: 0.64 MB
  • 20 pages

Document Identifiers

Author Details

Han Xu
  • Department of Computer Science and Technology, Peking University, Beijing, China
Zhenjiang Hu
  • Key Laboratory of High Confidence Software Technologies (MoE), Department of Computer Science and Technology, Peking University, Beijing, China

Cite AsGet BibTex

Han Xu and Zhenjiang Hu. Analytical Differential Calculus with Integration. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 143:1-143:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.143

Abstract

Differential lambda-calculus was first introduced by Thomas Ehrhard and Laurent Regnier in 2003. Despite more than 15 years of history, little work has been done on a differential calculus with integration. In this paper, we shall propose a differential calculus with integration from a programming point of view. We show its good correspondence with mathematics, which is manifested by how we construct these reduction rules and how we preserve important mathematical theorems in our calculus. Moreover, we highlight applications of the calculus in incremental computation, automatic differentiation, and computation approximation.

Subject Classification

ACM Subject Classification
  • Software and its engineering → General programming languages
  • Software and its engineering → Functional languages
Keywords
  • Differential Calculus
  • Integration
  • Lambda Calculus
  • Incremental Computation
  • Adaptive Computing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Martín Abadi and Gordon D. Plotkin. A simple differentiable programming language. Proceedings of the ACM on Programming Languages, 4(POPL):1–28, January 2020. URL: https://doi.org/10.1145/3371106.
  2. Umut A. Acar, Amal Ahmed, and Matthias Blume. Imperative self-adjusting computation. In George C. Necula and Philip Wadler, editors, Proceedings of the 35th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2008, San Francisco, California, USA, January 7-12, 2008, pages 309-322. ACM, 2008. Google Scholar
  3. Umut A. Acar, Guy E. Blelloch, and Robert Harper. Adaptive functional programming. In John Launchbury and John C. Mitchell, editors, Conference Record of POPL 2002: The 29th SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Portland, OR, USA, January 16-18, 2002, pages 247-259. ACM, 2002. Google Scholar
  4. Mario Alvarez-Picallo, Alex Eyers-Taylor, Michael Peyton Jones, and C.-H. Luke Ong. Fixing incremental computation - derivatives of fixpoints, and the recursive semantics of datalog. In Luís Caires, editor, Programming Languages and Systems - 28th European Symposium on Programming, ESOP 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Prague, Czech Republic, April 6-11, 2019, Proceedings, volume 11423 of Lecture Notes in Computer Science, pages 525-552. Springer, 2019. Google Scholar
  5. Mario Alvarez-Picallo and C. H. Luke Ong. The difference lambda-calculus: A language for difference categories, 2020. URL: http://arxiv.org/abs/2011.14476.
  6. Atilim Gunes Baydin, Barak A. Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind. Automatic differentiation in machine learning: a survey. J. Mach. Learn. Res., 18:153:1-153:43, 2017. Google Scholar
  7. Yufei Cai, Paolo G. Giarrusso, Tillmann Rendel, and Klaus Ostermann. A theory of changes for higher-order languages: incrementalizing λ-calculi by static differentiation. In Michael F. P. O'Boyle and Keshav Pingali, editors, ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '14, Edinburgh, United Kingdom - June 09 - 11, 2014, pages 145-155. ACM, 2014. Google Scholar
  8. Thomas Ehrhard. An introduction to differential linear logic: proof-nets, models and antiderivatives. Math. Struct. Comput. Sci., 28(7):995-1060, 2018. Google Scholar
  9. Thomas Ehrhard and Laurent Regnier. The differential lambda-calculus. Theor. Comput. Sci., 309(1-3):1-41, 2003. Google Scholar
  10. Conal Elliott. The simple essence of automatic differentiation. Proc. ACM Program. Lang., 2(ICFP):70:1-70:29, 2018. Google Scholar
  11. Paolo G. Giarrusso, Yann Régis-Gianas, and Philipp Schuster. Incremental backslashlambda -calculus in cache-transfer style - static memoization by program transformation. In Luís Caires, editor, Programming Languages and Systems - 28th European Symposium on Programming, ESOP 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Prague, Czech Republic, April 6-11, 2019, Proceedings, volume 11423 of Lecture Notes in Computer Science, pages 553-580. Springer, 2019. Google Scholar
  12. Andreas Griewank and Andrea Walther. Evaluating derivatives - principles and techniques of algorithmic differentiation, Second Edition. SIAM, 2008. Google Scholar
  13. Robert Kelly, Barak A. Pearlmutter, and Jeffrey Mark Siskind. Evolving the incremental λ calculus into a model of forward automatic differentiation (AD). CoRR, abs/1611.03429, 2016. URL: http://arxiv.org/abs/1611.03429.
  14. Christoph Koch. Incremental query evaluation in a ring of databases. In Jan Paredaens and Dirk Van Gucht, editors, Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2010, June 6-11, 2010, Indianapolis, Indiana, USA, pages 87-98. ACM, 2010. Google Scholar
  15. Alp Kucukelbir, Dustin Tran, Rajesh Ranganath, Andrew Gelman, and David M. Blei. Automatic differentiation variational inference. J. Mach. Learn. Res., 18:14:1-14:45, 2017. Google Scholar
  16. Per-Åke Larson and Jingren Zhou. Efficient maintenance of materialized outer-join views. In Rada Chirkova, Asuman Dogac, M. Tamer Özsu, and Timos K. Sellis, editors, Proceedings of the 23rd International Conference on Data Engineering, ICDE 2007, The Marmara Hotel, Istanbul, Turkey, April 15-20, 2007, pages 56-65. IEEE Computer Society, 2007. Google Scholar
  17. Yanhong A. Liu. Efficiency by incrementalization: An introduction. High. Order Symb. Comput., 13(4):289-313, 2000. URL: https://doi.org/10.1023/A:1026547031739.
  18. Oleksandr Manzyuk. A simply typed λ-calculus of forward automatic differentiation. Electronic Notes in Theoretical Computer Science, 286:257-272, 2012. Proceedings of the 28th Conference on the Mathematical Foundations of Programming Semantics (MFPS XXVIII). Google Scholar
  19. Robert Paige and Shaye Koenig. Finite differencing of computable expressions. ACM Trans. Program. Lang. Syst., 4(3):402-454, 1982. Google Scholar
  20. Benjamin C. Pierce. Types and Programming Languages. The MIT Press, 2002. Google Scholar
  21. Jeffrey Mark Siskind and Barak A. Pearlmutter. Nesting forward-mode AD in a functional framework. High. Order Symb. Comput., 21(4):361-376, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact