glenn@dit.lth.se (Glenn Jennings) (01/18/91)
Can anyone please point me to any *published* works dealing with this issue:
Is it easy or hard to automatically transform an algorithm which
is expressed recursively, into one that is expressed iteratively ?
Practical results are preferred, but theoretical discussions are still
helpful. I am guessing that it is hard (in general) to devise a program
which can convert an arbitrary recursive program into one having only loops.
Please reply by email to glenn@dit.lth.se THANK YOU !
--
Glenn Jennings DSt/LTH Tel: (+46) 46 109763
Dept. of Computer Engineering Fax: (+46) 46 104714
Box 118, Lund University Email: glenn@dit.lth.se
S-221 00 Lund, SWEDENglenn@dit.lth.se (Glenn Jennings) (01/18/91)
(Sorry if this gets onto "comp.lang.functional" twice...)
Can anyone please point me to any *published* works dealing with this issue:
Is it easy or hard to automatically transform an algorithm which
is expressed recursively, into one that is expressed iteratively ?
Practical results are preferred, but theoretical discussions are still
helpful. I am guessing that it is hard (in general) to devise a program
which can convert an arbitrary recursive program into one having only loops.
Please reply by email to glenn@dit.lth.se THANK YOU !
--
Glenn Jennings DSt/LTH Tel: (+46) 46 109763
Dept. of Computer Engineering Fax: (+46) 46 104714
Box 118, Lund University Email: glenn@dit.lth.se
S-221 00 Lund, SWEDENstark@sbstark (Eugene Stark) (01/20/91)
>Can anyone please point me to any *published* works dealing with this issue: > > Is it easy or hard to automatically transform an algorithm which > is expressed recursively, into one that is expressed iteratively ? > > Practical results are preferred, but theoretical discussions are still >helpful. I am guessing that it is hard (in general) to devise a program >which can convert an arbitrary recursive program into one having only loops. Isn't this something that is done by nearly every compiler? - Gene Stark
eerke@cs.kun.nl (Eerke Boiten) (01/21/91)
In article <1991Jan19.182618.7727@sbcs.sunysb.edu> stark@sbstark (Eugene Stark) writes: [Glenn Jennings writes:] >>Can anyone please point me to any *published* works dealing with this issue: >> >> Is it easy or hard to automatically transform an algorithm which >> is expressed recursively, into one that is expressed iteratively ? >> >> Practical results are preferred, but theoretical discussions are still >>helpful. I am guessing that it is hard (in general) to devise a program >>which can convert an arbitrary recursive program into one having only loops. I was going to respond to this, Gene Stark was ahead of me: > >Isn't this something that is done by nearly every compiler? > Yes, of course it is done by nearly every compiler. So, generally it is easy. Just the stacks-implementation of recursion. The interesting question is not whether it is possible to transform recursive algorithms into iterative ones, but whether it is possible to do this *without using stacks*. Tail-recursive functions, i.e. fns of the form f(x) = if P(x) then H(x) else f(K(x)) fi can be immediately translated into y:= x; WHILE NOT P(y) DO y:= K(y); RETURN H(y) General linear recursive functions, of the form f(x) = if P(x) then H(x) else E(x,f(K(x))) fi cannot, in general, be translated into iterative form without using stacks. This is proved by Paterson and Hewitt [Pat70]. In the literature on transformational programming (cf. the book by my "boss" H. Partsch [Par90a], or [Fea87]), many examples of transformations from linear recursion to tail recursion are treated (in particular, use of an accumulator and inversion of computation). Follows a small excerpt from my BibTeX file on transformational programming etc. : @ARTICLE{ Ars82, Author= {J. Arsac and Y. Kodratoff}, Title= {Some Techniques for Recursion Removal from Recursive Functions}, Journal= toplas, Volume= 4, Number= 2, Month= Apr, Year= 1982, Pages= {295--322}} % Ars82: Transformational, many techniques. @ARTICLE{ Aus78, Author= {M.A. Auslander and M.R. Strong}, Title= {Systematic Recursion Removal}, Journal= cacm, Volume= 21, Number= 2, Pages= {127--133}, Year= 1978} % Aus78 and other work by Strong: classical. @BOOK{ Bau82a, Author= {Bauer, F.L. and W{\"o}ssner, H.}, Title= {Algorithmic Language and Program Development}, Publisher= sv, Address= {Berlin}, Year= 1982} % Early textbook on transformational programming; % contains large section on recursion simplification and -removal. @CONFERENCE{ Fea87, Author= {Feather, M.S.}, Title= {A Survey and Classification of some Program Transformation Approaches and Techniques}, Crossref= {Mee87}, Pages= {165--196}} @PROCEEDINGS{ Mee87, Booktitle= {Program Specification and Transformation. Proceedings of the {IFIP} {TC2}/{WG2.1} Working Conference on Program Specification and Transformation} Title= {Program Specification and Transformation. Proceedings of the {IFIP} {TC2}/{WG2.1} Working Conference on Program Specification and Transformation} Editor= {Meertens, L.G.L.T.}, Publisher= nhpc, Address= {Amsterdam}, Year= 1987} % General survey in IFIP TC2 conference proceedings. @BOOK{ Par90a, Author= {Partsch, H.}, Title= {Specification and Transformation of Programs - a Formal Approach to Software Development}, Address= {Berlin}, Publisher= sv, Year= 1990} % Recent textbook on transformational programming. @CONFERENCE{ Pat70, Author= {Paterson, M.S. and Hewitt, C.E.}, Title= {Comparative Schematology}, Booktitle= {Record of the Project MAC Conf. on Conc.Syst. and Par.Comp., {W}oods Hole, {M}ass.}, Year= 1970, Address= {New York}, Publisher= {ACM}, Pages= {119--127}} % Contains proof that stacks are sometimes necessary. @ARTICLE{ Str71, Author= {Strong, Jr., H.R.}, Title= {Translating recursion equations into flowcharts}, Journal= jcss, Volume= 5, Pages= {254--285}, Year= 1971} @ARTICLE{ Str75, Author= {H.R.A. Strong and A. Maggiolo-Schettini and B.A. Rosen}, Title= {Recursion Structure Simplification}, Journal= sicomp, Volume= 4, Number= 3, Year= 1975, Pages= {307--320}} @ARTICLE{ Wal73, Author= {Walker, S.A. and Strong, H.R.}, Title= {Characterizations of flowchartable recursions}, Journal= jcss, Volume= 7, Pages= {404--447}, Year= 1973} -- Eerke Boiten Department of Informatics (STOP Project), K.U.Nijmegen Toernooiveld, 6525 ED Nijmegen, The Netherlands Tel. +31-80-652236. Email: eerke@cs.kun.nl
mattias@brigitte.csd.uu.se (Mattias Waldau) (01/28/91)
Hakan Millroth (hakanm@emil.csd.uu.se) asked me to submit this respons to following message. [Glenn Jennings writes:] >>Can anyone please point me to any *published* works dealing with this issue: >> >> Is it easy or hard to automatically transform an algorithm which >> is expressed recursively, into one that is expressed iteratively ? >> >> Practical results are preferred, but theoretical discussions are still >>helpful. I am guessing that it is hard (in general) to devise a program >>which can convert an arbitrary recursive program into one having only loops. My PhD thesis describes a technique for compiling a logic program using structural linear recursion to the following iterative form. The head of a recursive clause is compiled to iterative code (WHILE- and FOR-loops) for one large unification that replaces the N smaller unifications in an SLD-resolution system. The body of the clause is compiled to iterative code that runs the left-body (the calls to the left of the recursive call) and right-body in separate FOR-loops. Structural nonlinear recursion can be compiled in a similar way by obtaining a temporary linear representation of the recursion tree during head unification (this gives practically no overhead since the entire tree is traversed anyway in the single large unification resulting invoking the program). The significance of compiling recursion to FOR-loops in this way (rather than to WHILE-loops as in traditional tail-recursion optimization) is that the compiled code can be parallelized by standard techniques for parallelizing Fortran DO-loops. This is a form of parallel processing that, when applicable, is inherently more efficient than traditional AND-parallelism, since the computation can be directly mapped to an array of parallel processors without runtime task scheduling and load balancing. -- Mattias Waldau Computing Science Department mattias@emil.csd.uu.se P.O. Box 520, S-751 20 Uppsala, Sweden Phone: +46-18-181055