×

zbMATH — the first resource for mathematics

Recursion removal/introduction by formal transformation: An aid to program development and program comprehension. (English) Zbl 0956.68014
Summary: 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 (analyzing 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. However, the existing recursion removal transformations, such as the techniques discussed by D. E. Knuth [\((*)\) Computing Surveys 6, 261-301 (1974; Zbl 0301.68014)] and R. S. Bird [\((**)\) Commun. ACM 20, 434-439 (1977; Zbl 0358.68016)], can only be applied in the reverse direction if the source program happens to match the structure a 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 \((*)\) and \((**)\). 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 a ‘breadth-first’ search is the most general form.
We also give two examples of recursion introduction as an aid to formal reverse engineering.

MSC:
68N01 General topics in the theory of software
Software:
RAISE
PDF BibTeX XML Cite
Full Text: DOI