Selective memoization
Authors:
Open Access
- 15 January 2003
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 38 (1) , 14-25
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.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- A judgmental reconstruction of modal logicMathematical Structures in Computer Science, 2001
- Caching function calls using precise dependenciesACM SIGPLAN Notices, 2000
- Static caching for incremental computationACM Transactions on Programming Languages and Systems, 1998
- Incremental computation via function caching1989
- Eliminating Redundant Recursive Calls.ACM Transactions on Programming Languages and Systems, 1983
- Tabulation Techniques for Recursive ProgramsACM Computing Surveys, 1980
- An example of hierarchical design and proofCommunications of the ACM, 1978
- Elimination of recursive calls using a small table of “randomly” selected function valuesBIT Numerical Mathematics, 1976
- “Memo” Functions and Machine LearningNature, 1968
- A Basis for a Mathematical Theory of Computation )1963