Some Techniques for Recursion Removal from Recursive Functions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Some Techniques for Recursion Removal from Recursive Functions

Full text

Pdf (1.27 MB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 4 , Issue 2 (April 1982) table of contents

Pages: 295 - 322

Year of Publication: 1982

ISSN:0164-0925

Authors

J. Arsac	L.A. 248 du CNRS, Institut de programmation, Tour 55-65, 4, place Jussieu, 75230 Paris Cedex 05, France
Y. Kodratoff	L.R.I., Bat. 490, F-91405, Orsay, France

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 38, Citation Count: 9

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/357162.357171 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	ARSAC, J. Premieres leqons de programmation. CEDIC/Fernand Nathan, Paris, 1980.
	2	ARSA~, J. La construction de programmes structures. Dunod, Paris, 1977.
	3	E. A. Ashcroft , W. W. Wadge, Lucid, a nonprocedural language with iteration, Communications of the ACM, v.20 n.7, p.519-526, July 1977 [doi>10.1145/359636.359715]
	4	AUmN, R. Mechanizing Structural Induction. Ph.D. dissertation, Dep. of Artificial Intelligence, Univ. of Edinburgh, Edinburgh, Scotland, 1976.
	5	M. A. Auslander , H. R. Strong, Systematic recursion removal, Communications of the ACM, v.21 n.2, p.127-134, Feb. 1978 [doi>10.1145/359340.359344]
	6	BIERMANN, A.W. The inference of regular LISP programs from examples. IEEE Trans. Syst. Man Cybern. SMC-8 (1978), 585-600.
	7	Robert S. Boyer , J. Strother Moore, Proving Theorems about LISP Functions, Journal of the ACM (JACM), v.22 n.1, p.129-144, Jan. 1975 [doi>10.1145/321864.321875]
	8	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]
	9	BURSTALL, R.M., AND DARLINGTON, J. A system which automatically improves programs. Acta Inf. 6 (1976), 41-60.
	10	CHAMBERLIN, D.D. The "single-assignment" approach to parallel processing. In Proceedings of the 1971 Fall Joint Computer Conference, Las Vegas, Nev., Nov. 16-18, 1971, vol. 39. AFIPS Press, Arlington, Va., 1971, pp. 263-269.
	11	DIJKSTRA, E.W. A misguided educational effort. EWD-757, Oct. 31, 1980.
	12	DIJKSTRA, E.W. More about the function '~fusc." EWD-578, Aug. 16, 1976.
	13	DIJKSTRA, E.W. An exercise for Dr. R.H. Burstall. EWD-570, May 24, 1976.
	14	FA~C, J. FOLDS, a Declarative Formal Language Definition System. Ph.D. dissertation, Computer Science Dep., Stanford Univ., Stanford, Calif., 1972.
	15	FEATHER, M.S. A System for Developing Programs by Transformation. Ph.D. dissertation, Univ. of Edinburgh, Edinburgh, Scotland, 1979.
	16	FLAJOLET, P. Private communication.
	17	Peter Henderson , James H. Morris, Jr., A lazy evaluator, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.95-103, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811543]
	18	C. A. R. Hoare, An axiomatic basis for computer programming, Communications of the ACM, v.12 n.10, p.576-580, Oct. 1969 [doi>10.1145/363235.363259]
	19	HOOGVORST, P. Interpretation d'un langage sans affectation. These 3/~me cycle, Ecole normale sup~rieure Paris, 1977.
	20	HUET, G. R~solution d'~quations dans les langages d'ordre 1, 2 ..... w. These, Paris, 1976.
	21	HUE?, G., A~o LA~G, B. Proving and applying program transformations expressed with secondorder patterns. Acta Inf. 11, 1 (Jan. 1978), 31-55.
	22	JOUA~NAUD, J.-P., A~O Guz~o, G. Inference of functions with an interactive system. In Machine Intelligence, vol. 9, D. Michie (Ed.). Ellis Horwood, Chichester, 1979, pp. 227-250.
	23	JOUANNAUD, J.-P., A~I) KOORATOFF, Y. Characterization of a class of functions synthesized from examples by a SUMMERS-like method using a "B.M.W." matching technique. In Proceedings of the International Joint Conference on Artificial Intelligence, Tokyo, Japan, 1979, pp. 440-446.
	24	KODRATOFF, Y. A class of functions synthesized from a finite number of examples and a LISP program scheme. Int. J. Comput. Inf. Sci. 8, 6 (Dec. 1979), 489-521.
	25	KOORATOFF, Y. Choix d'un programme LISP correspondant ~ des exemples. In Congrbs AFCET- INRIA Reconnaissance des formes, Chatenay-Malabry, France, Feb. 1978, pp. 212-219.
	26	KOORA?OFF, Y., AND JOVAN~AUO, J.-P. Some specifications for the synthesis of lists programs. In Proceedings of the International Workshop on Program Construction, Bonas, 1980.
	27	KOORATOFF, Y., ANO PAPON, E. A system for program synthesis and program optimization. In Proceedings AISB Meeting, Amsterdam, 1980, pp. Kodratoff 1-10.
	28	KoTr, L. About a transformation system: Theoretical study in program transformation. In Program Transformations: 3rd international Symposium on Programming. Dunod, Paris, 1978, pp. 232-247.
	29	LEVY, J.-J. Private communication.
	30	John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
	31	Zohar Manna, Introduction to Mathematical Theory of Computation, McGraw-Hill, Inc., New York, NY, 1974
	32	Zohar Manna , Stephen Ness , Jean Vuillemin, Inductive methods for proving properties of programs, Communications of the ACM, v.16 n.8, p.491-502, Aug. 1973 [doi>10.1145/355609.362336]
	33	MANNA, Z., AND WALDINGER, R. Knowledge and reasoning in program synthesis. Artif. Intell. 6, 2 (Summer 1975), 175-208.
	34	MANNA, Z., AND WALDINGER, R. Synthesis: Dreams ~ programs. Tech. Rep. CS-77-630, Computer Science Dep., Stanford Univ., Stanford, Calif., 1979.
	35	MOORE, J.S. Introducing iteration into the pure LISP theorem prover. IEEE Trans. Softw. Eng. SE-1, 3 (Sept. 1975), 328-338.
	36	PEPPER, P., PARTSCH, H., WOESSNER, H., AND BAUER, F.L. Transformational approach to programming. In Program Transformations: 3rd International Symposium on Programming. Dunod, Paris, 1978, pp. 248-262.
	37	PLOrKZN, G.-D. Automatic Methods of Inductive Inference. Ph.D. dissertation, Dep. of Artificial Intelligence, Univ. of Edinburgh, Edinburgh, Scotland, 1971.
	38	PLOTKiN, G.-D. A further note on inductive generalization. In Machine Intelligence, vol. 6, B. Meltzer and D. Michie (Eds.). Edinburgh University Press, Edinburgh, Scotland, 1971, pp. 101-124.
	39	PLOTKIN, G.-D. A note on inductive generalization. In Machine Intelligence, vol. 5, B. Meltzer and D. Michie (Eds.). Edinburgh University Press, Edinburgh Scotland, 1969, pp. 135-151.
	40	REYNOLDS, J.-C. Transformational systems and the algebraic structure of atomic formulas. In Machine Intelligence, vol. 5, B. Meltzer and D. Michie (Eds.). Edinburgh University Press, Edinburgh, Scotland, 1969, pp. 135-151.
	41	SCOTT, D. Outline of a mathematical theory of computation. In 4th Annual Princeton Conference on Information Sciences & Systems, Princeton, N.J., 1970, pp. 169-176.
	42	SLOANE, N.J.A. A handbook of integer sequences. Academic Press, New York, 1973.
	43	Phillip D. Summers, A Methodology for LISP Program Construction from Examples, Journal of the ACM (JACM), v.24 n.1, p.161-175, Jan. 1977 [doi>10.1145/321992.322002]
	44	TESLER, L.G., ANO ENEA, H.J. A language design for concurrent processes. In Proceedings of the 1968 Spring joint Computer Conference, Atlantic City, N.J., April 30-May 2, 1968, vol. 32. AFIPS Press, Arlington, Va., 1968, pp. 403-408.
	45	WALKER, S.-A., AND STRONG, H.R. Characterization of a fiowchartable recursion. J. Comput. Syst. Sci. 7 (1973), 404-447.
	46	WEGBREIT, B. Goal directed program transformation, iEEE Trans. Sofiw. Eng. SE-2, 2 (June 1976), 69-80.

CITED BY 9

	S. K. Debray, Unfold/fold transformations and loop optimization of logic programs, ACM SIGPLAN Notices, v.23 n.7, p.297-307, July 1988
	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
	H. Partsch , R. Steinbrüggen, Program Transformation Systems, ACM Computing Surveys (CSUR), v.15 n.3, p.199-236, Sept. 1983
	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
	Björn Lisper, Detecting static algorithms by partial evaluation, ACM SIGPLAN Notices, v.26 n.9, p.31-42, Sept. 1991
	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
	David A. Rosenblueth, A Multiple-Clause Folding Rule Using Instantiation and Generalization, Fundamenta Informaticae, v.69 n.1-2, p.219-249, January 2006
	Owen Kaser , C. R. Ramakrishnan , I. V. Ramakrishnan , R. C. Sekar, EQUALS – a fast parallel implementation of a lazy language, Journal of Functional Programming, v.7 n.2, p.183-217, March 1997
	Uday S. Reddy , Barat Jayaraman, Theory of linear equations applied to program transformation, Proceedings of the Eighth international joint conference on Artificial intelligence, p.10-16, August 08-12, 1983, Karlsruhe, West Germany