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
together with partial data
s are transformed into an often
faster specialized version
pgm-s by precomputing parts
pgm that depend only on
- Computer graphics by ray tracing
a ray tracer efficiently
written in C ran 1.5 to 3 times faster after specialization to the
scene to be drawn --- significant because high resolution ray tracing
can take hours of computer time, while building
pgm-s for a known scene
s and compiling it takes
seconds or minutes.
- Fast Fourier transform
:a Fortran FFT program was specialized
with respect to a fixed function and number of points. On examples the
result ran between 1.5 and 4 times faster than the original.
- Circuit and planetary simulations: using
parallel execution of
pgm-s, extremely high speedups of
Scheme programs were obtained. Partial evaluation
yields large basic blocks which parallelize well.
Compiling and compiler generation
interpreters for programming languages: the best-studied applications
of partial evaluation. Well-documented good results for various
Which problems can be solved faster using specialization?
Specialization is worthwhile when
pgm runs long,
pgm-s is significantly faster than
Suitable problem types include:
- Highly parameterised computations that use much time consulting
parameters, but are often run using the same parameter settings.
Programs with many similar subcomputations.
Programs of a highly interpretive nature, e.g.
circuit and other simulators, where specialization removes the time
to scan the object being simulated.
Database query search algorithms.
- Metaprogramming, where
a problem is solved by designing a user-oriented language and an
interpreter for it.
What is the state of the art?
Partial Evaluation and Automatic Program Generation
Neil D Jones, Carsten K Gomard, Peter Sestoft.
Prentice Hall International, UK, June, 1993.
O Danvy, R Glück, P Thiemann.
Lecture Notes in Computer Science vol. 1110. Springer-Verlag, Heidelberg, 1996.
A summary of the contents of these proceedings can be found as a
dvi file or as
Partial Evaluation - Practice and Theory
T Mogensen, P Thiemann.
Lecture Notes in Computer Science vol. ????. Springer-Verlag, Heidelberg, 1998.
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).
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
- Scheme: two systems,
Similix at Copenhagen and
Schism at Rennes;
- C: two systems,
C-mix at Copenhagen and the
TEMPO system at Rennes;
- SML: SML-mix, a
prototype at Copenhagen;
- Fortran 77: a prototype developed at Vienna and Copenhagen;
- Logic programming: systems developed by SICS (Swedish Institute of
Computer Science), K.U. Leuven (Belgium) and University of Bristol.
How automatic is partial evaluation?
The following steps are all automatic:
- First, a binding-time analysis to see which
pgm can potentially
be executed using only some of its runtime input (so-called static
- Once a value
s for the static data has explicitly been given,
pgm is transformed by precomputing
parts depending only on
s into the
pgm-s (which can then be compiled).
- 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
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
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.