Compilers - Research in Recursive-to-Non-Recursive Functions

Author

Research in Recursive-to-Non-Recursive Functions

Kaustubh

2004-11-29, 4:10 pm

Hi,
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.

Thanks in Advance,
Kaustubh

Martin Ward

2004-12-02, 3:57 am

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

stefaan

2004-12-02, 3:57 am

kaustubh.gandhi@gmail.com (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.

Hello,

In the context of my PhD research I have developed a method for
systematically transforming recursion into iteration from imperative
programs (including C). The method works for non-linear non-mutual
recursion in the presence of side-effects. It allows systematic
trade-offs between space complexity, time complexity and available
parallelism.

Feel free to mail me privately for more detailed discussion.

Best Regards,
Stefaan Himpe.

Sponsored Links