Yanhong A. Liu
Scott D. Stoller
Skip Abstract Section
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.
- ABADI, M., LAMPSON, B., AND LI~VY, J.-J. 1996. Analysis and caching of dependencies. In Proceedings of the 1996 ACM SIGPLAN International Conference on Functional Programming. ACM, New York. Google Scholar
- AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J. D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass. Google Scholar
- AHO, A. V., SETHI, R., AND ULLMAN, J. D. 1986. Compilers, Principles, Techniques, and Tools. Addison-Wesley, Reading, Mass. Google Scholar
- ALLEN, F. E. 1969. Program optimization. In Annual Review of Automatic Programming. Vol. 5. Pergamon Press, New York, 239-307.Google Scholar
- 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.Google Scholar
- BALLANCE, R. A., GRAHAM, S. L., AND VAN DE VANTER, M. L. 1992. The Pan language-based editing system. ACM Trans. Soft. Eng. Methodol. 1, 1 (Jan.), 95-127. Google Scholar
- BIRD, R. S. 1980. Tabulation techniques for recursive programs. ACM Comput. Surv. 12, 4 (Dec.), 403-417. Google Scholar
- BIRD, R. S. 1984. The promotion and accumulation strategies in transformational programming. A CM Trans. Program. Lang. Syst. 6, 4 (Oct.), 487-504. Google Scholar
- BURSTALL, R. M. AND DARLINGTON, J. 1977. A transformation system for developing recursive programs. J. ACM 24, 1 (Jan.), 44-67. Google Scholar
- CARTWRIGHT, R. 1984. Recursive programs as definitions in first order logic. SIAM J. Cornput. 13, 2 (May), 374-408. Google Scholar
- CHIN, W.-N. 1993. Towards an automated tupling strategy. In Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation. ACM, New York, 119-132. Google Scholar
- CHIN, W.-N. AND KHOO, S.-C. 1993. Tupling functions with multiple recursion parameters. In Proceedings of the 3rd International Workshop on Static Analysis, P. Cousot, M. Falaschi, G. Fil~, and A. Rauzy, Eds. Lecture Notes in Computer Science, vol. 724. Springer-Verlag, Berlin, 124-140. Google Scholar
- COCKE, J. AND KENNEDY, K. 1977. An algorithm for reduction of operator strength. Cornrnun. ACM 20, 11 (Nov.), 850-856. Google Scholar
- COHEN, N. H. 1983. Eliminating redundant recursive calls. ACM Trans. Program. Lang. Syst. 5, 3 (July), 265-299. Google Scholar
- CORMEN, T. H., LEISERSON, C. E., AND RIVEST, R. L. 1990. Introduction to Algorithms. The MIT Press/McGraw-Hill. Google Scholar
- DERANSART, P., JOURDAN, M., AND LORHO, B. 1988. Attribute Grammars: Definitions, Systems, and Bibliography. Lecture Notes in Computer Science, vol. 323. Springer-Verlag, Berlin. Google Scholar
- EARLEY, J. 1976. High level iterators and a method for automatically designing data structure representation. J. Cornput. Lang. 1, 321-342.Google Scholar
- GUNTER, C. A. 1992. Semantics of Programming Languages. The MIT Press, Cambridge, Mass. Google Scholar
- HALL, R. J. 1990. Program improvement by automatic redistribution of intermediate results. Tech. Rep. AI-TR-1251, Artificial Intelligence Laboratory, MIT, Cambridge, Mass. Dec. Google Scholar
- 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.Google Scholar
- HOOVER, R. 1992. Alphonse: Incremental computation as a programming abstraction. In Proceedings of the A CM SIGPLAN '92 Conference on Programming Language Design and Irnplernentation. ACM, New York, 261-272. Google Scholar
- HUGHES, J. 1985. Lazy memo-functions. In Proceedings of the 2nd Conference on Functional Programming Languages and Computer Architecture. Lecture Notes in Computer Science, vol. 201. Springer-Verlag, Berlin, 129-146. Google Scholar
- HUGHES, J. 1990. Compile-time analysis of functional programs. In Research Topics in Functional Programming, D. Turner, Ed. Addison-Wesley, Reading, Mass., 117-153. Google Scholar
- JONES, N. D., GOMARD, C. K., AND SESTOFT, P. 1993. Partial Evaluation and Automatic Program Generation. Prentice-Hall, Englewood Cliffs, N.J. Google Scholar
- JONES, S. B. AND LE MI~TAYER, D. 1989. Compile-time garbage collection by sharing analysis. In Proceedings of the gth International Conference on Functional Programming Languages and Computer Architecture. ACM, New York, 54-74. Google Scholar
- KATAYAMA, T. 1984. Translation of attribute grammars into procedures. ACM Trans. Program. Lang. Syst. 6, 3 (July), 345-369. Google Scholar
- KELLER, R. M. AND SLEEP, M. R. 1986. Applicative caching. ACM Trans. Program. Lang. Syst. 8, 1 (Jan.), 88-108. Google Scholar
- KLEENE, S. C. 1952. Introduction to Metarnathernatics. Van Nostrand, New York. 10th reprint, Wolters-Noordhoff Publishing, Groningen and North-Holland Publishing Company, Amsterdam, 1991.Google Scholar
- KNUTH, D. E. 1968. Semantics of context-free languages. Math. Syst. Theory 2, 2 (June), 127-145.Google Scholar
- LAUNCHBURY, J. 1989. Projection factorisations in partial evaluation. Ph.D. thesis, Department of Computing, University of Glasgow, Glasgow, Scotland.Google Scholar
- LAUNCHBURY, J. 1991. Strictness and binding-time analysis: Two for the price of one. In Proceedings of the A CM SIGPLAN '91 Conference on Programming Language Design and Irnplernentation. ACM, New York, 80-91. Google Scholar
- LAWALL, J. L. AND DANVY, O. 1993. Separating stages in the continuation-passing style transformation. In Conference Record of the 20th Annual A CM Symposium on Principles of Prograrnrning Languages. ACM, New York, 124-136. Google Scholar
- LIU, Y. A. 1995. CACHET: An interactive, incrementM-attribution-based program transformation system for deriving incremental programs. In Proceedings of the 10th Knowledge-Based Software Engineering Conference. IEEE CS Press, Los Alamitos, Calif., 19-26. Google Scholar
- LIU, Y. A. 1997. Principled strength reduction. In Algorithmic Languages and Calculi, R. Bird and L. Meertens, Eds. Chapman ~ Hall, London, U.K., 357-381. Google Scholar
- LIU, Y. A. 1998. Dependence analysis for recursive data. In Proceedings of the 1998 IEEE International Conference on Computer Languages. IEEE CS Press, Los Alamitos, Calif. Google Scholar
- LIU, Y. A. AND STOLLER, S. D. 1998. Loop optimization for aggregate array computations. In Proceedings of the 1998 IEEE International Conference on Computer Languages. IEEE CS Press, Los Alamitos, Calif. Google Scholar
- LIU, Y. A. AND TEITELBAUM, T. 1995. Systematic derivation of incremental programs. Sci. Comput. Program. 24, 1 (Feb.), 1-39. Google Scholar
- LIU, Y. A., STOLLER, S. D., AND TEITELBAUM, T. 1996. Discovering auxiliary information for incremental computation. In Conference Record of the 23rd Annual A CM Symposium on Principles of Programming Languages. ACM, New York, 157-170. Google Scholar
- MICHIE, D. 1968. "memo" functions and machine learning. Nature 218, 19-22.Google Scholar
- MOGENSEN, T. 1989. Separating binding times in language specifications. In Proceedings of the 4th International Conference on Functional Programming Languages and Computer Architecture. ACM, New York, 12-25. Google Scholar
- 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.Google Scholar
- PAAKKI, J. 1995. Attribute grammar paradigms--A high-level methodology in language implementation. ACM Comput. Surv. 27, 2 (June), 196-255. Google Scholar
- PAIGE, R. 1983. Transformational programming--Applications to algorithms and systems. In Conference Record of the 10th Annual A CM Symposium on Principles of Programming Languages. ACM, New York, 73-87. Google Scholar
- PAIGE, R. 1990. Symbolic finite differencing--Part I. In Proceedings of the 3rd European Symposium on Programming. Lecture Notes in Computer Science, vol. 432. Springer-Verlag, Berlin, 36-56. Google Scholar
- PAIGE, R. 1994. Viewing a program transformation system at work. In Proceedings of Joint 6th International Conference on Programming Languages: Implementations, Logics and Programs and 4th International Conference on Algebraic and Logic Programming, M. Hermenegildo and J. Penjam, Eds. Lecture Notes in Computer Science, vol. 844. Springer-Verlag, Berlin, 5-24. Google Scholar
- PAIGE, R. AND KOENIG, S. 1982. Finite differencing of computable expressions. ACM Trans. Program. Lang. Syst. 4, 3 (July), 402-454. Google Scholar
- PARTSCH, H. A. 1990. Specification and Transformation of Programs--A Formal Approach to Software Development. Springer-Verlag, Berlin. Google Scholar
- PETTOROSSI, t. 1984. A powerful strategy for deriving efficient programs by transformation. In Conference Record of the 1984 A CM Symposium on LISP and Functional Programming. ACM, New York. Google Scholar
- PETTOROSSI, A. 1987. Strategical derivation of on-line programs. In Program Specification and Transformation, L. G. L. T. Meertens, Ed. North-Holland, Amsterdam, 73-88. Google Scholar
- PETTOROSSI, t. AND PROIETTI, M. 1997. Program derivation via list introduction. In Algorithmic Languages and Calculi, R. Bird and L. Meertens, Eds. Chapman ~ Hall, London, U.K. Google Scholar
- PLOTKIN, G. D. 1975. Call-by-name, call-by-value and the h-calculus. Theoret. Comput. Sci. 1, 125-159.Google Scholar
- PUGH, W. 1988. An improved cache replacement strategy for function caching. In Proceedings of the 1988 ACM Conference on LISP and Functional Programming. ACM, New York, 269-276. Google Scholar
- PUGH, W. AND TEITELBAUM, T. 1989. Incremental computation via function caching. In Conference Record of the 16th Annual A CM Symposium on Principles of Programming Languages. ACM, New York, 315-328. Google Scholar
- PURDOM, P. W. AND BROWN, C. A. 1985. The Analysis of Algorithms. Holt, Rinehart and Winston. Google Scholar
- REPS, T. AND TEITELBAUM, T. 1988. The Synthesizer Generator: A System for Constructing Language-Based Editors. Springer-Verlag, New York. Google Scholar
- REPS, T. AND TURNIDGE, T. 1996. Program specialization via program slicing. In Proceedings of the Dagstuhl Seminar on Partial Evaluation, O. Danvy, R. Gliick, and P. Thiemann, Eds. Lecture Notes in Computer Science, vol. 1110. Springer-Verlag, Berlin, 409-429. Google Scholar
- REPS, T., TEITELBAUM, T., AND DEMERS, t. 1983. Incremental context-dependent analysis for language-based editors. ACM Trans. Program. Lang. Syst. 5, 3 (July), 449-477. Google Scholar
- ROSENDAHL, M. 1989. Automatic complexity analysis. In Proceedings of the ~th International Conference on Functional Programming Languages and Computer Architecture. ACM, New York, 144-156. Google Scholar
- 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.Google Scholar
- SMITH, D. R. 1990. KIDS: A semiautomatic program development system. IEEE Trans. Softw. Eng. 16, 9 (Sept.), 1024-1043. Google Scholar
- SUNDARESH, R. S. 1991. Building incremental programs using partial evaluation. In Proceedings of the Symposium on Partial Evaluation and Semantics-Based Program Manipulation. ACM, New York, 83-93. Google Scholar
- SUNDARESH, R. S. AND HUDAK, P. 1991. Incremental computation via partial evaluation. In Conference Record of the 18th Annual A CM Symposium on Principles of Programming Languages. ACM, New York, 1-13. Google Scholar
- TRAUB, K. R. 1986. A compiler for the MIT tagged-token dataflow architecture. M.S. thesis, Department of Electrical Engineering and Computer Science, MIT, Cambridge, Massachusetts. Appeared as Technical Report LCS TR-370, August, 1986. Google Scholar
- WADLER, P. AND HUGHES, R. J. M. 1987. Projections for strictness analysis. In Proceedings of the 3rd International Conference on Functional Programming Languages and Computer Architecture. Lecture Notes in Computer Science, vol. 274. Springer-Verlag, Berlin, 385-407. Google Scholar
- WEBB, J. t. 1992. Steps towards architecture-independent image processing. IEEE Comput. 25, 2 (Feb.), 21-31. Google Scholar
- WEBBER, A. 1995. Optimization of functional programs by grammar thinning. A CM Trans. Program. Lang. Syst. 17, 2 (Mar.), 293-330. Google Scholar
- WEBBER, A. B. 1993. Principled optimization of functional programs. Ph.D. thesis, Department of Computer Science, Cornell University, Ithaca, N.Y. Also appeared as Technical Report TR 93-1363, June 1993. Google Scholar
- WEBBER, A. B. 1997. Program analysis using binary relations. In Proceedings of the A CM SIGPLAN '97 Conference on Programming Language Design and Implementation. ACM, New York, 249-160. Google Scholar
- WEGBREIT, B. 1975. Mechanical program analysis. Commun. ACM 18, 9 (Sept.), 528-538. Google Scholar
- WELLS, W. M., III. 1986. Efficient synthesis of Gaussian filters by cascaded uniform filters. IEEE Trans. Part. Anal. Mach. Intell. 8, 2 (Mar.), 234-239. Google Scholar
- YEH, D. AND KASTENS, U. 1988. Improvements on an incremental evaluation algorithm for ordered attribute grammars. SIGPLAN Not. 23, 12, 45-50. Google Scholar
- ZABIH, R. 1994. Individuating unknown objects by combining motion and stereo. Ph.D. thesis, Department of Computer Science, Stanford University, Stanford, Calif. Google Scholar
- ZABIH, R. AND WOODFILL, J. 1994. Non-parametric local transforms for computing visual correspondence. In Proceedings of the 3rd European Conference on Computer Vision, J.-O. Eklundh, Ed. Lecture Notes in Computer Science, vol. 801. Springer-Verlag, 151-158. Google Scholar
Index Terms
- Static caching for incremental computation
Recommendations
Dynamic Programming via Static Incrementalization
Dynamic programming is an important algorithm design technique. It is used for problems whose solutions involve recursively solving subproblems that share subsubproblems. While a straightforward recursive program solves common subsubproblems repeatedly, ...
Efficiency by Incrementalization: An Introduction
Incremental computation takes advantage of repeated computations on inputs that differ slightly from one another, computing each output efficiently by exploiting the previous output. This paper gives an overview of a general and systematic approach to ...
Optimizing Ackermann's function by incrementalization
PEPM '03: Proceedings of the 2003 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulationThis paper describes a formal derivation of an optimized Ackermann's function following a general and systematic method based on incrementalization. The method identifies an appropriate input increment operation and computes the function by repeatedly ...
Reviews
Pierre Jouvelot
Recursive programs such as the Fibonacci function induce redundant subexpression evaluations at run time. Caching of the intermediate values of subexpressions is a natural tradeoff mechanism that potentially decreases the overall program running time while increasing memory consumption. Using a new cache-and-prune method on sets of recursive function definitions, incremental versions of these functions that use efficient caching can be derived. This paper describes how this three-step derivation process operates on each function. First, a version that caches all intermediate values is derived. Then, this new function is incrementalized; for any argument x , the value of f on any input combining x and an input change y is specified using f x and y . Finally, unused intermediate values are pruned from this extended definition. Only Step 2 is not fully automatable. Some small examples are provided, together with a comprehensive discussion of related techniques. Even though the basic ideas behind the cache-and-prune technique are relatively straightforward, getting the details right is more intricate. The paper digs into these issues to provide a detailed description of all involved mechanisms. Some optimality results are provided. T ogether with the examples, they give some insurance regarding the practical import of these techniques. This paper should mainly appeal to people interested in advanced compilation and optimization techniques.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments