Show simple item record

dc.contributor.authorWard, Martin
dc.contributor.authorBennett, Keith H.
dc.date.accessioned2005-09-05T19:30:31Z
dc.date.available2005-09-05T19:30:31Z
dc.date.issued1999
dc.identifier.citationWard, M.P. and Bennett, K.H., Recursion removal/introduction by formal transformation: an aid to program development and program comprehension, In: The computer journal, vol.42, no.8, 1999, pp 650-673en
dc.identifier.issn0010-4620
dc.identifier.otherIR/2005/21
dc.identifier.urihttp://hdl.handle.net/2086/44
dc.descriptionPeer-reviewed. received 16th March 1999; accepted 8th September 1999en
dc.description.abstractThe 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 [1] and Bird [2], 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 [1,2]. 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.en
dc.format.extent377167 bytes
dc.format.extent399555 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoenen
dc.publisherOxford University Pressen
dc.relation.ispartofseriesSTRLen
dc.relation.ispartofseries1999/10en
dc.subjectrecursionen
dc.subjectformal methodsen
dc.subjectreverse engineeringen
dc.subjectre-engineeringen
dc.subjectWSLen
dc.subjectwide spectrum languageen
dc.subjectrefinementen
dc.subjectprogram comprehensionen
dc.titleRecursion removal/introduction by formal transformation: an aid to program development and program comprehensionen
dc.typeArticleen
dc.identifier.doihttps://doi.org/10.1093/comjnl/42.8.650
dc.researchgroupSoftware Technology Research Laboratory (STRL)


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record