Efficient multi-level generating extensions for program specialization

Multiple program specialization can stage a computation into several computation phases. This paper presents an effective solution for multiple program specialization by generalizing conventional off-line partial evaluation and integrating the “cogen approach” with a multi-level binding-time analysis. This novel “multi-cogen approach” solves two fundamental problems of self-applicable partial evaluation: the generation-time problem and the generator-size problem. The multilevel program generator has been implemented for a higher-order subset of Scheme. Experimental results show a remarkable reduction of generation time and generator size compared to previous attempts of multiple self-application.