Operational semantics-directed compilers and machine architectures

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Operational semantics-directed compilers and machine architectures

Full text

Pdf (2.13 MB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 16 , Issue 4 (July 1994) table of contents

Pages: 1215 - 1247

Year of Publication: 1994

ISSN:0164-0925

Author

John Hannan

The Pennsylvania State University

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 26, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/183432.183458 What is a DOI?

ABSTRACT

We consider the task of automatically constructing intermediate-level machine architectures and compilers generating code for these architectures, given operational semantics for source languages. We use operational semantics in the form of abstract machines given by rewrite systems in which the rewrite rules operate on terms representing states of computations. To construct compilers and new architectures we employ a particular strategy called pass separation, a form of staging transformation, that takes a program p and constructs a pair of programs p1, p2 such that p(x, y) = p2(p1(x), y)) for all x,y. If p represents an operational semantics for a language, with arguments x and y denoting a source program and its input data, then pass separation constructs programs p1 and p2 corresponding to a compiler and an executor. The compiler translates the source language into an intermediate-level target language, and the executor provides the definition for this language. Our use of pass separation supports the automatic definition of target languages or architectures, and the structure of these architectures is directed by the structure of the given source semantics. These architectures resemble abstract machine languages found in hand-crafted compilers. Our method is restricted to a limited class of abstract machines given as term-rewriting systems, but we argue that this class encompasses a large set of language definitions derived from more natural operational semantics. We provide two examples of our method by constructing compilers and target architectures for a simple functional language and a simple imperative language. Though we construct these architectures automatically, they bear a striking resemblance to existing architectures constructed by hand.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. Bondorf, Automatic autoprojection of higher order recursive equations, Proceedings of the third European symposium on programming on ESOP '90, p.70-87, May 1990, Copenhagen, Denmark
	2	BONDORF, A. AND DANVY, O. 1990. Automatic autoprojection of recursive equations with global variables and abstract data types. Tech. Rep. 90/4, DIKU, University of Copenhagen.
	3	G. Cousineau , P.-L. Curien, The categorical abstract machine, Science of Computer Programming, v.8 n.2, p.173-202, April 1, 1987 [doi>10.1016/0167-6423(87)90020-7 ]
	4	John Hannan, Making abstract machines less abstract, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.618-635, June 1991, Cambridge, Massachusetts, United States
	5	John Hannan, Staging transformations for abstract machines, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.130-141, June 17-19, 1991, New Haven, Connecticut, United States
	6	HANNAN, J. AND MILLER, D. 1992. From operational semantics to abstract machines. Math. Struct. Comput. Sci. 2, 4, 415-459.
	7	HANNAN, J. AND PFENNING, F. 1992. Compiler verification in LF. In Proceedings of the 7th Annual IEEE Symposium on Logic ~n Computer Science, A. Scedrov, Ed. IEEE Computer Society Press, Los Alamitos, Calif., 407-418.
	8	Robert Harper , Furio Honsell , Gordon Plotkin, A framework for defining logics, Journal of the ACM (JACM), v.40 n.1, p.143-184, Jan. 1993 [doi>10.1145/138027.138060]
	9	JONES, N.D. 1987. Challenging problems in partial evaluation and mixed computation. In Partial Evaluation and Mixed Computation, D. Bjorner, A. P. Ershov, and N. D. Jones, Eds. North-Holland, Amsterdam, 1-14.
	10	Neil D. Jones, Semantics-Directed Compiler Generation: Proceedings, Springer-Verlag New York, Inc., Secaucus, NJ, 1980
	11	JONES, N., SESTOFT, P., AND SCNDERGAARD, H. 1989. MIX: A self-applicable partial evaluator for experiments in compiler generation. J. LISP Symbol. Comput. 2, 1, 9-50.
	12	Ulrik Jørring , William L. Scherlis, Compilers and staging transformations, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.86-96, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512652]
	13	G. Kahn, Natural semantics, 4th Annual Symposium on Theoretical Aspects of Computer Sciences on STACS 87, p.22-39, February 1987, Passau, Germany
	14	R. Kelsey , P. Hudak, Realistic compilation by program transformation (detailed summary), Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.281-292, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75302]
	15	P. Kursawe, How to invent a prolog machine, New Generation Computing, v.5 n.1, p.97-114, April 1987
	16	LANDIN, P.J. 1964. The mechanical evaluation of expressions. Comput. J. 6, 5, 308-320.
	17	Peter Lee, Realistic compiler generation, MIT Press, Cambridge, MA, 1989
	18	Hanne Riis Nielson , Flemming Nielson, Semantics with applications: a formal introduction, John Wiley & Sons, Inc., New York, NY, 1992
	19	NILSSON, U. 1993. Towards a methodology for the design of abstract machines for logic programming languages. J. Logic Program. 16, 1, 2 (May), 163-189.
	20	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]
	21	PLOTKIN, G. 1981. A structural approach to operational semantics. DAIMI FN-19, Aarhus Univ., Aarhus, Denmark.
	22	Ascander Suarez, Compiling ML into CAM, Logical foundations of functional programming, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	23	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]
	24	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]