Realistic Compilation by Partial Evaluation
Two key steps in the compilation of strict functional languages are
the conversion of higher-order functions to data structures
(closures) and the transformation to tail-recursive style. We
show how to perform both steps at once by applying first-order offline
partial evaluation to a suitable interpreter. The resulting code is
easy to transliterate to low-level C or native code. We have
implemented the compilation to C; it yields a performance comparable
to that of other modern Scheme-to-C compilers. In addition, we have
integrated various optimizations such as constant propagation,
higher-order removal, and arity raising simply by modifying the
underlying interpreter. Purely first-order methods suffice to achieve
the transformations. Our approach is an instance of
semantics-directed compiler generation.