Tabulation Techniques for Recursive Programs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Tabulation Techniques for Recursive Programs

Full text

Pdf (1.26 MB)

Source

ACM Computing Surveys (CSUR) archive
Volume 12 , Issue 4 (December 1980) table of contents

Pages: 403 - 417

Year of Publication: 1980

ISSN:0360-0300

Author

R. S. Bird

Department of Computer Science, University of Reading, Reading, Berkshire RG6 2AX, England

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 60, Citation Count: 37

Additional Information:

references cited by index terms 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/356827.356831 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.

	AHO72	Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
	AHO75	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	BELL57	BELLMAN, R. E. Dynamw program. ruing, Princeton University Press, Princeton, N.J., 1957.
	BIRD77a	R. S. Bird, Notes on recursion elimination, Communications of the ACM, v.20 n.6, p.434-439, June 1977 [doi>10.1145/359605.359630]
	BIRD77b	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]
	BURS75	R. M. Burstall , John Darlington, Some transformations for developing recursive programs, Proceedings of the international conference on Reliable software, p.465-472, April 21-23, 1975, Los Angeles, California
	CHAN73	CHANDRA, A. K. "Efficient compilation of linear recursive programs," in Conference Record, IEEE 14th Ann. Syrup. Switching and Auto~nata Theory, 1973, pp. 16-25.
	COHE79	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]
	HIRS75	D. S. Hirschberg, A linear space algorithm for computing maximal common subsequences, Communications of the ACM, v.18 n.6, p.341-343, June 1975 [doi>10.1145/360825.360861]
	HORO79	HOROWITZ, E., AND SAHNI, S. Fundamentals of computer algorlthms, Fearon- Pitman, Belmont, Calif., 1979.
	KNUT69	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	MCCA	John McCarthy, On Efficient Ways of Evaluating Certain Recursive Functions, Massachusetts Institute of Technology, Cambridge, MA, 1962
	MCCA63	McCARTHY, J. "A basis for a mathematical theory of computation," in Computer programming and formal systems, E. Braffort and D. Hirschberg (Eds.), North- Holland, Amsterdam, 1963, pp. 33-70.
	MICH67	MICHIE, D. "Memo functions: A language feature with rote learning properties," DMIP Memo. MIP-R-29, Edinburgh. 1967.
	PART76	PARTSCH, H., AND PEPPER, P. "A family of rules for recm~i0n removed rehted to the Towers of Hanoi problem," inf. Pro. cess. Lett. 5, 6 (Dec. 1976), }.74-177.
	PATE70	PATERSON, 1~. S., AND HEWITT, C. E. "Comparative schematology," in Record of Pro/ect MAC Conf. on Concurrent Sys. terns and Parallel Computation, 1970, pp. 119-127.
	PAUL78	PAUL, W. J., AND TAtAr, R.oE. "Timespace trade-offs in a pebble game," Acta Inf. l0 (1978), 111-115.
	PIPP78	Nicholas Pippenger, A Time-Space Trade-Off, Journal of the ACM (JACM), v.25 n.3, p.509-515, July 1978 [doi>10.1145/322077.322091]
	REIN77	Edward M. Reingold , Jurg Nievergelt , Narsingh Deo, Combinatorial Algorithms: Theory and Practice, Prentice Hall College Div, 1977
	SHOR78	SHORT'r, J. "An iterative program to calculate Fibonacci numbers in O(log n) arithmetic operations," Inf. Process. Lett. 7, 6 (Oct. 1978), 299-303.
	STEI77	STEINBRUGGEN, R. "Equivalent recursire definitions of ce~gin number theoretical functions," TUM-INFO-7714, Technische Univ. Miinchen, West Germany, 1977.
	VORO66	VOROBOYOV, N.N. The Fibonacci numbers, D. C. Heath, Boston, Mass., 1966.
	WALK71	WALKER, S.A. "Some graph games related to the efficient calculation of expressions," IBM Res./~.p. RC-3628., 1971.
	WATA80	WATANABE, O. "Another application of recursion introduction," Inf. Process. Lett. 10, 3 (1980), 116-119.
	WELL71	WEL~, M. B. "Elements of combinato. rial computing, Pergamon Press, Elmsford, N.Y., 1971.
	WIRT76	Niklaus Wirth, Algorithms & data structures, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985

CITED BY 37

	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
	J. Ángel Velázquez-Iturbide, Recursion in gradual steps (is recursion really that difficult?), ACM SIGCSE Bulletin, v.32 n.1, p.310-314, Mar. 2000
	H. Partsch , R. Steinbrüggen, Program Transformation Systems, ACM Computing Surveys (CSUR), v.15 n.3, p.199-236, Sept. 1983
	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
	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
	Saumya Debray, Abstract interpretation and low-level code optimization, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.111-121, June 21-23, 1995, La Jolla, California, United States
	T. A. Marsland , M. Campbell, Parallel Search of Strongly Ordered Game Trees, ACM Computing Surveys (CSUR), v.14 n.4, p.533-551, Dec. 1982
	Richard B. Kieburtz , Jonathan Shultis, Transformations of FP program schemes, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.41-48, October 18-22, 1981, Portsmouth, New Hampshire, United States
	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
	L. Colussi, Recursion As an Effective Step in Program Development, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.1, p.55-67, Jan. 1984
	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
	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
	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
	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
	Alberto Pettorossi , Maurizio Proietti, Rules and strategies for transforming functional and logic programs, ACM Computing Surveys (CSUR), v.28 n.2, p.360-414, June 1996
	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
	N. Yoshida, A transformational approach to the derivation of hardware algorithms from recurrence equations, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.433-440, November 12-17, 1988, Orlando, Florida, United States
	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
	Gary Ford, A framework for teaching recursion, ACM SIGCSE Bulletin, v.14 n.2, p.32-39, June 1982
	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
	Beatrice Luca , Stefan Andrei , Hugh Anderson , Siau-Cheng Khoo, Program transformation by solving recurrences, Proceedings of the 2006 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, January 09-10, 2006, Charleston, South Carolina
	Yanhong A. Liu , Scott D. Stoller, Optimizing Ackermann's function by incrementalization, ACM SIGPLAN Notices, v.38 n.10, p.85-91, October 2003
	Norman H. Cohen, Eliminating Redundant Recursive Calls., ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.265-299, July 1983
	Jan Hext, Mr Waring's problem, ACM SIGCSE Bulletin, v.26 n.4, p.13-16, Dec. 1994
	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
	David Wakeling, EDUCATIONAL PEARL: Biological sequence similarity, Journal of Functional Programming, v.16 n.1, p.1-12, January 2006
	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
	Henry G. Baker, The Boyer Benchmark at warp speed, ACM SIGPLAN Lisp Pointers, v.V n.3, p.13-14, July-Sept. 1992
	Henry G. Baker, The Gabriel “Triangle” Benchmark at warp speed, ACM SIGPLAN Lisp Pointers, v.V n.3, p.15-17, July-Sept. 1992
	Henry G. Baker, Speeding up the “Puzzle” Benchmark a “bit”, ACM SIGPLAN Lisp Pointers, v.V n.3, p.18-21, July-Sept. 1992
	Henry G. Baker, A tachy “TAK”, ACM SIGPLAN Lisp Pointers, v.V n.3, p.22-23, July-Sept. 1992
	Lambert Meertens, Calculating the Sieve of Eratosthenes, Journal of Functional Programming, v.14 n.6, p.759-763, November 2004
	Henry G. Baker, Equal rights for functional objects or, the more things change, the more they are the same, ACM SIGPLAN OOPS Messenger, v.4 n.4, p.2-27, Oct. 1993
	Maurice Bruynooghe , Luc De Raedt , Danny De Schreye, Explanation based program transformation, Proceedings of the 11th international joint conference on Artificial intelligence, p.407-412, August 20-25, 1989, Detroit, Michigan
	Jack Mostow , Donald Cohen, Automating program speedup by deciding what to cache, Proceedings of the 9th international joint conference on Artificial intelligence, p.165-172, August 18-23, 1985, Los Angeles, California