Higher-Order and Symbolic Computation, 16(1/2)37-62
Dynamic Programming via Static IncrementalizationYanhong A. Liu, Computer Science Department, State University of New York at Stony Brook, Stony Brook, NY 11794, USA
Scott D. Stoller, Computer Science Department, State University of New York at Stony Brook, Stony Brook, NY 11794, USA
|
Abstract: Dynamic programming is an important algorithm design
technique. It is used for problems whose solutions involve recursively
solving subproblems that share subsubproblems. While a straightforward
recursive program solves common subsubproblems repeatedly, a dynamic
programming algorithm solves every subsubproblem just once, saves the
result, and reuses it when the subsubproblem is encountered
again. This can reduce the time complexity from exponential to
polynomial. This paper describes a systematic method for transforming
programs written as straightforward recursions into programs that use
dynamic programming. The method extends the original program to cache
all possibly computed values, incrementalizes the extended program
with respect to an input increment to use and maintain all cached
results, prunes out cached results that are not used in the
incremental computation, and uses the resulting incremental program to
form an optimized new program. Incrementalization statically exploits
semantics of both control structures and data structures and maintains
as invariants equalities characterizing cached results. It provides
the basis of a general method for achieving drastic program
speedups. Compared with previous methods that perform memoization or
tabulation, the method based on incrementalization is more powerful
and systematic. It has been implemented in a prototype system CACHET
and applied to numerous problems and succeeded on all of them.
Keywords: caching, dependence analysis, dynamic programming, incremental computation, incremental update, incrementalization, memoization, program optimization, program transformation, pruning, tabulation, static analysis |
This article can be downloaded [here].
![[picture of journal cover]](../LISP.JPG)