Staging transformations for abstract machines

We present a complete set of staging transformations for translating a class of interpreters into compilers and ex-ecutors. 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 pro-gram p and constructs a pair of programs pl, pz such that P(Z, Y) = P2(P1 (~), v) for all $, 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 pI and P2 corresponding to a compiler and an executor. The pass separation process includes the an tomatic definition of a semantics-directed machine archi-tecture that serves aa 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 A-calculus into a compiler and executor for a variant of the Categorical Ab-stract Machine.