Program improvement by source to source transformation

ABSTRACT

We treat a program as an object of manipulation, determine items of program constancy, and simplify the program based on the constancy. Some motivation for program manipulation is presented, along with two examples of “higher level optimization” written in an Algol-like language. A collection of program transformations and a model of the compilation process in terms of source-to-source transformations are presented. Finally a description of the application of these ideas to an existing programming language is given.

REFERENCES

• 1: Abrams, Philip: {APL}, "An APL Machine", Stanford Electronics Laboratory, SU-SEL-70-017, February 1970.
• 2: ACM Sigplan: {Languages}, Symposium on Very High Level Languages, Sigplan Notices, 9, 4 April 1974.
• 3: ACM Sigplan: {Optimization}, Proceedings of a Symposium on Compiler Optimization, Sigplan Notices, July 1970.
• 4: Allen, Frances E. and Cocke, John: {Catalogue}, "A Catalogue of Optimizing Transformations", in R. Rustin (Ed.) Design and Optimization of Compilers, Prentice-Hall 1972.
• 5: Bearisto, David and Sattley, Kirk: {Laboratory}, "BETA Laboratory", Final Report, Mass. Computer Associates, Inc., CADD-7312-3111, December 31, 1973.
• 6: Beckman, Lenhart et al: {Evaluator}, "A Partial Evaluator and its use as a Programming Tool", Dept. of Computer Sciences, Uppsala University, Sweden, November 1974.
• 7: R. M. Burstall , John Darlington, Some transformations for developing recursive programs, Proceedings of the international conference on Reliable software, p.465-472, April 21-23, 1975, Los Angeles, California
• 8: Cheatham, T. E.: {Evaluator}, "EL1 Symbolic Evaluator-Design Notes", working paper.
• 9: T. E. Cheatham, Jr. , Ben Wegbreit, On a laboratory for the study of automating programming, Proceedings of ACM conference on Proving assertions about programs, p.208-211, January 06-07, 1972, Las Cruces, New Mexico, United States
• 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: Charles Matthew Geschke, Global program optimizations., 1973
• 12: C. A. R. Hoare, Hints on programming language design., Stanford University, Stanford, CA, 1973
• 13: Karr, Michael: {Information}, "Gathering Information About Programs", Mass. Computer Associates, Inc., CA-7507-1411, July 14, 1975.
• 14: Karr, Michael: {Assignment}, "The Assignment of Scalar Variables to Memory Cells", Mass. Computer Associates, Inc., CAID-7501-0611, January 1975.
• 15: Karr, Michael: {Inequalities}, "Proving Inequalities", Mass. Computer Associates, Inc., CA-7406-1011, June 1974. Submitted for publication.
• 16: Karr, Michael: {Affine}, "Affine Relationships Among Variables of a Program", Mass. Computer Associates, Inc., CA-7402-2811, June 1974. Accepted for publication by Acta Informatica.
• 17: 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]
• 18: Lamport, Leslie: {Parallel}, "Parallel Execution on Array and Vector Computers ", Proceedings of the 1975 Sagamore Conference on Parallel Processing, August 1975.
• 19: Leslie Lamport, The Hyperplane Method for an Array Computer, Proceedings of the Sagamore Computer Conference on Parallel Processing, p.113-131, August 20-23, 1974
• 20: 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]
• 21: Lamport, Leslie: {Coordinate}, "The Coordinate Method for the Parallel Execution of DO Loops", Proceedings of the 1973 Sagamore Conference on Parallel Processing, August 1973.
• 22: Loveman, David: {Transformation}, "Source-to-Source Transformation of Programs", in preparation.
• 23: Loveman, David, Bearisto, David, Karr, Michael and Sattley, Kirk: {Development 1975}, "Development of Compiler Optimization Techniques", Mass. Computer Associates, Inc., CADD-7508-3111, August 31, 1975.
• 24: 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
• 25: Loveman, David: {K in a Row}, "The 'K in a Row' Problem ", Mass. Computer Associates, Inc., CADD-7412-0411, December 4, 1974.
• 26: Loveman, David, Sattley, Kirk and Bearisto, David: {Development 1974}, "Development of Compiler Optimization Techniques", Mass. Computer Associates, Inc., CADD-7407-2311, July 1974.
• 27: Loveman, David: {Replacement}, "On the Compilation of the Beta Replacement Statement", Mass. Computer Associates, Inc., CADD-7308-0911, August 9, 1973.
• 28: Presberg, David and Johnson, Neil: {Paralyzer}, "The Paralyzer, IVTRAN's Parallelism Analyzer and Synthesizer", Proceedings of a Conference on Programming Languages and Compilers for Parallel and Vector Machines, Sigplan Notices, Vol. 10, No. 3, March 1975.
• 29: Saint, Harry: {Ordering}, "The Partial Ordering of Loops and Array References", Mass. Computer Associates, Inc., CADD-7312-3112, December 31, 1973.
• 30: Marvin Schaefer, A mathematical theory of global program optimization (Prentice-Hall series in automatic computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1973
• 31: Shapiro, Robert M. and Saint, Harry: {Algorithms}, "The Representation of Algorithms", Applied Data Research, Inc., Final Technical Report. RADC-TR-69-313, Vol. II, Rome Air Development Center, September 1969.
• 32: Ben Wegbreit, Mechanical program analysis, Communications of the ACM, v.18 n.9, p.528-539, Sept. 1975 [doi>10.1145/361002.361016]
• 33: Wegbreit, Ben: {Extraction}, "Property Extraction in Well-Founded Property Sets ", IEEE Transactions on Software Engineering, Vol. SE-1, No. 3, September 1975.
• 34: Wegbreit, Ben: {Transformation}, "Goal-Directed Program Transformation", Xerox Palo Alto Research Center, September 1975.
• 35: Ben Wegbreit, The synthesis of loop predicates, Communications of the ACM, v.17 n.2, p.102-113, Feb. 1974 [doi>10.1145/360827.360850]
• 36: Wegbreit, Ben: {Closure}, "Procedure Closure in EL1", The Computer Journal, Vol. 17, No. 1, February 1974.
• 37: Wegbreit, Ben: {ECL}, "The ECL Programming System", Proc. FJCC, Vol. 39, pp.253-262, 1971.
• 38: 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:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation

General Terms:
Algorithms, Languages, Performance, Theory

Keywords:
Compilation, Optimization, Program improvement, Program manipulation, Source-to-source transformation