The Translation of 'Go To' Programs to 'While' Programs.
Edward A. Ashcroft, Zohar Manna · Yourdon Press eBooks · 1971
Some of the papers presented in this book already have been widely circulated; others were published in well-known journals, like IBM Systems Journal but largely were ignored when they first appeared; and then there are the obscure papers like this one by Ashcroft and Manna, which was presented at the 1971 IFIP Conference in Ljubljana, Yugoslavia. It's not that the ideas in the paper are obscure -- it's just that very few people in the mainstream EDP community attended the Conference, and precious few copies of the conference proceedings ever found their way into American libraries. It is, however, a paper that many people over the years have wanted to read, particularly since it deals with a subject also mentioned by Knuth (Structured Programming with go to State, ments [see Paper 20]), Wulf (A Case Against the GOTO [Paper 8]), and Bom and Jacopini (Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules [Paper 2]). The subject of the Ashcroft and Manna paper is the translation of unstructured programs into equivalent structured programs. Although Wulf's paper sets forth a more practical, step-by-step mechanism for such translations, Ashcroft and Manna give an extremely detailed, extremely theoretical presentation, providing an important addition to the work of Bom and Jacopini --- but it's definitely for the more serious students of computer science. The larger issue of is ignored by Ashcroft and Manna, and, to a large extent, by everyone else. The issue began as a theoretical question: Could any program be written as a structured program? Bom and Jacopini answered the question in the affirmative by demonstrating that any arbitrary program could be translated ir/to an equivalent structured program. Wulf, Knuth, and Ashcroft and Manna shifted the emphasis of the question slightly: Could one translate an existing program into a structured program that still would have the same topology as the original program? To most people, the mere question suggested heresy, perverting the very idea of writing structured programs! Rather than writing bad code and then cleaning it up, they argued, we should begin by writing good code in the first place. But the larger issue of restructuring does exist. The vast mountains of unstructured code, which already were written before structured programming came along, clearly can't be thrown away. Members of the average EDP organization have to live with their code, for better or worse, for a period of ten years or more before they can afford to discard it. Do Ashcroft and Manna have the solution for these people? Can we take existing unstructured code and translate it into more maintainable, structured code? And, more important, can we do it mechanically? In principle, we can. Indeed, the Ashcroft-Manna algorithm has been built into so-called structuring engines such as the one described by Guy de Balbine in Better Manpower Utilization Using Automatic Restructuring. But there are questions that still have not been completely answered: For example, can one really trust such an automatic translation process? What if the original unstructured program worked because of its use of syntactically illegal COBOL statements --- not in spite of, but because of illegal statements that the compiler ignored, or for which it produced mysterious object code that accidentally produced the right result! Another somewhat ironic situation could occur that would hamper the success of an automatic translation process: After living with a program for ten years, a veteran maintenance programmer may have become intimately familiar with the rat's-nest unstructured logic, and a mechanical translation of the program into a structured form actually might be less understandable! Of course, it is unlikely that a structuring engine could improve anything but the control structures (and perhaps the formatting, if a PRETTYPRINT function is included); the data-names still might be so cryptic that nobody would be able to understand the program. Moreover, the program might be part of a larger system suffering from all the problems of, say, pathological connections or global data areas. So, it is not entirely clear that the world really wants mechanical structuring algorithms. However, since situations do exist in which the capability might be useful, it is a very good idea to be familiar with the kind of translation mechanisms that Ashcroft and Manna present.