REALISTIC COMPILATION BY PARTIAL EVALUATION

Two key steps in the compilation of strict functional languages are th e conversion of higher-order functions to data structures (closures) a nd 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 s imply by modifying the underlying interpreter. Purely first-order meth ods suffice to achieve the transformations. Our approach is an instanc e of semantics-directed compiler generation.