Staging transformations for abstract machines

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


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 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 architecture 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 Abstract Machine.

Original languageEnglish (US)
Pages (from-to)130-141
Number of pages12
JournalACM SIGPLAN Notices
Issue number9
StatePublished - Jan 5 1991

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Staging transformations for abstract machines'. Together they form a unique fingerprint.

Cite this