ML Partial Evaluation Using Set-Based Analysis
Abstract
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, 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1994
- Accession Number
- ADA278955
Entities
People
- Karoline Malmkjaer
- Nevin Heintze
- Oliver Danvy
Organizations
- Carnegie Mellon University