Semantics-directed machine architecture

ABSTRACT

We show how to analyze the denotational semantics for a programming language to obtain a compiler and a suitable target machine for the language. We do this by rewriting the equations using suitable combinators. The machine operates by simulating the reduction sequences for the combinator terms. The reduction sequences pass through certain standard forms, which become an architecture for the machine, and the combinators become machine instructions. Despite the abstract nature of its development, the machine greatly resembles a conventional one. The method is illustrated by a simple expression language with procedures and input-output.

REFERENCES

• 1: Benjamin M. Brosgol, TCOLAda and the “Middle End” of the PQCC Ada compiler, Proceedings of the ACM-SIGPLAN symposium on The ADA programming language, p.101-112, January 1980 [doi>10.1145/800004.807940]
• 2: T. J.W. Clarke , P. J.S. Gladstone , C. D. MacLean , A. C. Norman, SKIM - The S, K, I reduction machine, Proceedings of the 1980 ACM conference on LISP and functional programming, p.128-135, August 25-27, 1980, Stanford University, California, United States [doi>10.1145/800087.802798]
• 3: Curry, H. B., and Feys, R. Combinatory Logic, Vol. 1. North- Holland, Amsterdam, 1958.
• 4: Federhen, S. "A Mathematical Semantics for PLANNER" M.S. Thesis, University of Maryland, 1980.
• 5: Michael J. C. Gordon, The Denotational Description of Programming Languages: An Introduction, Springer-Verlag New York, Inc., Secaucus, NJ, 1979
• 6: Neil D. Jones, Semantics-Directed Compiler Generation: Proceedings, Springer-Verlag New York, Inc., Secaucus, NJ, 1980
• 7: 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
• 8: F. Lockwood Morris, Advice on structuring compilers and proving them correct, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.144-152, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512941]
• 9: Mosses, P. D. "Mathematical Semantics and Compiler Generation", D. Phil thesis, Oxford Univ., 1975.
• 10: Peter D. Mosses, A Constructive Approach to Compiler Correctness, Proceedings of the 7th Colloquium on Automata, Languages and Programming, p.449-469, July 14-18, 1980
• 11: Michael J. O'Donnell, Computing in Systems Described by Equations, Springer-Verlag New York, Inc., Secaucus, NJ, 1977
• 12: Raoult, J. C., and Sethi, R. "On metalanguages for a compiler generator: properties of a notation for combining functions", manuscript, Bell Laboratories, Murray Hill, N.J. (July, 1981).
• 13: 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
• 14: 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
• 15: Joseph E. Stoy, Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, MIT Press, Cambridge, MA, 1977
• 16: 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--249.
• 17: Turner, D. A. "A New Implementation Technique for Applicative Languages" Software: Practice and Experience 9 (1979), 31--49.
• 18: 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]
• 19: Wand, M. "Different Advice on Structuring Compilers and Proving Them Correct" Indiana University Computer Science Department, Technical Report No. 95 (September, 1980).