Eliminating Redundant Recursive Calls.

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Eliminating Redundant Recursive Calls.

Full text

Pdf (1.74 MB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 5 , Issue 3 (July 1983) table of contents

Pages: 265 - 299

Year of Publication: 1983

ISSN:0164-0925

Author

Norman H. Cohen

Harvard University

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 40, Citation Count: 18

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/2166.2167 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	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]
	3	R. S. Bird, Improving programs by the introduction of recursion, Communications of the ACM, v.20 n.11, p.856-863, Nov. 1977 [doi>10.1145/359863.359889]
	4	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]
	5	CHANDRA, A.K. Efficient compilation of linear recursive programs. In Conference Record, IEEE 14th Annual Symposium on Switching and Automata Theory (Iowa City, Iowa, Oct. 1973), pp. 16-25.
	6	COHEN, N.H. Source-to-Source Improvement of Recursive Programs. Ph.D. dissertation, Division of Applied Sciences, Harvard Univ., Cambridge, Mass., May 1980.
	7	Norman H. Cohen, Characterization and elimination of redundancy in recursive programs, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.143-157, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567766]
	8	DARLINGTON, J. Program transformation and synthesis: Present capabilities. Res. Rep. 77/43, Dept. of Computing and Control, Imperial College of Science and Technology, London, Sept. 1977.
	9	DARLINGTON, J., AND BURSTALL, R.M. A system which automatically improves programs. Acta Inf. 6, 1 (Mar. 1976), 41-60.
	10	Daniel P. Friedman , David S. Wise , Mitchell Wand, Recursive programming through table look-up, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.85-89, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806326]
	11	HILDEN, J. Elimination of recursive calls using a small table of "randomly" selected function values. BIT 16, 1 (1976), 60-73.
	12	LEWIS, H.R. A new decidable problem, with applications. In Proceedings, IEEE 18th Annual Symposium on Foundations of Computer Science (Providence, R.I., Oct.-Nov. 1977), pp. 62-73.
	13	MICHIE, D. "Memo" functions and machine learning. Nat. 218, 5136 (Apr. 6, 1968), 19-22.
	14	PATERSON, M.S., ANO HEWITr, C.E. Comparative schematology. In Record of the Project MAC Conference on Concurrent Systems and Parallel Computation (Woods Hole, Mass., June 2-5, 1970), pp. 119-127.
	15	PIPPENCER, N. Pebbling. Res. Rep. RC 8258, IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y., May 1980.
	16	STRONG, H.R. Translating recursion equations into flowcharts. J. Comput. Syst. Sci. 5, 3 (June 1971), 254-285.
	17	Sowmitri Swamy , John E. Savage, Space-time tradeoffs for linear recursion, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.135-142, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567765]
	18	VUILLEMIN, J. Correct and optimal implementations of recursion in a simple programming language. J. Comput. $yst. Sci. 9, 3 (Dec. 1974), 332-354.

CITED BY 18

	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
	Yanhong A. Liu , Scott D. Stoller, From recursion to iteration: what are the optimizations?, ACM SIGPLAN Notices, v.34 n.11, p.73-82, Nov. 1999
	Steven Prestwich, Online partial deduction of logic programs, Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.111-118, June 14-16, 1993, Copenhagen, Denmark
	Yanhong A. Liu , Tim Teitelbaum, Caching intermediate results for program improvement, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.190-201, June 21-23, 1995, La Jolla, California, United States
	Wei-Ngan Chin , Masami Hagiya, A bounds inference method for vector-based memoization, ACM SIGPLAN Notices, v.32 n.8, p.176-187, Aug. 1997
	Yanhong A. Liu , Scott D. Stoller, Program optimization using indexed and recursive data structures, ACM SIGPLAN Notices, v.37 n.3, p.108-118, March 2002
	Vance E. Waddle, Production trees: a compact representation of parsed programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.61-83, Jan. 1990
	Jeffrey F. Naughton , Raghu Ramakrishnan, How to forget the past without repeating it, Journal of the ACM (JACM), v.41 n.6, p.1151-1177, Nov. 1994
	Zhenjiang Hu , Hideya Iwasaki , Masato Takeichi , Akihiko Takano, Tupling calculation eliminates multiple data traversals, ACM SIGPLAN Notices, v.32 n.8, p.164-175, Aug. 1997
	Yanhong A. Liu , Scott D. Stoller, Dynamic Programming via Static Incrementalization, Higher-Order and Symbolic Computation, v.16 n.1-2, p.37-62, March-June 2003
	Norman H. Cohen, A note on Cohen's “eliminating redundant recursive calls”, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.680-685, Oct. 1985
	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
	Umut A. A. Acar , Guy E. Blelloch , Robert Harper, Selective memoization, ACM SIGPLAN Notices, v.38 n.1, p.14-25, January 2003
	Yanhong A. Liu, Efficiency by Incrementalization: An Introduction, Higher-Order and Symbolic Computation, v.13 n.4, p.289-313, Dec. 1, 2000
	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
	Wei-Ngan Chin , Siau-Cheng Khoo , Neil Jones, Redundant Call Elimination via Tupling, Fundamenta Informaticae, v.69 n.1-2, p.1-37, January 2006
	Jeffrey F. Naughton , Raghu Ramakrishnan, How to Forget the Past Without Repeating It, Proceedings of the 16th International Conference on Very Large Data Bases, p.278-289, August 13-16, 1990
	Peter Madden , Alan Bundy , Alan Smaill, Recursive Program Optimization through Inductive Synthesis Proof Transformation, Journal of Automated Reasoning, v.22 n.1, p.65-115, January 1999

INDEX TERMS

Primary Classification:
I. Computing Methodologies
I.2 ARTIFICIAL INTELLIGENCE
I.2.2 Automatic Programming
Subjects: Program transformation

Additional Classification:
D. Software
D.1 PROGRAMMING TECHNIQUES
D.3 PROGRAMMING LANGUAGES
D.3.3 Language Constructs and Features
Subjects: Procedures, functions, and subroutines
D.3.4 Processors
Subjects: Optimization

F. Theory of Computation
F.3 LOGICS AND MEANINGS OF PROGRAMS
F.3.3 Studies of Program Constructs
Subjects: Program and recursion schemes

G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS
G.2.2 Graph Theory
Subjects: Trees; Graph algorithms

General Terms:
Design, Languages, Performance, Theory

REVIEW

"Jiri Horejs : Reviewer"

The methods of tabulating results of recursive calls to avoid their recomputations are surveyed in [1]. The reviewed paper considers a rather special, theoretically simple, yet practically significant (as demonstrated by numerous examples) clas more...

Collaborative Colleagues:

Norman H. Cohen: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player