Incrementalizing Polynomial Functors
Pages 44 - 49
Abstract
Incremental computing promises to lead to faster and more efficient programs by avoiding unnecessary recomputations, but existing approaches are often ad-hoc. We consider a more generic approach to incrementality using the idea of data types as polynomial functors and investigate how this approach can lead to constructions of changes and incrementalizations.
References
[1]
Michael Gordon Abbott, Thorsten Altenkirch, and Neil Ghani. 2005. Containers: Constructing strictly positive types. Theor. Comput. Sci., 342, 1 (2005), 3–27. https://doi.org/10.1016/J.TCS.2005.06.002
[2]
Yufei Cai, Paolo G. Giarrusso, Tillmann Rendel, and Klaus Ostermann. 2014. A theory of changes for higher-order languages: incrementalizing λ -calculi by static differentiation. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’14, Edinburgh, United Kingdom - June 09 - 11, 2014, Michael F. P. O’Boyle and Keshav Pingali (Eds.). ACM, 145–155. https://doi.org/10.1145/2594291.2594304
[3]
Olivier Danvy and Lasse R. Nielsen. 2001. Defunctionalization at Work. In Proceedings of the 3rd international ACM SIGPLAN conference on Principles and practice of declarative programming, September 5-7, 2001, Florence, Italy. ACM, 162–174. https://doi.org/10.1145/773184.773202
[4]
Paolo G. Giarrusso, Yann Régis-Gianas, and Philipp Schuster. 2019. Incremental λ -Calculus in Cache-Transfer Style - Static Memoization by Program Transformation. In 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, Luís Caires (Ed.) (Lecture Notes in Computer Science, Vol. 11423). Springer, 553–580. https://doi.org/10.1007/978-3-030-17184-1_20
[5]
James Koppel. 2019. The Best Refactoring You’ve Never Heard Of. https://www.pathsensitive.com/2019/07/the-best-refactoring-youve-never-heard.html
[6]
Kazutaka Matsuda and Meng Wang. 2015. Applicative bidirectional programming with lenses. In Proceedings of the 20th ACM SIGPLAN International Conference on Functional Programming, ICFP 2015, Vancouver, BC, Canada, September 1-3, 2015, Kathleen Fisher and John H. Reppy (Eds.). ACM, 62–74. https://doi.org/10.1145/2784731.2784750
[7]
Akimasa Morihata. 2018. Incremental computing with data structures. Sci. Comput. Program., 164 (2018), 18–36. https://doi.org/10.1016/J.SCICO.2017.04.001
[8]
Nelson Niu and David I. Spivak. 2023. Polynomial Functors: A Mathematical Theory of Interaction. arxiv:2312.00990.
Recommendations
Data Types with Symmetries and Polynomial Functors over Groupoids
Polynomial functors (over Set or other locally cartesian closed categories) are useful in the theory of data types, where they are often called containers. They are also useful in algebra, combinatorics, topology, and higher category theory, and in this ...
Discrete generalised polynomial functors
ICALP'12: Proceedings of the 39th international colloquium conference on Automata, Languages, and Programming - Volume Part IIWe study generalised polynomial functors between presheaf categories, developing their mathematical theory together with computational applications. The main theoretical contribution is the introduction of discrete generalised polynomial functors, a ...
A formal proof of Hensel's lemma over the p-adic integers
CPP 2019: Proceedings of the 8th ACM SIGPLAN International Conference on Certified Programs and ProofsThe field of p-adic numbers ℚp and the ring of p-adic integers ℤp are essential constructions of modern number theory. Hensel’s lemma, described by Gouvêa as the “most important algebraic property of the p-adic numbers,” shows the existence of roots of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2024 Copyright is held by the owner/author(s). Publication rights licensed to 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 the author(s) 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].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 20 September 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Hessian Ministry of Higher Education, Research, Science and the Arts
- LOEWE
Conference
FTfJP '24
Sponsor:
FTfJP '24: 26th ACM International Workshop on Formal Techniques for Java-like Programs
September 20, 2024
Vienna, Austria
Acceptance Rates
Overall Acceptance Rate 51 of 75 submissions, 68%
Upcoming Conference
ISSTA '25
- Sponsor:
- sigsoft
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 30Total Downloads
- Downloads (Last 12 months)30
- Downloads (Last 6 weeks)6
Reflects downloads up to 22 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in