Experiments with a supercompiler

ABSTRACT

In this paper we present and discuss some examples of the operation of the first experimental model of a supercompiler. We have chosen our examples to serve as “exhibits” which highlight most important features of the supercompiler and intimate its potential uses (this is reflected in section names). The acquaintance with REFAL is not assumed in this paper; our comments will be sufficient for a reader experienced in programming languages to understand REFAL programs (and almost to learn REFAL in the process).

REFERENCES

• 1: 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]
• 2: 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
• 3: Turchin, V.F. The Language REFAL, the Theory of Compilation, and Metasystem Analysis. Courant Institute Report #20, New York, 1980.
• 4: Ershov, E.P. On the essence of translation. in: Neuhold, Editor, Formal Description of Programming Concepts, North-Holland Publ. Co. (1978) pp. 391-418.
• 5: H. Jan Komorowski, Partial evaluation as a means for inferencing data structures in an applicative language: a theory and implementation in the case of prolog, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.255-267, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582181]
• 6: Vuillemin, J. Correct and optimal implementation of recursion in a simple programming language. Journal of Computer and System Sciences, vol. 9, No. 3, Dec. 1974.
• 7: 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]
• 8: Friedman, D.P., and Wise, D.S., CONS should not evaluate its argument in: Michaelson and Milner Editors, Automata, Languages, and Programming, Edinburgh Univ. Press (1967), pp. 257-284.
• 9: Valentin F. Turchin, The Use of Metasystem Transition in Theorem Proving and Program Optimization, Proceedings of the 7th Colloquium on Automata, Languages and Programming, p.645-657, July 14-18, 1980

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
      D.3.2 Language Classifications
          Subjects: Data-flow languages

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Partial evaluation

General Terms:
Languages, Theory