Static caching for incremental computation

ABSTRACT

A systematic approach is given for deriving incremental programs that exploit caching. The cache-and-prune method presented in the article consists of three stages: (I) the original program is extended to cache the results of all its intermediate subcomputations as well as the final result, (II)) the extended program is incrementalized so that computation on a new input can use all intermediate results on an old input, and (III) unused results cached by the extended program and maintained by the incremental program are pruned away, leaving a pruned extended program that caches only useful intermediate results and a pruned incremental program that uses and maintains only useful results. All three stages utilize static analyses and semantics-preserving transformations. Stages I and III are simple, clean, and fully automatable. The overall method has a kind of optimality with respect to the techniques used in Stage II. The method can be applied straightfowardly to provide a systematic approach to program improvement via caching.

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: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 4: ALLEN, F. E. 1969. Program optimization. In Annual Review of Automatic Programming. Vol. 5. Pergamon Press, New York, 239-307.
• 5: ALLEN, F. E., COCKE, J., AND KENNEDY, I~. 1981. Reduction of operator strength. In Program Flow Analysis, S. S. Muchnick and N. D. Jones, Eds. Prentice-HM1, Englewood Cliffs, N.J., 79-101.
• 6: Robert A. Ballance , Susan L. Graham , Michael L. Van De Vanter, The Pan language-based editing system, ACM Transactions on Software Engineering and Methodology (TOSEM), v.1 n.1, p.95-127, Jan. 1992 [doi>10.1145/125489.122804]
• 7: 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]
• 8: R. S. Bird, The promotion and accumulation strategies in transformational programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.4, p.487-504, Oct. 1984 [doi>10.1145/1780.1781]
• 9: R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
• 10: Robert Cartwright, Recursive programs as definitions in first order logic, SIAM Journal on Computing, v.13 n.2, p.374-408, May 1984 [doi>10.1137/0213026]
• 11: Wei-Ngan Chin, Towards an automated tupling strategy, Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.119-132, June 14-16, 1993, Copenhagen, Denmark [doi>10.1145/154630.154643]
• 12: Wei-Ngan Chin , Siau-Cheng Khoo, Tupling Functions with Multiple Recursion Parameters, Proceedings of the Third International Workshop on Static Analysis, p.124-140, September 22-24, 1993
• 13: John Cocke , Ken Kennedy, An algorithm for reduction of operator strength, Communications of the ACM, v.20 n.11, p.850-856, Nov. 1977 [doi>10.1145/359863.359888]
• 14: 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]
• 15: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 16: Pierre Deransart , Martin Jourdan , Bernard Lorho, Attribute grammars: definitions, systems and bibliography, Springer-Verlag New York, Inc., New York, NY, 1988
• 17: EARLEY, J. 1976. High level iterators and a method for automatically designing data structure representation. J. Cornput. Lang. 1, 321-342.
• 18: Carl A. Gunter, Semantics of programming languages: structures and techniques, MIT Press, Cambridge, MA, 1992
• 19: Robert J Hall, Program Improvement by Automatic Redistribution of Intermediate Results, Massachusetts Institute of Technology, Cambridge, MA, 1991
• 20: HALL, R. J. 1991. Program improvement by automatic redistribution of intermediate results: An overview. In Automating Software Design, M. R. Lowry and R. D. McCartney, Eds. AAAI Press/The MIT Press, 339-372.
• 21: 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
• 22: John Hughes, Lazy memo-functions, Proc. of a conference on Functional programming languages and computer architecture, p.129-146, January 1985, Nancy, France
• 23: John Hughes, Compile-time analysis of functional programs, Research topics in functional programming, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 24: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 25: Simon B. Jones , Daniel Le Métayer, Compile-time garbage collection by sharing analysis, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.54-74, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99375]
• 26: Takuya Katayama, Translation of attribute grammars into procedures, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.3, p.345-369, July 1984 [doi>10.1145/579.586]
• 27: Robert M. Keller , M. R. Sleep, Applicative caching, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.1, p.88-108, Jan. 1986 [doi>10.1145/5001.5004]
• 28: KLEENE, S. C. 1952. Introduction to Metarnathernatics. Van Nostrand, New York. 10th reprint, Wolters-Noordhoff Publishing, Groningen and North-Holland Publishing Company, Amsterdam, 1991.
• 29: KNUTH, D. E. 1968. Semantics of context-free languages. Math. Syst. Theory 2, 2 (June), 127-145.
• 30: LAUNCHBURY, J. 1989. Projection factorisations in partial evaluation. Ph.D. thesis, Department of Computing, University of Glasgow, Glasgow, Scotland.
• 31: John Launchbury, Strictness and binding-time analyses: two for the price of one, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.80-91, June 24-28, 1991, Toronto, Ontario, Canada
• 32: Julia L. Lawall , Olivier Danvy, Separating stages in the continuation-passing style transformation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.124-136, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158613]
• 33: Y. A. Liu, CACHET: an interactive, incremental-attribution-based program transformation system for deriving incremental programs, Proceedings of The 10th Knowledge-Based Software Engineering Conference, p.19, November 12-15, 1995
• 34: Yanhong A. Liu, Principled strength reduction, Proceedings of the IFIP TC 2 WG 2.1 international workshop on Algorithmic languages and calculi, p.357-381, January 1997, Alsace, France
• 35: Yanhong A. Liu, Dependence Analysis for Recursive Data, Proceedings of the 1998 International Conference on Computer Languages, p.206, May 14-16, 1998
• 36: Yanhong A. Liu , Scott D. Stoller, Loop optimization for aggregate array computations, Proceedings of the 1998 International Conference on Computer Languages, p.262, May 14-16, 1998
• 37: Yanhong A. Liu , Tim Teitelbaum, Systematic derivation of incremental programs, Science of Computer Programming, v.24 n.1, p.1-39, Feb. 1995 [doi>10.1016/0167-6423(94)00031-9]
• 38: Yanhong A. Liu , Scott D. Stoller , Tim Teitelbaum, Discovering auxiliary information for incremental computation, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.157-170, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237769]
• 39: MICHIE, D. 1968. "memo" functions and machine learning. Nature 218, 19-22.
• 40: Torben Æ Mogensen, Separating binding times in language specifications, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.12-25, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99372]
• 41: MOSTOW, D. J. AND COHEN, D. 1985. Automating program speedup by deciding what to cache. In Proceedings of the 9th International Joint Conference on Artificial Intelligence. Morgan Kaufmann Publishers, San Francisco, Calif., 165-172.
• 42: Jukka Paakki, Attribute grammar paradigms—a high-level methodology in language implementation, ACM Computing Surveys (CSUR), v.27 n.2, p.196-255, June 1995 [doi>10.1145/210376.197409]
• 43: Robert Paige, Transformational programming: applications to algorithms and systems, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.73-87, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567076]
• 44: R. Paige, Symbolic finite differencing, part I (invited lecture), Proceedings of the third European symposium on programming on ESOP '90, p.36-56, May 1990, Copenhagen, Denmark
• 45: Robert Paige, Viewing A Program Transformation System At Work, Proceedings of the 6th International Symposium on Programming Language Implementation and Logic Programming, p.5-24, September 14-16, 1994
• 46: Robert Paige , Shaye Koenig, Finite Differencing of Computable Expressions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.402-454, July 1982 [doi>10.1145/357172.357177]
• 47: Helmut A. Partsch, Specification and transformation of programs: a formal approach to software development, Springer-Verlag New York, Inc., New York, NY, 1990
• 48: Alberto Pettorossi, A powerful strategy for deriving efficient programs by transformation, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.273-281, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802044]
• 49: A. Pettorossi, Strategical derivation of on-line programs, The IFIP TC2/WG 2.1 Working Conference on Program specification and transformation, p.73-88, June 1987, Bad To:9Ailz, Germany
• 50: Alberto Pettorossi , Maurizio Proietti, Program derivation via list introduction, Proceedings of the IFIP TC 2 WG 2.1 international workshop on Algorithmic languages and calculi, p.296-323, January 1997, Alsace, France
• 51: PLOTKIN, G. D. 1975. Call-by-name, call-by-value and the h-calculus. Theoret. Comput. Sci. 1, 125-159.
• 52: 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]
• 53: 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]
• 54: Paul Walton Purdom, Jr. , Cynthia A. Brown, The analysis of algorithms, Holt, Rinehart & Winston, Austin, TX, 1985
• 55: Thomas W. Reps , Tim Teitelbaum, The synthesizer generator: a system for constructing language-based editors, Springer-Verlag New York, Inc., New York, NY, 1989
• 56: Thomas W. Reps , Todd Turnidge, Program Specialization via Program Slicing, Selected Papers from the Internaltional Seminar on Partial Evaluation, p.409-429, February 12-16, 1996
• 57: Thomas Reps , Tim Teitelbaum , Alan Demers, Incremental Context-Dependent Analysis for Language-Based Editors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.449-477, July 1983 [doi>10.1145/2166.357218]
• 58: Mads Rosendahl, Automatic complexity analysis, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.144-156, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99381]
• 59: SCOTT, D. S. 1982. Lectures on a mathematical theory of computation. In Theoretical Foundations of Programming Methodology, M. Broy and G. Schmidt, Eds. D. Reidel Publishing Company, 145-292.
• 60: D. R. Smith, KIDS: A Semiautomatic Program Development System, IEEE Transactions on Software Engineering, v.16 n.9, p.1024-1043, September 1990 [doi>10.1109/32.58788]
• 61: R. S. Sundaresh, Building incremental programs using partial evaluation, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.83-93, June 17-19, 1991, New Haven, Connecticut, United States
• 62: 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]
• 63: K. R. Traub, A COMPILER FOR THE MIT TAGGED-TOKEN DATAFLOW ARCHITECTURE, Massachusetts Institute of Technology, Cambridge, MA, 1986
• 64: Philip Wadler , R. J. M. Hughes, Projections for strictness analysis, Proc. of a conference on Functional programming languages and computer architecture, p.385-407, October 1987, Portland, Oregon, United States
• 65: Jon A. Webb, Steps Toward Architecture-Independent Image Processing, Computer, v.25 n.2, p.21-31, February 1992 [doi>10.1109/2.121472]
• 66: Adam Webber, Optimization of functional programs by grammar thinning, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.293-330, March 1995 [doi>10.1145/201059.201067]
• 67: Adam Brooks Webber, Principled optimization of functional programs, Cornell University, Ithaca, NY, 1993
• 68: Adam Brooks Webber, Program analysis using binary relations, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.249-260, June 16-18, 1997, Las Vegas, Nevada, United States
• 69: Ben Wegbreit, Mechanical program analysis, Communications of the ACM, v.18 n.9, p.528-539, Sept. 1975 [doi>10.1145/361002.361016]
• 70: W Wells, III, Efficient synthesis of Gaussian filters by cascaded uniform filters, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.2, p.234-239, March 1986 [doi>10.1109/TPAMI.1986.4767776]
• 71: D. Yeh , U. Kastens, Improvements of an incremental evaluation algorithm for ordered attribute grammars, ACM SIGPLAN Notices, v.23 n.12, p.45-50, Dec. 1988 [doi>10.1145/57669.57672]
• 72: Ramin Zabih , Oussama Khatib, Individuating unknown objects by combining motion and stereo, 1994
• 73: Ramin Zabih , John Woodfill, Non-parametric local transforms for computing visual correspondence, Proceedings of the third European conference on Computer Vision (Vol. II), p.151-158, May 1994, Stockholm, Sweden

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation; Automatic analysis of algorithms

General Terms:
Algorithms, Languages, Performance

Keywords:
caching, dependence analysis, incremental computation, incremental programs, intermediate results, memoization, optimization, program efficiency improvement, program transformation, static analysis