Realistic compilation by program transformation (detailed summary)

ABSTRACT

Using concepts from denotational semantics, we have produced a very simple compiler that can be used to compile standard programming languages and produces object code as efficient as that of production compilers. The compiler is based entirely on source-to-source transformations performed on programs that have been translated into an intermediate language resembling the lambda calculus. The output of the compiler, while still in the intermediate language, can be trivially translated into machine code for the target machine. The compilation by transformation strategy is simple: the goal is to remove any dependencies on the intermediate language semantics that the target machine cannot implement directly. Front-ends have been written for Pascal, BASIC, and Scheme and the compiler produces code for the MC68020 microprocessor.

REFERENCES

• Boyle 84: James M. Boyle and Monagur N. Muralidharan. Program reusability through program transformation. in IEEE Transactions on, Software Engineering SE- 10(5):574-588, September 1984.
• Boyle 86: J. M. Boyle , K. W. Dritz , M. N. Muralidharan , R. J. Taylor, Deriving sequential and parallel programs from pure LISP specifications by program transformation, The IFIP TC2/WG 2.1 Working Conference on Program specification and transformation, p.1-19, June 1987, Bad To:9Ailz, Germany
• Brooks 82: Rodney A. Brooks , Richard P. Gabriel , Guy L. Steele, Jr., An optimizing compiler for lexically scoped LISP, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.261-275, June 23-25, 1982, Boston, Massachusetts, United States
• Feeley: M. Feeley and G. Lapalme. Closure generation based on viewing LAMBDA as EPSILON plus COMPILE. D~partement d'informatique et de recherche op~rationnelle (I.R.O.), Universit~ de MontrSal, P.O.B. 6128, Station A, Montreal, QuSbec, H3C3J7 (Canada).
• Johnsson 87: Thomas Johnsson. Lambda lifting: Transforming programs into recursire equations. In Compiling Lazy Functional Languages. PhD thesis, Chalmers University of Technology, 1987
• Kelsey 89: Richard Andrews Kelsey, Compilation by program transformation, 1989
• Kranz 86: David Kranz , Norman Adams , Richard Kelsey , Jonathan Rees , Paul Hudak , James Philbin, ORBIT: an optimizing compiler for scheme, ACM SIGPLAN Notices, v.21 n.7, p.219-233, July 1986
• Lee 87: P. Lee, The automatic generation of realistic compilers from high-level semantic descriptions, University of Michigan, Ann Arbor, MI, 1987
• Paulson 82: Lawrence Paulson, A semantics-directed compiler generator, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.224-233, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582178]
• Plotkin 75: G. D. Plotkin. Call-by-name, call-by-value and the A-calcuhs. in Theoretical Computer Science 1:125-159, 1975.
• Rees 84: Jonathan A. Rees, Norman I. Adams, and James R. Meehan. The T manual, fourth edition. Yale University Computer Science Department, January 1984.
• Standish 76: T. A. Standish, D. C. harriman, D. F. Kibler, and J. M. Neighbors. The Irvine program transformation catalogue Department of Information and Computer Science, University of California at Irvine, 1976.
• Steele 78: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Functional constructs

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: T
      D.3.4 Processors
          Subjects: Compilers

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

General Terms:
Languages