Semantics-Based Compiling: A Case Study in Type-Directed Partial Evaluation

We illustrate a simple and effective solution to semantics-based compiling. Our solution is based on type-directed partial evaluation, where ffl our compiler generator is expressed in a few lines, and is efficient; ffl its input is a well-typed, purely functional definitional interpreter in the manner of denotational semantics; ffl the output of the generated compiler is three-address code, in the fashion and efficiency of the Dragon Book; ffl the generated compiler processes several hundred lines of source code per second. The source language considered in this case study is imperative, blockstructured, higher-order, call-by-value, allows subtyping, and obeys stack discipline. It is bigger than what is usually reported in the literature on semantics-based compiling and partial evaluation. Our compiling technique uses the first Futamura projection, i.e., we compile programs by specializing a definitional interpreter with respect to this program. Our definitional interp..