Selective memoization

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: Martín Abadi , Butler Lampson , Jean-Jacques Lévy, Analysis and caching of dependencies, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.83-91, May 24-26, 1996, Philadelphia, Pennsylvania, United States
• 2: Umut A. Acar , Guy E. Blelloch , Robert Harper, Adaptive functional programming, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.247-259, January 16-18, 2002, Portland, Oregon
• 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: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 5: John Allen, Anatomy of LISP, McGraw-Hill, Inc., New York, NY, 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: Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
• 8: R. S. Bird, Tabulation Techniques for Recursive Programs, ACM Computing Surveys (CSUR), v.12 n.4, p.403-417, Dec. 1980 [doi>10.1145/356827.356831]
• 9: Norman H. Cohen, Eliminating Redundant Recursive Calls., ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.265-299, July 1983 [doi>10.1145/2166.2167]
• 10: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 11: Alan Demers , Thomas Reps , Tim Teitelbaum, Incremental evaluation for attribute grammars with application to syntax-directed editors, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.105-116, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567544]
• 12: John Field , Tim Teitelbaum, Incremental reduction in the lambda calculus, Proceedings of the 1990 ACM conference on LISP and functional programming, p.307-322, June 27-29, 1990, Nice, France [doi>10.1145/91556.91679]
• 13: Eiichi Goto , Yasumasa Kanada, Hashing LEMMAs on time complexities with applications to formula manipulation, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.154-158, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806334]
• 14: Allan Heydon , Roy Levin , Yuan Yu, Caching function calls using precise dependencies, ACM SIGPLAN Notices, v.35 n.5, p.311-320, May 2000
• 15: J. Hilden. Elimination of recursive calls using a small table of randomly selected function values. BIT, 16(1):60--73, 1976.
• 16: Roger Hoover, Alphonse: incremental computation as a programming abstraction, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.261-272, June 15-19, 1992, San Francisco, California, United States
• 17: John Hughes, Lazy memo-functions, Proc. of a conference on Functional programming languages and computer architecture, p.129-146, January 1985, Nancy, France
• 18: S. P. Jones. The Implementation of Functional Programming Languages. Prentice-Hall, 1987.
• 19: Yanhong A. Liu , Scott D. Stoller, Dynamic Programming via Static Incrementalization, Proceedings of the 8th European Symposium on Programming Languages and Systems, p.288-305, March 22-28, 1999
• 20: Yanhong A. Liu , Scott D. Stoller , Tim Teitelbaum, Static caching for incremental computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.3, p.546-585, May 1998 [doi>10.1145/291889.291895]
• 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: Peter Norvig, Techniques for automatic memoization with applications to context-free parsing, Computational Linguistics, v.17 n.1, March 1991
• 26: Helmut A. Partsch, Specification and transformation of programs: a formal approach to software development, Springer-Verlag New York, Inc., New York, NY, 1990
• 27: M. Pennings. Generating Incremental Attribute Evaluators. PhD thesis, University of Utrecht, Nov. 1994.
• 28: Maarten Pennings , S. Doaitse Swierstra , Harald Vogt, Using Cached Functions and Constructors for Incremental Attribute Evaluation, Proceedings of the 4th International Symposium on Programming Language Implementation and Logic Programming, p.130-144, August 26-28, 1992
• 29: Frank Pfenning, Structural Cut Elimination, Proceedings of the 10th Annual IEEE Symposium on Logic in Computer Science, p.156, June 26-29, 1995
• 30: Frank Pfenning , Rowan Davies, A judgmental reconstruction of modal logic, Mathematical Structures in Computer Science, v.11 n.4, p.511-540, August 2001 [doi>10.1017/S0960129501003322]
• 31: Jeff Polakow , Frank Pfenning, Natural Deduction for Intuitionistic Non-communicative Linear Logic, Proceedings of the 4th International Conference on Typed Lambda Calculi and Applications, p.295-309, April 07-09, 1999
• 32: W. Pugh. Incremental computation via function caching. PhD thesis, Department of Computer Science, Cornell University, 1987.
• 33: William Pugh, An improved replacement strategy for function caching, Proceedings of the 1988 ACM conference on LISP and functional programming, p.269-276, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62719]
• 34: W. Pugh , T. Teitelbaum, Incremental computation via function caching, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.315-328, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75305]
• 35: Jay M. Spitzen , Karl N. Levitt , Lawrence Robinson, An example of hierarchical design and proof, Communications of the ACM, v.21 n.12, p.1064-1075, Dec. 1978 [doi>10.1145/359657.359667]
• 36: R. S. Sundaresh , Paul Hudak, A theory of incremental computation and its application, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-13, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99587]
• 37: Yuchen Zhang , Yanhong A. Lin, Automating derivation of incremental programs, Proceedings of the third ACM SIGPLAN international conference on Functional programming, p.350, September 26-29, 1998, Baltimore, Maryland, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.0 General

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
      D.3.3 Language Constructs and Features
          Subjects: Control structures

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Languages, Performance

Keywords:
memoization, performance, programmer controlled, selective