Article

Program optimization using indexed and recursive data structures

Authors:

Yanhong A. Liu,

Scott D. StollerAuthors Info & Claims

PEPM '02: Proceedings of the 2002 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation

Pages 108 - 118

https://doi.org/10.1145/503032.503041

Published: 14 January 2002 Publication History

Abstract

This paper describes a systematic method for optimizing recursive functions using both indexed and recursive data structures. The method is based on two critical ideas: first, determining a minimal input increment operation so as to compute a function on repeatedly incremented input; second, determining appropriate additional values to maintain in appropriate data structures, based on what values are needed in computation on an incremented input and how these values can be established and accessed. Once these two are determined, the method extends the original program to return the additional values, derives an incremental version of the extended program, and forms an optimized program that repeatedly calls the incremental program. The method can derive all dynamic programming algorithms found in standard algorithm textbooks. There are many previous methods for deriving efficient algorithms, but none is as simple, general, and systematic as ours.

References

[1]

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

Digital Library

[2]

J. H. Ahrens and G. Finke. Merging and sorting applied to the 0-1 knapsack problem. Operations Research, 23(6):1099-1109, 1975.]]

[3]

F. Bancilhon, D. Maier, Y. Sagiv, and J. D. Ullman. Magic sets and other strange ways to implement logic programs. In Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, pages 1-16. ACM, New York, 1986.]]

Digital Library

[4]

F. L. Bauer and H. Wossner. Algorithmic Language and Program Development. Springer-Verlag, Berlin, 1982.]]

Digital Library

[5]

H. Bernstein. To transpose or not to transpose-performance issues in the use of Java-based XML software for real-world problems. http://www.cs.sunysb.edu/liu/darseminar/msg00005.html, Sept. 2001.]]

[6]

R. Bird and O. de Moor. Algebra of Programming. Prentice-Hall, 1996.]]

Digital Library

[7]

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

Digital Library

[8]

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

Digital Library

[9]

W.-N. Chin and M. Hagiya. A bounds inference method for vector-based memoization. In Proceedings of the 1997 ACM SIGPLAN International Conference on Functional Programming, pages 176-187. ACM, New York, June 1997.]]

Digital Library

[10]

W.-N. Chin and S.-C. Khoo. Tupling functions with multiple recursion parameters. In P. Cousot, M. Falaschi, G. File, 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.]]

Digital Library

[11]

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

Digital Library

[12]

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

Digital Library

[13]

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.]]

Digital Library

[14]

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.]]

Digital Library

[15]

H. Ganzinger and D. McAllester. A new meta-complexity theorem for bottom-up logic programs. In Proceedings of the International Joint Conference on Automated Reasoning, Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2001.]]

Digital Library

[16]

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

Digital Library

[17]

N. Klarlund. MONA Version 1.3 User Manual, Oct. 1998.]]

[18]

Y. A. Liu. Efficiency by incrementalization: An introduction. Higher-Order and Symbolic Computation, 13(4):289-313, Dec. 2000.]]

Digital Library

[19]

Y. A. Liu and S. D. Stoller. Dynamic programming via static incrementalization. In Proceedings of the 8th European Symposium on Programming, volume 1576 of Lecture Notes in Computer Science, pages 288-305. Springer-Verlag, Berlin, Mar. 1999.]]

Digital Library

[20]

Y. A. Liu and S. D. Stoller. From recursion to iteration: what are the optimizations? In Proceedings of the ACM SIGPLAN 2000 Workshop on Partial Evaluation and Semantics-Based Program Manipulation, pages 73-82. ACM, New York, Jan. 2000.]]

Digital Library

[21]

Y. A. Liu and S. D. Stoller. Optimizing Ackermann's function by incrementalization. Technical Report DAR 01-1, Computer Science Department, SUNY Stony Brook, Jan. 2001.]]

[22]

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.]]

Digital Library

[23]

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.]]

Digital Library

[24]

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

Digital Library

[25]

D. McAllester. On the complexity analysis of static analyses. In Proceedings of the 6th International Static Analysis Symposium, volume 1694 of Lecture Notes in Computer Science, pages 312-329. Springer-Verlag, Berlin, Sept. 1999.]]

Digital Library

[26]

J. F. Naughton and R. Ramakrishnan. Bottom-up evaluation of logic programs. In J.-L. Lassez and G. Plotkin, editors, Computational Logic: Essays in Honor of Alan Robinson, pages 640-700. The MIT Press, Cambridge, Mass., 1991.]]

[27]

R. Paige. Real-time simulation of a set machine on a RAM. In Computing and Information, Vol. II, pages 69-73. Canadian Scholars Press, 1989. Proceedings of ICCI '89: The International Conference on Computing and Information, Toronto, Canada, May 23-27, 1989.]]

[28]

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

Digital Library

[29]

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

Digital Library

[30]

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.]]

Digital Library

[31]

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.]]

Digital Library

[32]

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

Digital Library

[33]

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

Digital Library

[34]

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.]]

Digital Library

[35]

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

[36]

D. S. Warren. The XSB tabled logic programming system (abstract). In J. Minker, editor, Workshop on Logic-Based Artificial Intelligence, Washington, DC, June 14-16, 1999, College Park, Maryland, 1999. Computer Science Department, University of Maryland.]]

[37]

A. Webber. Optimization of functional programs by grammar thinning. ACM Trans. Program. Lang. Syst., 17(2):293-330, Mar. 1995.]]

Digital Library

Cited By

Shilov N(2018)Etude on Recursion EliminationModeling and Analysis of Information Systems10.18255/1818-1015-2018-5-549-56025:5(549-560)Online publication date: 28-Oct-2018
https://doi.org/10.18255/1818-1015-2018-5-549-560
Liu YStoller S(2009)From datalog rules to efficient programs with time and space guaranteesACM Transactions on Programming Languages and Systems10.1145/1552309.155231131:6(1-38)Online publication date: 26-Aug-2009
https://dl.acm.org/doi/10.1145/1552309.1552311
Mu SHatcliff JGlück Rde Moor O(2008)Maximum segment sum is backProceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation10.1145/1328408.1328414(31-39)Online publication date: 7-Jan-2008
https://dl.acm.org/doi/10.1145/1328408.1328414
Show More Cited By

Recommendations

Program optimization using indexed and recursive data structures

This paper describes a systematic method for optimizing recursive functions using both indexed and recursive data structures. The method is based on two critical ideas: first, determining a minimal input increment operation so as to compute a function ...
Retroactive data structures

We introduce a new data structuring paradigm in which operations can be performed on a data structure not only in the present, but also in the past. In this new paradigm, called retroactive data structures, the historical sequence of operations ...
Whole-program dynamic software updating

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PEPM '02: Proceedings of the 2002 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation

January 2002

146 pages

ISBN:158113455X

DOI:10.1145/503032

Program Chair:
Peter Thiemann
Univeristy of Freiburg, Germany

ACM SIGPLAN Notices Volume 37, Issue 3
March 2002
142 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/509799
Issue’s Table of Contents

Copyright © 2002 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 January 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PEPM02

Sponsor:

PEPM02: 2002 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation

January 14 - 15, 2002

Oregon, Portland

Acceptance Rates

PEPM '02 Paper Acceptance Rate 11 of 22 submissions, 50%;

Overall Acceptance Rate 66 of 120 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
444
Total Downloads

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

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Shilov N(2018)Etude on Recursion EliminationModeling and Analysis of Information Systems10.18255/1818-1015-2018-5-549-56025:5(549-560)Online publication date: 28-Oct-2018
https://doi.org/10.18255/1818-1015-2018-5-549-560
Liu YStoller S(2009)From datalog rules to efficient programs with time and space guaranteesACM Transactions on Programming Languages and Systems10.1145/1552309.155231131:6(1-38)Online publication date: 26-Aug-2009
https://dl.acm.org/doi/10.1145/1552309.1552311
Mu SHatcliff JGlück Rde Moor O(2008)Maximum segment sum is backProceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation10.1145/1328408.1328414(31-39)Online publication date: 7-Jan-2008
https://dl.acm.org/doi/10.1145/1328408.1328414
Liu YStoller S(2008)Dynamic Programming via Static IncrementalizationAutomatic Program Development10.1007/978-1-4020-6585-9_9(71-92)Online publication date: 2008
https://doi.org/10.1007/978-1-4020-6585-9_9
Steffen PGiegerich R(2006)Table design in dynamic programmingInformation and Computation10.1016/j.ic.2006.02.006204:9(1325-1345)Online publication date: 1-Sep-2006
https://dl.acm.org/doi/10.1016/j.ic.2006.02.006
Liu YStoller S(2003)Optimizing Ackermann's function by incrementalizationACM SIGPLAN Notices10.1145/966049.77739838:10(85-91)Online publication date: 7-Jun-2003
https://dl.acm.org/doi/10.1145/966049.777398
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
Liu YStoller SLeuschel M(2003)Optimizing Ackermann's function by incrementalizationProceedings of the 2003 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation10.1145/777388.777398(85-91)Online publication date: 7-Jun-2003
https://dl.acm.org/doi/10.1145/777388.777398
SATOH TOKAWA INISHIKAWA TSATO TSEKI M(2010)PREDICTION OF WAVEFORMS OF LONG-PERIOD GROUND MOTIONS FOR HYPOTHETICAL EARTHQUAKES USING EMPIRICAL REGRESSION RELATIONS OF RESPONSE SPECTRA AND PHASE SPECTRAJournal of Structural and Construction Engineering (Transactions of AIJ)10.3130/aijs.75.52175:649(521-530)Online publication date: 2010
https://doi.org/10.3130/aijs.75.521

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents