Loops in combinator-based compilers

ABSTRACT

In our paper [Wand 82a], we introduced a paradigm for compilation based on combinators. A program from a source language is translated (via a semantic definition) to trees of combinators; the tree is simplified (via associative and distributive laws) to a linear, assembly-language-like format: the "compiler writer's virtual machine" operates by simulating a reduction sequence of the simplified tree. The correctness of these transformations follows from general results about the λ-calculus. The code produced by such n generator is always tree-like. In this paper, the method is extended to produce target code with explicit loops. This is done by re-introducing variables into the terms of the target language in a restricted way, along with a structured binding operator.

REFERENCES

• 1: {Barendregt 81} Barendregt, H. P. The Lambda Calculus: Its Syntax and Semantics, North-Holland, Amsterdam, 1981.
• 2: Robert Milne , C. Strachey, A Theory of Programming Language Semantics, Halsted Press, New York, NY, 1977
• 3: Martin R. Raskovsky , Philip A. Collier, From standard to implementation denotational semantics, Semantics-Directed Compiler Generation, Proceedings of a Workshop, p.94-139, January 14-18, 1980
• 4: Ravi Sethi, Circular Expressions: Elimination of Static Environments, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.378-392, July 13-17, 1981
• 5: Ravi Sethi, Control flow aspects of semantics directed compiling (Summary), Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.245-260, June 23-25, 1982, Boston, Massachusetts, United States
• 6: {Thatcher et al. 81} Thatcher, J. W., Wagner, E. G., and Wright, J. B. "More on Advice on Structuring Compilers and Proving Them Correct" Theoret. Comp. Sci. 15 (1981), 223-250.
• 7: {Turing 37} Turing, A. M. "The p-functions in λ-K-conversion" J. Symbolic Logic 2 (1937), 164.
• 8: {Turner 79} Turner, D. A. "A New Implementation Technique for Applicative Languages" Software-Practice and Experience 9 (1979), 31-49.
• 9: {Wand 80} Wand, M. "Different Advice on Structuring Compilers and Proving Them Correct", Indiana University Computer Science Department Technical Report No. 95 (September, 1980).
• 10: Mitchell Wand, Semantics-directed machine architecture, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.234-241, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582179]
• 11: Mitchell Wand, Deriving Target Code as a Representation of Continuation Semantics, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.496-517, July 1982 [doi>10.1145/357172.357179]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Denotational semantics
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Lambda calculus and related systems

General Terms:
Languages, Theory

Keywords:
combinators, loops