Umut A. Acar
Guy E. Blelloch
Robert Harper
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.
- M. Abadi, B. W. Lampson, and J.-J. Levy. Analysis and caching of dependencies. In International Conference on Functional Programming, pages 83--91, 1996.]] Google Scholar
Digital Library
- 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.]] Google ScholarDigital Library
- 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.]]Google Scholar
- A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.]] Google ScholarDigital Library
- J. Allen. Anatomy of LISP. McGraw Hill, 1978.]] Google ScholarDigital Library
- 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.]]Google Scholar
- R. Bellman. Dynamic Programming. Princeton University Press, 1957.]] Google ScholarDigital Library
- R. S. Bird. Tabulation techniques for recursive programs. ACM Computing Surveys, 12(4):403--417, Dec. 2002.]] Google ScholarDigital Library
- N. H. Cohen. Eliminating redundant recursive calls. ACM Transactions on Programming Languages and Systems, 5(3):265--299, July 1983.]] Google ScholarDigital Library
- T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press/McGraw-Hill, 1990.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- A. Heydon, R. Levin, and Y. Yu. Caching function calls using precise dependencies. ACM SIGPLAN Notices, 35(5):311--320, 2000.]] Google ScholarDigital Library
- J. Hilden. Elimination of recursive calls using a small table of randomly selected function values. BIT, 16(1):60--73, 1976.]]Google ScholarCross Ref
- 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.]] Google ScholarDigital Library
- R. J. M. Hughes. Lazy memo-functions. In Proceedings 1985 Conference on Functional Programming Languages and Computer Architecture, 1985.]] Google ScholarDigital Library
- S. P. Jones. The Implementation of Functional Programming Languages. Prentice-Hall, 1987.]]Google Scholar
- Y. A. Liu and S. D. Stoller. Dynamic programming via static incrementalization. In European Symposium on Programming, pages 288--305, 1999.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- D. Michie. 'memo' functions and machine learning. Nature, 218:19--22, 1968.]]Google ScholarCross Ref
- 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.]]Google Scholar
- 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.]]Google ScholarCross Ref
- P. Norvig. Techniques for automatic memoization with applications to context-free parsing. Computational Linguistics, pages 91--98, 1991.]] Google ScholarDigital Library
- H. A. Partsch. Specification and Transformation of Programs--A Formal Approach to Software Development. Springer-Verlag, 1990.]] Google ScholarDigital Library
- M. Pennings. Generating Incremental Attribute Evaluators. PhD thesis, University of Utrecht, Nov. 1994.]]Google Scholar
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- W. Pugh. Incremental computation via function caching. PhD thesis, Department of Computer Science, Cornell University, 1987.]]Google Scholar
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- J. M. Spitzen and K. N. Levitt. An example of hierarchical design and proof. Communications of the ACM, 21(12):1064--1075, 1978.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
Index Terms
- Selective memoization
Recommendations
Compile-time function memoization
CC 2017: Proceedings of the 26th International Conference on Compiler ConstructionMemoization is the technique of saving the results of computations so that future executions can be omitted when the same inputs repeat. Recent work showed that memoization can be applied to dynamically linked pure functions using a load-time technique ...
Selective memoization
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 ...
Imperative self-adjusting computation
POPL '08Self-adjusting computation enables writing programs that can automatically and efficiently respond to changes to their data (e.g., inputs). The idea behind the approach is to store all data that can change over time in modifiable references and to let ...
Comments