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, 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
sjohnson@iuvax.cs.indiana.edu (Steve Johnson) (01/23/91)
In article <2665@wn1.sci.kun.nl> eerke@cs.kun.nl (Eerke Boiten) writes: >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]. As I'm sure many will point out, the result in Paterson&Hewitt states that NON-linear recursion schemes cannot be translated to iterative form (i.e. expressed as a flow chart). The proof is done by showing the scheme f(x) = if P(x) then x else H(f(L(x)), f(R(x))) cannot be so translated. The tree-pebbling argument is reproduced in several places, including Manna's book [1]. Theorem 2 of [Pat70] states that linear schemes are translatable and gives a construction (in the form of a flow chart). Strong developed a stronger notion of translatability (between recursion schemes and flowcharts)--- I think he called it "operational translatability"---which isolates the iterative schemes from the linear schemes. For the case of linear schemes, it is helpful to look at the simpler case: f(x) = if P(x) then x else E(f(K(x)) The difference is that the value of `x' is not saved in the call to E. A iterative system of two functions computes this value, which is f(a) = E^n(K^n(a)) for some n. g(x, y) = if P(x) then h(x, y) else g(K(x), y) h(x, y) = if P(y) then x else h(E(x), K(y)) g(a, a) first computes K^n(a) while saving the original value of a for later. h(K^n(a), a) computers E^n(K^(a)). Applications of P are serving as a counter. Intuitively, g and h take twice as long to computer their result as f takes (if you count defined-function calls, say, or applications of P). The more general linear scheme given earler is trickier to write and, by the intuitive measure, takes quadratic time. A couple of other good references to these topics are Greibach's lecture notes [2] and Cohen's doctoral thesis [3]. I should also mention an article by Wand [4] in which he explores using analysis of continuations to determine whether control could be represented in something simpler than a stack (e.g. an accumulator, a bit, a counter, etc.). I hope that the originator of this note will post the collection of references accumulated. [Pat70] {from the original note} Paterson, M.S. and Hewitt, C.E., Comparative Schematology, Record of the Project MAC Conf. on Conc.Syst. Par.Comp., Woods Hole, Mass., 1970, ACM, New York, 119--127 [1] Zohar Manna, Theory of Computation. McGraw Hill, New York, 1974 [2] Sheila A. Greibach. Theory of Program Structures: Schemes, Semantics, Verification. Springer LNCS vol. 36, Springer, Berlin, 1975. [3] Norman H. Cohen. Source-to-source Improvement of Recursive Programs, Ph.D. Dissertation, Harvard Univ., Cambridge, Mass. (USA), 1980 [4] Mitchell Wand, Continuation based program transformations strategies, JACM 27(1):164-180 (January 1980)
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