Yanhong A. Liu
Scott D. Stoller
Skip Abstract Section
Abstract
Transforming recursion into iteration eliminates the use of stack frames during program execution. It has been studied extensively. This paper describes a powerful and systematic method, based on incrementalization, for transforming general recursion into iteration: identify an input increment, derive an incremental version under the input increment, and form an iterative computation using the incremental version. Exploiting incrementalization yields iterative computation in a uniform way and also allows additional optimizations to be explored cleanly and applied systematically, in most cases yielding iterative programs that use constant additional space, reducing additional space usage asymptotically, and run much faster. We summarize major optimizations, complexity improvements, and performance measurements.
- 1 H. Abelson, R. K. Dybvig, et al. Revised rept, rt on the algorithmic language Scheme. Hi'gher-Order and Symbolic Computation, 11(1):7-105, Aug. 1998.]] Google Scholar
Digital Library
- 2 A. V. Aho, J. E. ttopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-'Wesley, Reading, Mass., 1974.]] Google ScholarDigital Library
- 3 A. W. Appel. Modern C6rnpiler fmpiementation in Java. Cambridge University Pres,% 1998.]] Google ScholarDigital Library
- 4 J. Arsac and Y. Kodrateff. Some techniques for reeursion removal from recursive functions. A CM 7~.ans. Program. Lang. Syst., 4(2):295-322, Apr. 1982.]] Google ScholarDigital Library
- 5 J. Backus. Can programming be liberated from the yon Neumann style? a functional style and its algebra o.f programs. Commun. ACM, 21(8):613-641, Aug. 1978.]] Google ScholarDigital Library
- 6 J..Backus. From function level semantics to program transformation and optimization. In H. Ehrig et al., editors, Proceedings of the International Joint Confedence on Theory and Practice of Software Development, "volume 185 of Lecture Notes in Computer Science, pages 60-91. Springer-Verlag, Berlin, Mar. 1985.]] Google ScholarDigital Library
- 7 F. L. Batier a,xd H. ",VSs~uie,'. Algorithmic La~gut, ge ~nd Program Development. Springer-Verlag, Berlin, 1982.]] Google ScholarDigital Library
- 8 L. Blaine and A. Goldberg. DTRE--A semi-automatic transformation system. In B. M511er, editor, Constructing Programs from Specifications, pages 165-203. North-Holland, Amsterdam, 1991.]]Google Scholar
- 9 E. A. Boiten. Improving recursive functions by inverting the order of evaluation. Sci. Comput. Program., 18(2):139-179, Apr. 1992.]] Google ScholarDigital Library
- 10 R. M. Burstall and J. Darlington. A transformation system for developing recursive programs. J. ACM, 24(1):44-67, Jan. 1977.]] Google ScholarDigital Library
- 11 J. Cai and R. Paige. Program derivation by fixed point computation. Sci. Comput. Program., 11:197-261, Sept. 1988/89.]] Google ScholarDigital Library
- 12 N. H. Cohen. Eliminating redundant recursive calls. ACM Trans. Program. Lang. Syst., 5(3):265--299. July 1983.]] Google ScholarDigital Library
- 13 T. H. Cormen, C. E. Leiserson, and R. L. Rivest,. Introduction to Algorithms. The MIT Press/McGraw-Hill, 1990.]] Google ScholarDigital Library
- 14 J. Darlington and ~. Burstall. A system which automatically improves programs. Acts Informatica, 6(1):41--60, 1976.]]Google ScholarDigital Library
- 15 A. FiIinski. Recursion from iteration. Lisp and Symbolic Computation, 7(1):11-38, Jan. 1994.]] Google ScholarDigital Library
- 16 D. P. Friedman, M. Wand, and C. T. Haynes. Essentials of Programming Languages. MIT Press and McGraw-Hill, 1992.]] Google ScholarDigital Library
- 17 S. J Garland and D. C. Luckham. Program schemes, recursion schemes, and formal languages. J. Computer System Sciences, 7:119-160, 1973. Also appeared as technical report UCLA-ENG- 7154, June 2971.]]Google ScholarDigital Library
- 18 J. Golsing, B. Joy, and G. Steele. The Java Language Specification. Addison-WesIey, Reading, Mass., 1997.]]Google Scholar
- 19 S. A. Greibach. Theory of Program Structures: Schemes, Se. mantics, Verification, volume 36 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 1975.]] Google ScholarDigital Library
- 20 P. G. Harrison. Linearisation: An optimization for nonlinear functional programs. Sci. Comput. Program., 10:281-318, 1988.]] Google ScholarDigital Library
- 21 P. G. Harrison and H. Khoshnevisan. A new approach to recursion removal. Theoret. Comput. Sci., 93(1):91-113, 1992.]] Google ScholarDigital Library
- 22 P. G. Harrison and H. Khoshnevisan. On the synthesis of function inverses. Acta Informatica, 29(3):211-239, 1992.]] Google ScholarDigital Library
- 23 W. L. Harrison, III. The interprocedural analysis and automatic parallellization of scheme programs. Lisp and Symbolic Computation, 2(3;/4):179-396, Oct. 1989.]]Google Scholar
- 24 P. Hadak. t, semantic model of reference counting and its abstraction, in Conference Record of the 1986 A CM Symposium on LISP and Functional Programming, pages 351-363. ACM, New Yorl~. Aug. 1986.]] Google ScholarDigital Library
- 25 :3. Huet and B. Lang. Proving and applying program transformations expressed with second-order patterns. Acta Informatica, 11(1):31-55, 1978.]]Google ScholarDigital Library
- 26 N. D. Jones. The expressive power of higher-order types or, life without CONS. Journal of Functional Programming. To appear.]] Google ScholarDigital Library
- 27 S. B. Jones and D. Le M~tayer. Compile-time garbage collection by sharing analysis. In Proceedings of the $th International Conference on Functional Programming Languages and Computer Architecture~ pages 54-74. ACM, New York, Sept. 1989.]] Google ScholarDigital Library
- 28 A. J. Kfoury. Recursion versus iteration at higher-orders. In Fov.ndations of Software Technology and Theoretical Computer .$cienc~, volume 1346 of Lecture Notes in Computer Science, pages 57"-? Springer-Verlag, Berlin, Dec. 1997.]] Google ScholarDigital Library
- 29 R. B. Kieburtz and J. Shultis. Transformations of fp program ~chemes. In Proceedings of the ACM Conference on Functional Programming Lnnguages and Computer Architecture. ACM, N ew York, 1981.]] Google ScholarDigital Library
- 30 N. Klarlund. MONA Version 1.3 User Manual, Oct. 1998.]]Google Scholar
- 31 Y. A. Liu. CACHET: An interactive, incremental-attributionbased program transformation system for deriving incremental programs. In Proceedings of the l Oth Knowledge-Based Software Engineering Conference, pages 19-26. IEEE CS Press, Los Alamitos, Calif, Nov. 1995.]] Google ScholarDigital Library
- 32 Y. A. Liu. Principled strength reduction. In Proceedings of the IFIP TC2 Working Conference on Algorithmic Languages and Calcul~ Chapman &: Hall, London, U.K., Feb. 1997.]] Google ScholarDigital Library
- 33 Y. A. Liu and S. D. Stoller. Dynamic programming via static incrementalization. In Proceedings of the 8th European Symposium on Programming, volume 1576 of Lecture Notes in Computer Science, pages 288-305. Springer-Verlag, Berlin, Mar. 1999.]] Google ScholarDigital Library
- 34 Y. A. Liu and S. D. Stolter. From recursion to iteration: what are the optimizations? Technical Report TR 527, Computer Science Department, Indiana University, Bloomington, Indiana, July 1999.]]Google ScholarDigital Library
- 35 Y. A. Liu, S. D. Stoller, and T. Teitelbaum. Discovering auxiliary information for incremental computation. In Conference Record of the $3rd Annual A CM Symposium on Principles of Programming Languages, pages 157-170. ACM, New York, Jan. 1996.]] Google ScholarDigital Library
- 36 Y. A. Liu, S. D. Stoller, and T. Teitelbaum. Static caching for incremental computation. ACM Trans. Program. Lang. Syst., 20(3):546--585, May 1998.]] Google ScholarDigital Library
- 37 Y. A. Liu and T. Teitelbaum. Systematic derivation of incremental programs. Sci~ Comput. Program., 24(1):1-39, Feb. 1995.]] Google ScholarDigital Library
- 38 M. Odersky. Programming with variable functions. In Proceedings of the 1998 A CM SIGPLAN International Conference on Functional Programming, pages 105-1!6. ACM, New York, Sept. 1998.]] Google ScholarDigital Library
- 39 R. Paige. Real-time simulation of a set machine on a RAM. In Computing and information, Vol. II, pages 69-73. Canadian Scholars Press, 1989. Proceedings of ICCI '89: The International Conference on Computing and Information. Toronto, Canada, May 23-27, 1989.]]Google Scholar
- 40 R. Paige and S. Koenig. Finite differencing of computable expressions. ACM Trans. Program. Lan9. Syst., 4(3):402-454, July 1982.]] Google ScholarDigital Library
- 41 H. A. Partsch. Specification and Transformation of Prcgrams-- A Formal Approach to Software Development. Springer-Verlag, Berlin, 1990.]] Google ScholarDigital Library
- 42 M. S. Paterson and C. E. Hewitt. Comparative schematology. In Project MAC Conference on Concurrent Systems and Parallel Computation, pages 119-127. ACM, New York, 1970.]]Google ScholarDigital Library
- 43 A. Pettorossi. A powerful strategy for deriving efficient programs by transformation. In Conference Record of the 198~ A CM" Symposium on LISP and Functional Prograrnminq. ACM, New York, Aug. 1984.]] Google ScholarDigital Library
- 44 A. Pettorossi and M. Proietti. Rules and strategies for transforming functional and logic programs. A CM Comput. Surv., .28(2):360-414, June 1996.]] Google ScholarDigital Library
- 45 W. Pugh. The Omega Test: A fast and practical integer programming algorithm for dependence analysis. Commun. A CM, 31(8), Aug. 1992.]] Google ScholarDigital Library
- 46 P. W. Purdom and C. A. Brown- The Analysis of Algorithms. Holt, Rinehart and Winston, 1985.]] Google ScholarDigital Library
- 47 W. L. Scherlis. Program improvement by internal specialize, tion. tn Conference Record of the 8th Annual A CM Symposium on Principles of Programming Languages, pages 41-49. ACM, New York, Jan. 1981.]] Google ScholarDigital Library
- 48 H. Schorr and W. M. Waite. An efficient machine-independent procedure for grabage collection in various list structures. Commun. ACM, 10(8):501-506, Aug. a967.]] Google ScholarDigital Library
- 49 D. R. Smith. KIDS: A semiautomatic program development system. IEEE Trans. Softw. Eng., i6(9):1024-1043, Sept. 1990.]] Google ScholarDigital Library
- 50 S. A. Walker and H. R. Strong. Characterizations of flowchartable recursions. Journal of Computer anti System Sciences, 7:404-447, 1973.]]Google Scholar
- 51 M. Wand. Continuation-based program transfolmation strategies. J. ACM, 27(1):164-180, Jan. 1980.]] Google ScholarDigital Library
- 52 M. Wand and W. D. Clinger. Set constraints for destructive array update optimization. In Proceedings of the IEEE 1998 International Conference on Computer Languages, pages 184-193. IEEE CS Press, Los Alamitos~ Calif., May 1998.]] Google ScholarDigital Library
- 53 R. C. Waters. Automatic transformation of series expressions into loops. ACM Trans. Program. Lang. Syst., 13(1):52-98, Jan. 1991.]] Google ScholarDigital Library
- 54 B. Wegbreit. Goal-directed program transformation. IEEE Trans. Softw. Eng., SE-.q(9~):69-80. June 1976.]]Google Scholar
Index Terms
- From recursion to iteration: what are the optimizations?
Recommendations
From recursion to iteration: what are the optimizations?
PEPM '00: Proceedings of the 2000 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulationTransforming recursion into iteration eliminates the use of stack frames during program execution. It has been studied extensively. This paper describes a powerful and systematic method, based on incrementalization, for transforming general recursion ...
Iteration Functions in Some Nonsmooth Optimization Algorithms
Recently, several globally convergent model algorithms based on iteration functions have been proposed for solving nonsmooth optimization problems. In particular, Pang, Han and Rangaraj proposed such an algorithm for minimizing a locally Lipschitzian ...
Simplifying the variational iteration method: A new approach to obtain the Lagrange multiplier
AbstractThe variational iteration method (VIM) has been in the last two decades, one of the most used semi-analytical techniques for approximating nonlinear differential equations. The notion of VIM is based on the identification of the ...
Comments