The concept of a supercompiler

ABSTRACT

A supercompiler is a program transformer of a certain type. It traces the possible generalized histories of computation by the original program, and compiles an equivalent program, reducing in the process the redundancy that could be present in the original program. The nature of the redundancy that can be eliminated by supercompilation may be various, e.g., some variables might have predefined values (as in partial evaluation), or the structure of control transfer could be made more efficient (as in lazy evaluation), or it could simply be the fact that the same variable is used more than once. The general principles of supercompilation are described and compared with the usual approach to program transformation as a stepwise application of a number of equivalence rules. It is argued that the language Refal serves the needs of supercompilation best. Refal is formally defined and compared with Prolog and other languages. Examples are given of the operation of a Refal supercompiler implemented at CCNY on an IBM/370.

REFERENCES

• 1: BECKMAN, L., HARALDSON, A., OSKARSON, O., AND SANDEWALL, O. A partial evaluator and its use as a programming tool. Arti{. InteU. 7 (1974), 319-357.
• 2: 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]
• 3: ERSHOV, A.P. On the essence of translation. In Formal Description of Programming Concepts, E. J. Neuhold, Ed., North-Holland, Amsterdam, 1977, 391-418.
• 4: ERSHOV, A. P. Mixed computation: Potential applications and problems for future studies. Theor. Comput. Sci. 18 (1982), 41-67.
• 5: FRIEDMAN, D. P., AND WISE, D.S. CONS should not evaluate its arguments. In Automata, Languages and Programming, Michaelson and Millner, Eds, Edinburgh University Press, 1967, 257-284.
• 6: FUTAMURA, Y. Partial evaluation of computation process--an approach to a compiler-compiler. Syst. Comput. Control 2, 5 (1971), 45-50.
• 7: Yoshihiko Futamura, Parital Computation of Programs, Proceedings of RIMS Symposium on Software Science and Engineering, p.1-35, January 1983
• 8: Peter Henderson , James H. Morris, Jr., A lazy evaluator, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.95-103, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811543]
• 9: Neil D. Jones , David A. Schmidt, Compiler generation from denotational semantics, Semantics-Directed Compiler Generation, Proceedings of a Workshop, p.70-93, January 14-18, 1980
• 10: Neil D. Jones , Peter Sestoft , Harald Sondergaard, An experiment in partial evaluation: the generation of a compiler generator, Proc. of the first international conference on Rewriting techniques and applications, p.124-140, December 1985, Dijon, France
• 11: JONES, N., AND TOFTE, M. Some principles and notation for the construction of compiler generators. DIKU, Internal Rep., Univ. of Copenhagen, 1983.
• 12: LOMBARDI, L.A. Incremental computation. In Advances in Computers, 8, Academic Press, New York, 1967.
• 13: NILLSON, N.J. Artificial intelligence prepares for 2001. AI Mag. 4 (1983), 7-14.
• 14: O'SHEA, T., AND EISENSTADT, M. Artificial Intelligence. Harper and Row, New York, 1984.
• 15: H. Partsch , R. Steinbrüggen, Program Transformation Systems, ACM Computing Surveys (CSUR), v.15 n.3, p.199-236, Sept. 1983 [doi>10.1145/356914.356917]
• 16: REDDY, U. Narrowing as the operational semantics of functional languages. Submitted to the Symposium on Logic Programming (Boston, 1985).
• 17: Basic Refal and its Implementation on Computers. GOSSTROI SSSR, TsNIPIASS, Moscow, 1977. The authors are not indicated in the book. They are: V. F. Khoroshevski, And. V. Klimov, Ark. V. Klimov, A. G. Krasovski, S. A. Romanenko, I. B. Shchenkov, and V. F. Turchin. (In Russian)
• 18: SOWA, J.F. A prologue to Prolog. Draft, distributed with permission of the author, 1984.
• 19: TURCmN, V.F. Equivalent transformation of recursive functions defined in Refal. In Trudy Vsesoyuzn. Simpos. "Teoria Yazykov i metody progr," Alushta-Kiev, 1972, 31-42. (In Russian)
• 20: V. F. Turchin, A supercompiler system based on the language REFAL, ACM SIGPLAN Notices, v.14 n.2, p.46-54, February 1979 [doi>10.1145/954063.954069]
• 21: TURCHIN, V. F. The language Refal, the theory of compilation, and metasystem analysis. Courant Institute Rep. 20, 1980.
• 22: Valentin F. Turchin, Semantic definitions in REFAL and the automatic production of compilers, Semantics-Directed Compiler Generation, Proceedings of a Workshop, p.441-474, January 14-18, 1980
• 23: Valentin F. Turchin , Robert M. Nirenberg , Dimitri V. Turchin, Experiments with a supercompiler, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.47-55, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802134]
• 24: VUILLEMIN, J. Correct and optimal implementation of recursion in a simple programming language. J. Comput. Syst. Stud. 9, 3 (Dec. 1974).

INDEX TERMS

Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Refal
      D.3.4 Processors
          Subjects: Optimization; Compilers

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Algorithms, Design, Languages, Performance, Theory