Staging transformations for abstract machines

We present a complete set of staging transformations for translating a class of interpreters into compilers and executors. Staging transformation is the general process of separating stages or phases of a computation based on the availability of data. While encompassing partial evaluation, staging techniques can be more general, allowing for more powerful and flexible transformation strategies. We employ a particular strategy called pass separation 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. We apply this method in a restricted setting in which interpreters are described by abstract machines. For an interpreter p the pass separation constructs programs p1 and p2 corresponding to a compiler and an executor. The pass separation process includes the automatic definition of a semantics-directed machine architecture that serves as the target code for the compiler. This architecture resembles abstract machine code generated by hand-crafted compilers. Though our method is restricted to a limited class of abstract machines given as term rewriting systems, we argue that this class encompasses a large set of machines derived from operational semantics. We provide an example of our method by transforming an SECD-like machine for call-by-value evaluation of the λ-calculus into a compiler and executor for a variant of the Categorical Abstract Machine.