ISSN:
1573-0557
Keywords:
caching
;
incremental computation
;
incremental programs
;
incrementalization
;
program analysis
;
program optimization
;
program transformation
;
programming environments
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract Incremental computation takes advantage of repeated computations on inputs that differ slightly from one another, computing each output efficiently by exploiting the previous output. This paper gives an overview of a general and systematic approach to incrementalization: given a program f and an operation ⊕, the approach yields an incremental program that computes f(x ⊕ y) efficiently by using the result of f(x), the intermediate results of f(x), and auxiliary information of f(x) that can be inexpensively maintained. Since every non-trivial computation proceeds by iteration or recursion, the approach can be used for achieving efficient computation by computing each iteration incrementally using an appropriate incremental program. This approach has applications in interactive systems, optimizing compilers, transformational programming, and many other areas, where problems were previously solved in less general and systematic ways. This paper also describes the design and implementation of CACHET, a prototype system for incrementalization.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1026547031739
Permalink