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