Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/604131.604133acmconferencesArticle/Chapter ViewAbstractPublication PagespoplConference Proceedingsconference-collections
Article

Selective memoization

Published: 15 January 2003 Publication History

Abstract

We present a framework for applying memoization selectively. The framework provides programmer control over equality, space usage, and identification of precise dependences so that memoization can be applied according to the needs of an application. Two key properties of the framework are that it is efficient and yields programs whose performance can be analyzed using standard techniques.We describe the framework in the context of a functional language and an implementation as an SML library. The language is based on a modal type system and allows the programmer to express programs that reveal their true data dependences when executed. The SML implementation cannot support this modal type system statically, but instead employs run-time checks to ensure correct usage of primitives.

References

[1]
M. Abadi, B. W. Lampson, and J.-J. Levy. Analysis and caching of dependencies. In International Conference on Functional Programming, pages 83--91, 1996.]]
[2]
U. A. Acar, G. E. Blelloch, and R. Harper. Adaptive functional programming. In Proceedings of the Twenty-ninth Annual ACM-SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Jan. 2002.]]
[3]
U. A. Acar, G. E. Blelloch, and R. Harper. Selective memoization. Technical Report CMU-CS-02-194, Carnegie Mellon University, Computer Science Department, Dec. 2002.]]
[4]
A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.]]
[5]
J. Allen. Anatomy of LISP. McGraw Hill, 1978.]]
[6]
A. W. Appel and M. J. R. Gonçcalves. Hash-consing garbage collection. Technical Report CS-TR-412-93, Princeton University, Computer Science Department, 1993.]]
[7]
R. Bellman. Dynamic Programming. Princeton University Press, 1957.]]
[8]
R. S. Bird. Tabulation techniques for recursive programs. ACM Computing Surveys, 12(4):403--417, Dec. 2002.]]
[9]
N. H. Cohen. Eliminating redundant recursive calls. ACM Transactions on Programming Languages and Systems, 5(3):265--299, July 1983.]]
[10]
T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press/McGraw-Hill, 1990.]]
[11]
A. Demers, T. Reps, and T. Teitelbaum. Incremental evaluation of attribute grammars with application to syntax directed editors. In Conference Record of the 8th Annual ACM Symposium on POPL, pages 105--116, Jan. 1981.]]
[12]
J. Field and T. Teitelbaum. Incremental reduction in the lambda calculus. In Proceedings of the ACM '90 Conference on LISP and Functional Programming, pages 307--322, June 1990.]]
[13]
E. Goto and Y. Kanada. Hashing lemmas on time complexities with applications to formula manipulation. In Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation, pages 154--158, 1976.]]
[14]
A. Heydon, R. Levin, and Y. Yu. Caching function calls using precise dependencies. ACM SIGPLAN Notices, 35(5):311--320, 2000.]]
[15]
J. Hilden. Elimination of recursive calls using a small table of randomly selected function values. BIT, 16(1):60--73, 1976.]]
[16]
R. Hoover. Alphonse: incremental computation as a programming abstraction. In Proceedings of the 5th ACM SIGPLAN conference on Programming language design and implementation, pages 261--272. ACM Press, 1992.]]
[17]
R. J. M. Hughes. Lazy memo-functions. In Proceedings 1985 Conference on Functional Programming Languages and Computer Architecture, 1985.]]
[18]
S. P. Jones. The Implementation of Functional Programming Languages. Prentice-Hall, 1987.]]
[19]
Y. A. Liu and S. D. Stoller. Dynamic programming via static incrementalization. In European Symposium on Programming, pages 288--305, 1999.]]
[20]
Y. A. Liu, S. D. Stoller, and T. Teitelbaum. Static caching for incremental computation. ACM Transactions on Programming Languages and Systems, 20(3):546--585, 1~May 1998.]]
[21]
J. McCarthy. A Basis for a Mathematical Theory of Computation. In P. Braffort and D. Hirschberg, editors, Computer Programming and Formal Systems, pages 33--70. North-Holland, Amsterdam, 1963.]]
[22]
D. Michie. 'memo' functions and machine learning. Nature, 218:19--22, 1968.]]
[23]
J. Mostov and D. Cohen. Automating program speedup by deciding what to cache. In Proceedings of the Ninth International Joint Conference on Artificial Intelligence, pages 165--172, Aug. 1985.]]
[24]
T. Murphy, R. Harper, and K. Crary. The wizard of TILT: Efficient(?), convenient and abstract type representations. Technical Report CMU-CS-02-120, School of Computer Science, Carnegie Mellon University, Mar. 2002.]]
[25]
P. Norvig. Techniques for automatic memoization with applications to context-free parsing. Computational Linguistics, pages 91--98, 1991.]]
[26]
H. A. Partsch. Specification and Transformation of Programs--A Formal Approach to Software Development. Springer-Verlag, 1990.]]
[27]
M. Pennings. Generating Incremental Attribute Evaluators. PhD thesis, University of Utrecht, Nov. 1994.]]
[28]
M. Pennings, S. D. Swierstra, and H. Vogt. Using cached functions and constructors for incremental attribute evaluation. In Seventh International Symposium on Programming Languages, Implementations, Logics and Programs, pages 130--144, 1992.]]
[29]
F. Pfenning. Structural cut elimination. In D. Kozen, editor, Proceedings of the Tenth Annual Symposium on Logic in Computer Science, pages 156--166. Computer Society Press, 1995.]]
[30]
F. Pfenning and R. Davies. A judgmental reconstruction of modal logic. Mathematical Structures in Computer Science, 11:511--540, 2001. Notes to an invited talk at the Workshop on Intuitionistic Modal Logics and Applications (IMLA'99), Trento, Italy, July 1999.]]
[31]
J. Polakow and F. Pfenning. Natural deduction for intuitionistic non-commutative linear logic. In J.-Y. Girard, editor, Proceedings of the 4th International Conference on Typed Lambda Calculi and Applications (TLCA'99), pages 130--144. Springer-Verlag LNCS 1581, 1999.]]
[32]
W. Pugh. Incremental computation via function caching. PhD thesis, Department of Computer Science, Cornell University, 1987.]]
[33]
W. Pugh. An improved replacement strategy for function caching. In Proceedings of the 1988 ACM conference on LISP and functional programming, pages 269--276. ACM Press, 1988.]]
[34]
W. Pugh and T. Teitelbaum. Incremental computation via function caching. In Conference Record of the 16th Annual Symposium on POPL, pages 315--328, Jan. 1989.]]
[35]
J. M. Spitzen and K. N. Levitt. An example of hierarchical design and proof. Communications of the ACM, 21(12):1064--1075, 1978.]]
[36]
R. S. Sundaresh and P. Hudak. Incremental compilation via partial evaluation. In Conference Record of the 18th Annual ACM Symposium on POPL, pages 1--13, Jan. 1991.]]
[37]
Y. Zhang and Y. A. Liu. Automating derivation of incremental programs. In Proceedings of the third ACM SIGPLAN international conference on Functional programming, page 350. ACM Press, 1998.]]

Cited By

View all
  • (2021)ForerunnerProceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles10.1145/3477132.3483564(570-587)Online publication date: 26-Oct-2021
  • (2021)Using Selective Memoization to Defeat Regular Expression Denial of Service (ReDoS)2021 IEEE Symposium on Security and Privacy (SP)10.1109/SP40001.2021.00032(1-17)Online publication date: May-2021
  • (2020)Techniques for Efficient Automated Elimination of False Positives2020 IEEE 20th International Working Conference on Source Code Analysis and Manipulation (SCAM)10.1109/SCAM51674.2020.00035(259-263)Online publication date: Sep-2020
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
POPL '03: Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages
January 2003
308 pages
ISBN:1581136285
DOI:10.1145/604131
  • cover image ACM SIGPLAN Notices
    ACM SIGPLAN Notices  Volume 38, Issue 1
    January 2003
    298 pages
    ISSN:0362-1340
    EISSN:1558-1160
    DOI:10.1145/640128
    Issue’s Table of Contents
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: 15 January 2003

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. memoization
  2. performance
  3. programmer controlled
  4. selective

Qualifiers

  • Article

Conference

POPL03

Acceptance Rates

POPL '03 Paper Acceptance Rate 24 of 126 submissions, 19%;
Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)22
  • Downloads (Last 6 weeks)2
Reflects downloads up to 19 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2021)ForerunnerProceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles10.1145/3477132.3483564(570-587)Online publication date: 26-Oct-2021
  • (2021)Using Selective Memoization to Defeat Regular Expression Denial of Service (ReDoS)2021 IEEE Symposium on Security and Privacy (SP)10.1109/SP40001.2021.00032(1-17)Online publication date: May-2021
  • (2020)Techniques for Efficient Automated Elimination of False Positives2020 IEEE 20th International Working Conference on Source Code Analysis and Manipulation (SCAM)10.1109/SCAM51674.2020.00035(259-263)Online publication date: Sep-2020
  • (2019)Supporting the Scale-Up of High Performance Application to Pre-Exascale Systems: The ANTAREX Approach2019 27th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP)10.1109/EMPDP.2019.8671584(116-123)Online publication date: Feb-2019
  • (2019)Transforming Query Sequences for High-Throughput B+ Tree Processing on Many-Core Processors2019 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)10.1109/CGO.2019.8661166(96-108)Online publication date: Feb-2019
  • (2018)Memoized Flat Closures for CPSTrends in Functional Programming10.1007/978-3-319-89719-6_1(1-18)Online publication date: 19-Apr-2018
  • (2017)Purity analysis for JavaScript through abstract interpretationJournal of Software: Evolution and Process10.1002/smr.188929:12Online publication date: 25-Aug-2017
  • (2016)Improving financial computation speed with full and subproblem memoizationConcurrency and Computation: Practice & Experience10.1002/cpe.369328:3(905-915)Online publication date: 10-Mar-2016
  • (2014)Speeding up large-scale financial recomputation with memoizationProceedings of the 7th Workshop on High Performance Computational Finance10.1109/WHPCF.2014.9(17-22)Online publication date: 16-Nov-2014
  • (2014)MapReuseProceedings of the 2014 IEEE 28th International Parallel and Distributed Processing Symposium10.1109/IPDPS.2014.18(61-71)Online publication date: 19-May-2014
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media