Program Improvement by Source-to-Source Transformation

ABSTRACT

The use of source-to-source program transformations has proved valuable in improving program performance. The concept of program manipulation is elucidated by describing its role in both conventional optimization and high level modification of conditional, looping, and procedure structures. An example program fragment written in an Algol-like language is greatly improved by transformations enabled by a user-provided assertion about a data array. A compilation model based on the use of source-to-source program transformations is used to provide a framework for discussing issues of code generation, compilation of high level languages such as APL, and eliminating overhead commonly associated with modular structured programming. Application of the compilation model to several different languages is discussed.

REFERENCES

• 1: ABRAMS, P An APL machine, SU-SEL-70-017, Stanford Electron Lab Stanford, Cahf, Feb. 1970
• 2: ACM SIGPLAN Symposmm on very high level languages SIGPLAN Nouces (ACM) 9, 4 (April 1974)
• 3: ACM SIGPLAN. Proceedings of a symposmm on compder optimization. SIGPLAN Nouces (ACM) 5, 7 (July 1970)
• 4: ALLEN, F.E., AND COCKE, J A catalogue of opUmlzlng transformations In Destgn and Opttmtzatton of Compilers, R Rustm, Ed , Prentice-Hall, Englewood Cliffs, N J , 1972, pp 1-30
• 5: BeatRisro, D, ANO SArrERLY, K BETA laboratory Final Rep CADD-7312-3111, Mass Computer Associates, Inc, Wakefield, Mass., Dec 1973
• 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: CARTER, J L A case study of a new compdlng code generation techmque RC 5666, IBM Thomas J Watson Res Ctr, Yorktown Heights, N Y, Oct 1975
• 8: T. E. Cheatham , J. A. Townley, Symbolic evaluation of programs: a look at loop analysis, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.90-96, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806327]
• 9: CHEATHAM, T E, Arid WEGaREIT, B A laboratory for the study of automatic programming Proc. AFIPS 1972 SJCC, Vol 40, AFIPS Press, Montvale, N J , pp 11-21.
• 10: Susan L. Gerhart, Correctness-preserving program transformations, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.54-66, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512983]
• 11: GESCHKE, C M Global program optlmlzauons Ph D Th , Comptr Scl Dep , Carnegie-Mellon U , Pittsburgh, Pa, 1972
• 12: C. A. R. Hoare, Hints on programming language design., Stanford University, Stanford, CA, 1973
• 13: I~GALLS. D The execution tame profile as a programming tool In Design and Optzmzzatton of Comptlers, R Rustm, Ed , Prent,ce-Hall, Englewood Chffs, N J , 1972, pp. 107-128
• 14: KARR~ M Gathering mformat~on about programs CA-7507-1411, Mass Computer Associates, Inc, Wakefield, Mass , July 1975
• 15: KAttR, M On affine relationships among variables of a program Acta InformaOca 6, 2 (1976), 133-152
• 16: 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]
• 17: LAMPORT, L Parallel execution on array and vector computers Proc 1975 Sagamore Conf. on Parallel Processing, Syracuse U , Aug 1975, pp 187-191
• 18: Leslie Lamport, The parallel execution of DO loops, Communications of the ACM, v.17 n.2, p.83-93, Feb. 1974 [doi>10.1145/360827.360844]
• 19: LOVEMAN, D An ATE language processing system Autotestcon 76 Formally Automat,c Support Systems for Advanced Mamtamabd~ty, IEEE, New York, 1976, pp 1-9
• 20: David B. Loveman , Ross A. Faneuf, Program optimization - theory and practice, Proceedings of the conference on Programming languages and compilers for parallel and vector machines, p.97-102, March 18-19, 1975, New York, New York
• 21: David L. Presberg, The Paralyzer: Ivtran's Parallelism Analyzer and Synthesizer, Proceedings of the conference on Programming languages and compilers for parallel and vector machines, p.9-16, March 18-19, 1975, New York, New York
• 22: Marvin Schaefer, A mathematical theory of global program optimization (Prentice-Hall series in automatic computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1973
• 23: SCHNECK, P B , AND ANGEL, E A FORTRAN to FORTRAN optimizing compiler Computer J 16, 4 (Nov 1973), 322-330
• 24: SHAPIRO, R M , AND SAINT, H The representation of algorithms Final Tech. Rep RADC-TR-69-313, Applied Data Research, Inc , Vol II, Rome Air Develop Ctr., Sept 1969
• 25: 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]
• 26: STANOISH, T, HARRIMAN, D, KIBLER, D, AND NEIGHBORS, J The Irvlne program transformation catalogue Dep Inform and Cornptr Scl , U of California at Irvlne, Irvlne, Cahf, Jan 1976
• 27: VANTASSEL, D Program Style, Design Efficmncy, Debugging and Testing Prentice-Hall, Englewood Chffs. N J , 1974
• 28: WEGBREIT, B Goal-directed program transformation IEEE Trans on Software Eng SE-2, 2 (June 1976), 69-80
• 29: WEGBREIT, B Property extraction in well-founded property sets IEEE Trans on Software Eng SE-1, 3 (Sept. I975), 270-285
• 30: WEGBRE1T, B The ECL programming system Proc AFIPS FJCC, Vol 39, AFIPS Press, Montvale, N J, 253-262
• 31: W. A. Wulf , D. B. Russell , A. N. Habermann, BLISS: a language for systems programming, Communications of the ACM, v.14 n.12, p.780-790, Dec. 1971 [doi>10.1145/362919.362936]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving

          Nouns: Prolog

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

General Terms:
Languages, Performance, Theory