Denotational semantics as a specification of code generators

ABSTRACT

We describe the automatic generation - from the formal denotational semantic specification - of an efficient compiler's code generation phase, producing efficient code for real machines. The method has been succesfully implemented and tested with languages as complex as GEDANKEN!

REFERENCES

• 1: Formal Definition of the ADA Programming Language. Preliminary version. INRIA, 1980.
• 2: H. Ganzinger. Transforming Denotational Semantics into Practical Attribute Grammars. Lecture Notes in Computer Science 94. Springer-Verlag, 1980.
• 3: Martin C. Henson , Raymond Turner, Completion semantics and interpreter generation, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.242-254, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582180]
• 4: N.D.Jones and D.A.Schimdt. Compiler Generation from Denotational Semantics. Lecture Notes in Computer Science 94. Springer-Verlag, 1980.
• 5: P.D.Mosses. Mathematical Semantics and Compiler Generation. PhD. thesis. University of Oxford, 1975.
• 6: P.D.Mosses. Compiler Generation using Denotational Semantics. Mathematical Foundations of Computer Science. Lecture Notes in Computer Science 45. Springer-Verlag, 1976.
• 7: P.D.Mosses. SIS: A Compiler Generator System using Denotational Semantics. Reference Manual, University of Aarhus, 1978.
• 8: 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]
• 9: System Structure for Software Fault Tolerance. IEEE Transactions on Software Engineering, SE-1. 1975
• 10: M.R.Raskovsky and R.Turner. Compiler Generation and Denotational Semantics. Fundamentals of Computation Theory, 1979.
• 11: 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
• 12: M.R.Raskovsky. Generating a Real Compiler from a Denotational Semantics. Seminar Review. Institut National de Recherche en Informatique et en Automatique, 1981.
• 13: M.R.Raskovsky. ISL: The transformation rules. Departamental Memo #43, Department of Computing Science, Essex University, 1982
• 14: M.R.Raskovsky. ISL: Automatic Generation of: a Code Generator for Stoy's example language. Departamental Memo #44, Department of Computing Science, Essex University, 1982
• 15: M.R.Raskovsky. ISL: Automatic Generation of: a Code Generator for GEDANKEN. Departamental Memo #45, Department of Computing Science, Essex University, 1982
• 16: John C. Reynolds, G/EDANKEN—a simple typeless language based on the principle of completeness and the reference concept, Communications of the ACM, v.13 n.5, p.308-319, May 1970 [doi>10.1145/362349.362364]
• 17: M. Richards , C. Whitby-Strevens, BCPL: The Language and its Compiler, Cambridge University Press, New York, NY, 1981
• 18: Joseph E. Stoy, Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, MIT Press, Cambridge, MA, 1977
• 19: C.Strachey. Towards a Formal Semantics. Formal Language Description Languages for Computer Programming, pp 198-220. (Ed. T.B.Steel). North-Holland, Amsterdam, 1966.
• 20: C.Strachey. The Varieties of Programming Languages. Technical Monograph PRG-10, Programming Research Group, University of Oxford, 1973
• 21: B.Sufrin. LLI: A Parser Generator. Department of Computing Science, Essex University, 1978.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Denotational semantics

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation; Translator writing systems and compiler generators

General Terms:
Languages