Re: Research in Recursive-to-Non-Recursive Functions

On Monday 29 Nov 2004 4:22 am, Kaustubh wrote:
> Can someone please point me to the state-of-the-art research
> activities for "Automatic Conversion from Recursive to Non Recursive
> Functions" and such C-to-C Transformations. I have been working for
> some time on this in the context of C-to-VHDL Conversion.


Go to: http://www.cse.dmu.ac.uk/~mward/martin/papers/ and scroll down
to "Recursion Removal/Introduction by Formal Transformation: An Aid to
Program Development and Program Comprehension".


Abstract:


The transformation of a recursive program to an iterative
equivalent is a fundamental operation in Computer Science.
In the reverse direction, the task of _reverse engineering_
(analysing a given program in order to determine its specification)
can be greatly ameliorated if the program can be re-expressed
in a suitable recursive form. But the existing recursion removal
transformations, such as the techniques discussed by Knuth [.Knuth
goto.] and Bird [.Bird recursion removal.], can only be applied
in the reverse direction if the source program happens to match
the structure produced by a particular recursion removal operation.
In this paper we describe a much more powerful recursion removal
and introduction operation which describes its source and target
in the form of an _action system_ (a collection of labels
and calls to labels). A simple, mechanical, restructuring operation
can be applied to a great many iterative programs which will
put them in a suitable form for recursion introduction.
Our transformation generates strictly more iterative versions than
the standard methods, including those of Knuth and Bird [.Knuth goto,
Bird recursion removal.]. With the aid of this theorem we prove a
(somewhat counterintuitive) result for programs that contain
sequences of two or more recursive calls: under a reasonable
commutativity condition, ``depth-first'' execution is more
general than ``breadth-first'' execution. In ``depth-first''
execution, the execution of each recursive call is completed,
including all sub-calls, before execution of the next call is started.
In ``breadth-first'' execution, each recursive call in the sequence
is partially executed but any sub-calls are temporarily postponed.
This result means that any breadth-first program can be reimplemented
as a corresponding depth-first program, but the converse does not hold.
We also treat the case of ``random-first'' execution, where the execution
order is implementation dependent. For the more restricted domain of tree
searching we show that breadth first search is the most general form.
We also give two examples of recursion introduction as an aid
to formal reverse engineering.


--
Martin


Martin.Ward@durham.ac.uk http://www.cse.dmu.ac.uk/~mward/ Erdos number: 4

Return to the comp.compilers page.
Search the comp.compilers archives again.