Static caching for incremental computation
Yanhong A. Liu, Scott D. Stoller, and Tim Teitelbaum
Abstract:
A systematic approach is given for deriving incremental programs that
exploit caching. The cache-and-prune method presented in the
article consists of three stages: (I) the original program is extended to
cache the results of all its intermediate subcomputations as well as the
final result, (II)) the extended program is incrementalized so that
computation on a new input can use all intermediate results on an old
input, and (III) unused results cached by the extended program and
maintained by the incremental program are pruned away, leaving a pruned
extended program that caches only useful intermediate results and a pruned
incremental program that uses and maintains only useful results. All
three stages utilize static analyses and semantics-preserving
transformations. Stages I and III are simple, clean, and fully
automatable. The overall method has a kind of optimality with respect to
the techniques used in Stage II. The method can be applied
straightfowardly to provide a systematic approach to program improvement
via caching.
Scott Stoller's Home Page