OPERATIONAL SEMANTICS-DIRECTED COMPILERS AND MACHINE ARCHITECTURES

We consider the task of automatically constructing intermediate-level machine architectures and compilers generating code for these architec tures, given operational semantics for source languages. We use operat ional semantics in the form of abstract machines given by rewrite syst ems 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 transf ormation, 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 p rograms, p1 and p2 corresponding to a compiler and an executor. The co mpiler translates the source language into an intermediate-level targe t language, and the executor provides the definition for this language . Our use of pass separation supports the automatic definition of targ et languages or architectures, and the structure of these architecture s is directed by the structure of the given source semantics. These ar chitectures resemble abstract machine languages found in hand-crafted compilers. Our method is restricted to a limited class of abstract mac hines given as term-rewriting systems, but we argue that this class en compasses a large set of language definitions derived from more natura l operational semantics. We provide two examples of our method by cons tructing compilers and target architectures for a simple functional la nguage and a simple imperative language. Though we construct these arc hitectures automatically, they bear a striking resemblance to existing architectures constructed by hand.