Goal-directed program transformation

ABSTRACT

Program development often proceeds by transforming simple, clear programs into complex, involuted, but more efficient ones. This paper examines ways this process can be rendered more systematic. We show how analysis of program performance, partial evaluation of functions, and abstraction of recursive function definitions from recurring subgoals can be combined to yield many global transformations in a methodical fashion. Examples are drawn from compiler optimization, list processing, very high level languages, and APL execution.

REFERENCES

• 1: Abrams, P. An APL Machine. SLAC-14, Stanford Linear Accelerator Center, Feb. 1970.
• 2: ACM Sigplan Symp. on Very High Level Languages. Sigplan Notices, 9, 4, April 1974.
• 3: Allen, F.E. and Cocke, J. A catalogue of optimizing transformations. In R. Rustin (Ed.) Design and Optimization of Compilers, Prentice-Hall, 1972, 1-30.
• 4: Battarel, G. et al. Optimized interpretation of APL statements. In P. Gjerlov, H.J. Helms, and J. Nielsen (Eds.) APL Congress 73, North-Holland, 1973, 49-57.
• 5: Beckman, L. et al. A partial evaluator and its use as a programming tool. Dept. of Computer Sciences, Uppsala University, Sweden, Nov. 1974.
• 6: Robert S. Boyer , J. Strother Moore, Proving Theorems about LISP Functions, Journal of the ACM (JACM), v.22 n.1, p.129-144, Jan. 1975 [doi>10.1145/321864.321875]
• 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: Chin-Liang Chang , Richard C. Lee , Richard Char-Tung Lee, Symbolic Logic and Mechanical Theorem Proving, Academic Press, Inc., Orlando, FL, 1997
• 9: Cheatham, T.E. and Wegbreit, B. A laboratory for the study of automating programming. AFIPS Conf. Proc., Vol. 70 (Spring 1972), 11-21.
• 10: Jacques Cohen , Carl Zuckerman, Two languages for estimating program efficiency, Communications of the ACM, v.17 n.6, p.301-308, June 1974 [doi>10.1145/355616.361015]
• 11: Dijkstra, E.W. Notes on structured programming. In O.J. Dahl, E.W. Dijkstra, and C.A.R. Hoare (Eds.) Structured Programming, Academic Press, 1972, 1-82.
• 12: Jay Earley, High level operations in automatic programming, Proceedings of the ACM SIGPLAN symposium on Very high level languages, p.34-42, March 28-29, 1974, Santa Monica, California, United States
• 13: 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]
• 14: Henderson, P. and Morris, J.H. A lazy evaluator. CSL, Xerox Palo Alto Research Center, August 1975.
• 15: Holt, A.W. et al. Final report for the information system theory project. Applied Data Research, Inc., New York, Feb. 1968.
• 16: Kenneth E. Iverson, A Programming Language., John Wiley & Sons, 1962
• 17: Lombardi, L.A. and Raphael, B. Lisp as the language for an incremental computer. In E.C. Berkeley and D.G. Bobrow (Eds.) The Programming Language LISP: Its Operation and Applications, MIT Press, Cambridge, 1964, 204-219.
• 18: Manna, Z. and Waldinger, R. Knowledge and reasoning in program synthesis. Stanford Research Inst., Menlo Park, CA, Nov. 1974.
• 19: Pakin, S. APL/360 Reference Manual. Science Research Associates, Inc. 1968.
• 20: Sanderwall, E.A. Programming tool for management of predicate-calculus-oriented data bases. Proc. Second Int. Joint Conf. on Artificial Intelligence, British Computer Society, 1971.
• 21: J. T. Schwartz, Automatic and semiautomatic optimization of SETL, Proceedings of the ACM SIGPLAN symposium on Very high level languages, p.43-49, March 28-29, 1974, Santa Monica, California, United States
• 22: Vuillemin, J. Correct and optimal implementations of recursion in a simple programming language. JCSS, 9, 3 (Dec. 1974), 332-353.
• 23: Ben Wegbreit, Mechanical program analysis, Communications of the ACM, v.18 n.9, p.528-539, Sept. 1975 [doi>10.1145/361002.361016]

INDEX TERMS

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

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

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Mechanical theorem proving

General Terms:
Algorithms, Languages, Performance, Theory

Keywords:
APL, Analysis of programs, Compiler optimization, Evaluation in context, Execution analysis, Generalization, Lisp, List processing, Optimizing transformations, Partial evaluation, Program analysiss, Program transformation, Simplification, Very high level language