Incremental Computation: What Is the Essence?
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914090836819968 |
|---|---|
| author | Liu, Yanhong A. |
| author_facet | Liu, Yanhong A. |
| contents | Incremental computation aims to compute more efficiently on changed input by reusing previously computed results. We give a high-level overview of works on incremental computation, and highlight the essence underlying all of them, which we call incrementalization -- the discrete counterpart of differentiation in calculus. We present the gist of a systematic method for incrementalization, and a systematic method centered around it -- called Iterate-Incrementalize-Implement -- for program design and optimization, as well as algorithm design and optimization. We illustrate the methods with example applications in arithmetic computations, recursive functions, graph analysis, and distributed algorithms. At a meta-level, with historical contexts and for future directions, we stress the power of high-level data, control, and module abstractions in developing new and better algorithms and programs as well as their precise complexities. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_07946 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Incremental Computation: What Is the Essence? Liu, Yanhong A. Programming Languages Incremental computation aims to compute more efficiently on changed input by reusing previously computed results. We give a high-level overview of works on incremental computation, and highlight the essence underlying all of them, which we call incrementalization -- the discrete counterpart of differentiation in calculus. We present the gist of a systematic method for incrementalization, and a systematic method centered around it -- called Iterate-Incrementalize-Implement -- for program design and optimization, as well as algorithm design and optimization. We illustrate the methods with example applications in arithmetic computations, recursive functions, graph analysis, and distributed algorithms. At a meta-level, with historical contexts and for future directions, we stress the power of high-level data, control, and module abstractions in developing new and better algorithms and programs as well as their precise complexities. |
| title | Incremental Computation: What Is the Essence? |
| topic | Programming Languages |
| url | https://arxiv.org/abs/2312.07946 |