ML Partial Evaluation Using Set-Based Analysis

摘要

We describe the design and implementation of an off-line partial evaluator forStandard 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, partially-static 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 off-line 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 language LAMBDA. As such, our ML partial evaluator is not a source-ML to source-ML program transformer and issues of desugaring and type checking are avoided. The core part of our implementation, handling higher-order programs with partially-static values, is complete. We are currently working on extensions of the specializer to treat computational effects.