ML Partial Evaluation using Set-Based Analysis

We describe the design and implementation of an off-line partial evaluator for Standard ML programs. Our partial evaluator consists of two phases: analysis and specialization. Analysis: Set-based analysis is used to compute control flow, data flow and binding-time information. It provides a combination of speed and accuracy that is well suited to partial-evaluation applications: the analysis proceeds at a few hundred lines per second and is able to deal with higher-order functions, partiallystatic values, arithmetic, side effects and control effects. Specialization: To treat the rich static information supplied by set-based analysis, continuation-based specialization is used in conjunction with a notion of "lightweight" symbolic values. The specializer adapts and improves upon the proven design principles of offline polyvariant partial evaluators. Our system is integrated into the New Jersey compiler for Standard ML: both input and output languages are the compiler's intermediate la..