Article

Dynamic Programming via Static Incrementalization

Authors:

Yanhong A. Liu,

Scott D. StollerAuthors Info & Claims

ESOP '99: Proceedings of the 8th European Symposium on Programming Languages and Systems

Pages 288 - 305

Published: 22 March 1999 Publication History

Abstract

Dynamic programming is an important algorithm design technique. It is used for solving problems whose solutions involve recursively solving subproblems that share subsubproblems. While a straightforward recursive program solves common subsubproblems repeatedly and often takes exponential time, a dynamic programming algorithm solves every subsubproblem just once, saves the result, reuses it when the subsubproblem is encountered again, and takes polynomial time. 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. The principle underlying incrementalization is general 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 and applied to numerous problems and succeeded on all of them.

References

[1]

M. Abadi, B. Lampson, and J.-J. LÉvy. Analysis and caching of dependencies. In Proceedings of the 1996 ACM SIGPLAN International Conference on Functional Programming. ACM, New York, May 1996.

[2]

A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974.

[3]

F. L. Bauer, B. Möller, H. Partsch, and P. Pepper. Formal program construction by transformations--Computer-aided, intuition-guided programming. IEEE Trans. Softw. Eng., 15(2):165-180, Feb. 1989.

[4]

R. E. Bellman. Dynamic Programming. Princeton University Press, Princeton, New Jersey, 1957.

[5]

R. S. Bird. Tabulation techniques for recursive programs. ACM Comput. Surv., 12(4):403-417, Dec. 1980.

[6]

R. S. Bird. The promotion and accumulation strategies in transformational programming. ACM Trans. Program. Lang. Syst., 6(4):487-504, Oct. 1984.

[7]

R. S. Bird and O. de Moor. From dynamic programming to greedy algorithms. In B. Möller, H. Partsch, and S. Schuman, editors, Formal Program Development, volume 755 of Lecture Notes in Computer Science, pages 43-61. Springer-Verlag, Berlin, 1993.

[8]

E. A. Boiten. Improving recursive functions by inverting the order of evaluation. Sci. Comput. Program., 18(2):139-179, Apr. 1992.

[9]

R. M. Burstall and J. Darlington. A transformation system for developing recursive programs. J. ACM, 24(1):44-67, Jan. 1977.

[10]

W.-N. Chin. Towards an automated tupling strategy. In Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, pages 119-132. ACM, New York, June 1993.

[11]

W.-N. Chin and M. Hagiya. A bounds inference method for vector-based memoization. In ICFP 1997 {23}, pages 176-187.

[12]

W.-N. Chin and S.-C. Khoo. Tupling functions with multiple recursion parameters. In P. Cousot, M. Falaschi, G. Filè, and A. Rauzy, editors, Proceedings of the 3rd International Workshop on Static Analysis, volume 724 of Lecture Notes in Computer Science, pages 124-140. Springer-Verlag, Berlin, Sept. 1993.

[13]

N. H. Cohen. Eliminating redundant recursive calls. ACM Trans. Program. Lang. Syst., 5(3):265-299, July 1983.

[14]

T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. The MIT Press/McGraw-Hill, 1990.

[15]

S. Curtis. Dynamic programming: A different perspective. In R. Bird and L. Meertens, editors, Algorithmic Languages and Calculi, pages 1-23. Chapman & Hall, London, U.K., 1997.

[16]

O. de Moor. A generic program for sequential decision processes. In M. Hermenegildo and D. S. Swierstra, editors, Programming Languages: Implementations, Logics, and Programs, volume 982 of Lecture Notes in Computer Science, pages 1-23. Springer-Verlag, Berlin, 1995.

[17]

O. de Moor and J. Gibbons. Bridging the algorithm gap: A linear-time functional program for paragraph formatting. Technical Report CMS-TR-97-03, School of Computing and Mathematical Sciences, Oxford Brookes University, July 1997.

[18]

J. Field and T. Teitelbaum. Incremental reduction in the lambda calculus. In Proceedings of the 1990 ACM Conference on LISP and Functional Programming, pages 307-322. ACM, New York, June 1990.

[19]

D. P. Friedman, D. S. Wise, and M. Wand. Recursive programming through table look-up. In Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation, pages 85-89. ACM, New York, 1976.

[20]

Y. Futamura and K. Nogi. Generalized partial evaluation. In B. Bjørner, A. P. Ershov, and N. D. Jones, editors, Partial Evaluation and Mixed Computation, pages 133-151. North-Holland, Amsterdam, 1988.

[21]

Z. Hu, H. Iwasaki, M. Takeichi, and A. Takano. Tupling calculation eliminates multiple data traversals. In ICFP 1997 {23}, pages 164-175.

[22]

J. Hughes. Lazy memo-functions. In Proceedings of the 2nd Conference on Functional Programming Languages and Computer Architecture, volume 201 of Lecture Notes in Computer Science, pages 129-146. Springer-Verlag, Berlin, Sept. 1985.

[23]

Proceedings of the 1997 ACM SIGPLAN International Conference on Functional Programming. ACM, New York, June 1997.

[24]

R. M. Keller and M. R. Sleep. Applicative caching. ACM Trans. Program. Lang. Syst., 8(1):88-108, Jan. 1986.

[25]

H. Khoshnevisan. Efficient memo-table management strategies. Acta Informatica, 28(1):43-81, 1990.

[26]

Y. A. Liu. CACHET: An interactive, incremental-attribution-based program transformation system for deriving incremental programs. In Proceedings of the 10th Knowledge-Based Software Engineering Conference, pages 19-26. IEEE CS Press, Los Alamitos, Calif., Nov. 1995.

[27]

Y. A. Liu. Principled strength reduction. In R. Bird and L. Meertens, editors, Algorithmic Languages and Calculi, pages 357-381. Chapman & Hall, London, U.K., 1997.

[28]

Y. A. Liu. Dependence analysis for recursive data. In Proceedings of the IEEE 1998 International Conference on Computer Languages, pages 206-215. IEEE CS Press, Los Alamitos, Calif., May 1998.

[29]

Y. A. Liu and G. Gómez. Automatic accurate time-bound analysis for high-level languages. In Proceedings of the ACM SIGPLAN 1998 Workshop on Languages, Compilers, and Tools for Embedded Systems, volume 1474 of Lecture Notes in Computer Science, pages 31-40. Springer-Verlag, June 1998.

[30]

Y. A. Liu and S. D. Stoller. Loop optimization for aggregate array computations. In Proceedings of the IEEE 1998 International Conference on Computer Languages, pages 262-271. IEEE CS Press, Los Alamitos, Calif., May 1998.

[31]

Y. A. Liu, S. D. Stoller, and T. Teitelbaum. Discovering auxiliary information for incremental computation. In Conference Record of the 23rd Annual ACM Symposium on Principles of Programming Languages, pages 157-170. ACM, New York, Jan. 1996.

[32]

Y. A. Liu, S. D. Stoller, and T. Teitelbaum. Static caching for incremental computation. ACM Trans. Program. Lang. Syst., 20(3):546-585, May 1998.

[33]

Y. A. Liu and T. Teitelbaum. Systematic derivation of incremental programs. Sci. Comput. Program., 24(1):1-39, Feb. 1995.

[34]

D. Michie. "memo" functions and machine learning. Nature, 218:19-22, Apr. 1968.

[35]

D. J. Mostow and D. Cohen. Automating program speedup by deciding what to cache. In Proceedings of the 9th International Joint Conference on Artificial Intelligence, pages 165-172. Morgan Kaufmann Publishers, San Francisco, Calif., Aug. 1985.

[36]

R. Paige. Programming with invariants. IEEE Software, pages 56-69, Jan. 1986.

[37]

R. Paige. Symbolic finite differencing--Part I. In Proceedings of the 3rd European Symposium on Programming, volume 432 of Lecture Notes in Computer Science, pages 36-56. Springer-Verlag, Berlin, May 1990.

[38]

R. Paige and S. Koenig. Finite differencing of computable expressions. ACM Trans. Program. Lang. Syst., 4(3):402-454, July 1982.

[39]

H. A. Partsch. Specification and Transformation of Programs--A Formal Approach to Software Development. Springer-Verlag, Berlin, 1990.

[40]

A. Pettorossi. A powerful strategy for deriving efficient programs by transformation. In Conference Record of the 1984 ACM Symposium on LISP and Functional Programming. ACM, New York, Aug. 1984.

[41]

A. Pettorossi and M. Proietti. Rules and strategies for transforming functional and logic programs. ACM Comput. Surv., 28(2):360-414, June 1996.

[42]

A. Pettorossi and M. Proietti. Program derivation via list introduction. In R. Bird and L. Meertens, editors, Algorithmic Languages and Calculi. Chapman & Hall, London, U.K., 1997.

[43]

W. Pugh. An improved cache replacement strategy for function caching. In Proceedings of the 1988 ACM Conference on LISP and Functional Programming, pages 269-276. ACM, New York, July 1988.

[44]

W. Pugh. The Omega Test: A fast and practical integer programming algorithm for dependence analysis. Commun. ACM, 31(8), Aug. 1992.

[45]

W. Pugh and T. Teitelbaum. Incremental computation via function caching. In Conference Record of the 16th Annual ACM Symposium on Principles of Programming Languages, pages 315-328. ACM, New York, Jan. 1989.

[46]

P. W. Purdom and C. A. Brown. The Analysis of Algorithms. Holt, Rinehart and Winston, 1985.

[47]

T. Reps and T. Teitelbaum. The Synthesizer Generator: A System for Constructing Language-Based Editors. Springer-Verlag, New York, 1988.

[48]

W. L. Scherlis. Program improvement by internal specialization. In Conference Record of the 8th Annual ACM Symposium on Principles of Programming Languages, pages 41-49. ACM, New York, Jan. 1981.

[49]

D. R. Smith. KIDS: A semiautomatic program development system. IEEE Trans. Softw. Eng., 16(9):1024-1043, Sept. 1990.

[50]

D. R. Smith. Structure and design of problem reduction generators. In B. Möller, editor, Constructing Programs from Specifications, pages 91-124. North-Holland, Amsterdam, 1991.

[51]

M. Sniedovich. Dynamic Programming. Marcel Dekker, New York, 1992.

[52]

B. Wegbreit. Goal-directed program transformation. IEEE Trans. Softw. Eng., SE-2(2):69-80, June 1976.

Cited By

Liu YStoller SSagonas KMiller D(2003)From datalog rules to efficient programs with time and space guaranteesProceedings of the 5th ACM SIGPLAN international conference on Principles and practice of declaritive programming10.1145/888251.888268(172-183)Online publication date: 27-Aug-2003
https://dl.acm.org/doi/10.1145/888251.888268
Acar UBlelloch GHarper R(2003)Selective memoizationACM SIGPLAN Notices10.1145/640128.60413338:1(14-25)Online publication date: 15-Jan-2003
https://dl.acm.org/doi/10.1145/640128.604133
Acar UBlelloch GHarper RAiken AMorrisett G(2003)Selective memoizationProceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/604131.604133(14-25)Online publication date: 15-Jan-2003
https://dl.acm.org/doi/10.1145/604131.604133
Show More Cited By

Index Terms

Dynamic Programming via Static Incrementalization
1. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

Dynamic Programming via Static Incrementalization

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, ...
Efficiency by Incrementalization: An Introduction

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 ...
Towards Elastic Incrementalization for Datalog
PPDP '21: Proceedings of the 23rd International Symposium on Principles and Practice of Declarative Programming

Various incremental evaluation strategies for Datalog have been developed that reuse computations for small input changes. These methods assume that incrementalization is always a better strategy than recomputation. However, in real-world applications ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ESOP '99: Proceedings of the 8th European Symposium on Programming Languages and Systems

March 1999

304 pages

ISBN:3540656995

Editor:
S. Doaitse Swierstra

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 22 March 1999

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu YStoller SSagonas KMiller D(2003)From datalog rules to efficient programs with time and space guaranteesProceedings of the 5th ACM SIGPLAN international conference on Principles and practice of declaritive programming10.1145/888251.888268(172-183)Online publication date: 27-Aug-2003
https://dl.acm.org/doi/10.1145/888251.888268
Acar UBlelloch GHarper R(2003)Selective memoizationACM SIGPLAN Notices10.1145/640128.60413338:1(14-25)Online publication date: 15-Jan-2003
https://dl.acm.org/doi/10.1145/640128.604133
Acar UBlelloch GHarper RAiken AMorrisett G(2003)Selective memoizationProceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/604131.604133(14-25)Online publication date: 15-Jan-2003
https://dl.acm.org/doi/10.1145/604131.604133
Reps TRall L(2003)Computational Divided Differencing and Divided-Difference ArithmeticsHigher-Order and Symbolic Computation10.1023/A:102302422139116:1-2(93-149)Online publication date: 1-Mar-2003
https://dl.acm.org/doi/10.1023/A%3A1023024221391
Liu YStoller S(2002)Program optimization using indexed and recursive data structuresACM SIGPLAN Notices10.1145/509799.50304137:3(108-118)Online publication date: 14-Jan-2002
https://dl.acm.org/doi/10.1145/509799.503041
Liu YStoller SThiemann P(2002)Program optimization using indexed and recursive data structuresProceedings of the 2002 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation10.1145/503032.503041(108-118)Online publication date: 14-Jan-2002
https://dl.acm.org/doi/10.1145/503032.503041
Marion JMoyen J(2000)Efficient first order functional program interpreter with time bound certificationsProceedings of the 7th international conference on Logic for programming and automated reasoning10.5555/1765236.1765241(25-42)Online publication date: 6-Nov-2000
https://dl.acm.org/doi/10.5555/1765236.1765241
Liu YStoller SLawall J(2000)From recursion to iterationProceedings of the 2000 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation10.1145/328690.328700(73-82)Online publication date: 1-Jan-2000
https://dl.acm.org/doi/10.1145/328690.328700
Liu Y(2000)Efficiency by IncrementalizationHigher-Order and Symbolic Computation10.1023/A:102654703173913:4(289-313)Online publication date: 1-Dec-2000
https://dl.acm.org/doi/10.1023/A%3A1026547031739
Liu YStoller S(1999)From recursion to iterationACM SIGPLAN Notices10.1145/328691.32870034:11(73-82)Online publication date: 1-Nov-1999
https://dl.acm.org/doi/10.1145/328691.328700

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents