Program Specialization and Partial Evaluation

Program specialization, also known as partial evaluation, is an automatic tool for program optimization, similar in concept to but in several ways stronger than a highly optimizing compiler. It is a source-to-source staging transformation: program pgm together with partial data s are transformed into an often faster specialized version pgm-s by precomputing parts of pgm that depend only on s.

Some successes

Which problems can be solved faster using specialization?

Specialization is worthwhile when pgm runs long, and pgm-s is significantly faster than pgm. Suitable problem types include:

What is the state of the art?


European and US conferences (with proceedings):

PEMC 1987 (Partial Evaluation and Mixed Computation, North-Holland 1988), and

ACM-SIGPLAN PEPM 1991, 92, 93, 94, 95, 97 (Partial Evaluation and Semantics-based Program Manipulation, ACM Press except 1992 and 1994).

Research projects:

Danish Research Council DART, Esprit Semantique I, II, Atlantique.

Partial evaluators exist for:

All are academic projects, with promising results so far. The Scheme systems are the most mature. The C and Fortran 77 systems are most promising for industrial use. However both need more development and experimentation to bring them up to industrial strength

How automatic is partial evaluation?

The following steps are all automatic:

  1. First, a binding-time analysis to see which parts of pgm can potentially be executed using only some of its runtime input (so-called static data).

  2. Once a value s for the static data has explicitly been given, pgm is transformed by precomputing parts depending only on s into the specialized version pgm-s (which can then be compiled).

  3. The effect of running pgm on full input data is identical to that of running pgm-s on the dynamic input data part, i.e. the remaining input part not given by s.

The specialized pgm-s can be much faster than pgm (speedups exceeding 10 have been seen in practice).

Although binding-time analysis is fully automatic, pgm may need `tuning,' i.e. modification by hand, to get best binding-time separation and so maximal speedup. The speedup can be either measured, or predicted from the binding-time information.

After binding-time analysis, specialization can be done automatically and completely without human intervention as often as wished, e.g. every time the static data changes. A well-known example: compiling by specializing an interpreter.