Syntactic source to source transforms and program manipulation

ABSTRACT

Syntactic transforms are the source to source program transformations which preserve the history of computation, and thus do not modify the execution time. Combined with a small number of primitive semantic transforms, they provide a powerful tool for program manipulation. A complete catalogue of syntactic transforms, and its use for solution of a system of program equations, is given. Examples of derivation of more complex source to source transformations are also presented. Two case studies illustrate the way in which syntactic and semantic source to source transformations may be used for development of clear, simple, and reasonably efficient programs.

REFERENCES

• 1: Ashcroft, E., and Manna, Z. The translation of GO TO programs into WHILE programs. Information Processing 7 l, North-Holland Pub. Co., Amsterdam, pp. 250-255.
• 2: Arsac, J. La Construction de Programrnes Structures. Dunod, Paris, 1977.
• 3: Arsac, J. Emploi de methodes constructives en programmation. Un dossier: la fonction d'Ackerman. RAIRO d'Informatique Theorique, Vol. l, 1977, pp. 7-28.
• 4: Jacques J. Arsac, Langages sans Etiquettes et Transformations de Programmes, Proceedings of the 2nd Colloquium on Automata, Languages and Programming, p.112-128, July 29-August 02, 1974
• 5: Brenda S. Baker, An Algorithm for Structuring Flowgraphs, Journal of the ACM (JACM), v.24 n.1, p.98-120, Jan. 1977 [doi>10.1145/321992.321999]
• 6: R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
• 7: Cousineau, G. Transformation de programmes iteratifs. In Programmation, B. Robinet, Ed., Dunod, Paris, 1977, pp. 53-74.
• 8: Darlington, J., and Burstall, R. M. A system which automatically improves programs. Aeta lnformatica 6 (1976), 41-60.
• 9: De Millo, R., Einsenstadt, S., and Lipton, R. Space-time trade offs in structured programming. Johns Hopkins Conf. Information Systems and Science, 1976.
• 10: Floyd, R. W., and Knuth, D. E. Notes on avoiding GO TO statements. Information processing letters, Vol. 1, 1971, pp. 23-31.
• 11: Gerhardt, S. L. Knowledge about programs: a model and case study. IEEE Cone Reliable Software, Los Angeles, 1975, IEEE Cat. 75, CHO 940, pp. 89-93.
• 12: Gerhardt, S. L. Proof theory of partial correctness verification systems. SlAM J. Comptng. 5, 3 (1976), 355-377.
• 13: C. A. R. Hoare, Algorithm 63: partition, Communications of the ACM, v.4 n.7, p.321, July 1961 [doi>10.1145/366622.366642]
• 14: lrlik, J. Translating some recursive procedures into iterative schemes. In Programmation, B. Robinet, Ed., Dunod, Paris, 1977, pp. 39-52.
• 15: Donald E. Knuth, Structured Programming with go to Statements, ACM Computing Surveys (CSUR), v.6 n.4, p.261-301, Dec. 1974 [doi>10.1145/356635.356640]
• 16: Kosaraju, R. S. Analysis of structured programs. J. Comptr. and S),st. Sci. 9 (1974), 232-255.
• 17: Henry F. Ledgard , Michael Marcotty, A genealogy of control structures, Communications of the ACM, v.18 n.11, p.629-639, Nov. 1975 [doi>10.1145/361219.361222]
• 18: David B. Loveman, Program Improvement by Source-to-Source Transformation, Journal of the ACM (JACM), v.24 n.1, p.121-145, Jan. 1977 [doi>10.1145/321992.322000]
• 19: L. Nolin , G. Ruggiu, Formalization of EXEL, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.108-119, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512937]
• 20: W. W. Peterson , T. Kasami , N. Tokura, On the capabilities of while, repeat, and exit statements, Communications of the ACM, v.16 n.8, p.503-512, Aug. 1973 [doi>10.1145/355609.362337]
• 21: H. Gordon Rice, Recursion and iteration, Communications of the ACM, v.8 n.2, p.114-115, Feb. 1965 [doi>10.1145/363744.363781]
• 22: Thomas A. Standish , Dennis F. Kibler , James M. Neighbors, Improving and refining programs by program manipulation, Proceedings of the annual conference, p.509-516, October 20-22, 1976, Houston, Texas, United States [doi>10.1145/800191.805652]
• 23: Urschler, G. Automatic structuring of programs. IBM J. Res. Develop. (1975), 181-194.
• 24: Wegbreit, B. Goal directed program transformation. IEEE Trans. Software Eng. SE-2, 2 (1976), 69-80.

INDEX TERMS

Keywords:
control structures, program transforms, structured programming