Efficient Implementations of Software Architectures via Partial Evaluation.
The notion of flexibility (that is, the ability to adapt to changing requirements or execution contexts) is recognized as a key concern in structuring software, and many architectures have been designed to that effect. However, the corresponding implementations often come with performance and code size overheads. The source of inefficiency can be identified to be in the loose integration of components, because flexibility is often present not only at the design level but also in the implementation. To solve this flexibility vs. efficiency dilemma, we advocate the use of partial evaluation, which is an automated technique to produce efficient, specialized instances of generic programs. As supporting case studies, we consider several flexible mechanisms commonly found in software architectures: selective broadcast, pattern matching, interpreters, software layers, and generic libraries. Using Tempo, our specializer for C, we show how partial evaluation can safely optimize implementations of those mechanisms. Because this optimization is automatic, it preserves the original genericity and extensibility of the implementation.
Introduction
What is partial evaluation?
Partial evaluation is a technique to partially execute a program, when only some
of its input data are available. Consider a program p requiring two inputs, x 1
and x 2 . When specific values d 1 and d 2 are given for the two inputs, we can
run the program, producing a result. When only one input value d 1 is given,
we cannot run p, but can partially evaluate it, producing a version p d1 of p
specialized for the case where x Partial evaluation is an instance of
program specialization, and the specialized version p d1 of p is called a residual
program.
For an example, consider the following C function power(n, x), which computes
x raised to the n'th power.
int n,x;
f int p;
while (n ?
if (n % 2 ==
else
Given values 7, we can compute power(5,7), obtaining the result
exploits that x even integers n).
Suppose we need to compute power(n, x) for a great many
different values of x. Then we can partially evaluate the function for
obtaining the following residual function:
int x;
f int p;
We can compute power 5(7) to obtain the result 7 In fact, for
any input x, computing power 5(x) will produce the same result as computing
Department of Computer Science, University of Copenhagen, Universitetsparken
2 Department of Mathematics and Physics, Royal Veterinary and Agricultural University,
Thorvaldsensvej 40, DK-1871 Frederiksberg C, Denmark
power(5,x). Since the value of variable n is available for partial evaluation, we
say that n is static; conversely, the variable x is dynamic because its value is
unavailable.
This example shows the strengths of partial evaluation: in the residual program
power 5, all tests and all arithmetic operations involving n have been
eliminated. The flow of control (that is, the conditions in the while and if
statements) in the original program was completely determined by the static
variable n.
Now suppose we needed to compute power(n,7) for many different values
of n. This is the opposite problem of the above: now n is dynamic (unknown)
and x is static (known). There is little we can do in this case, since the flow of
control is determined by the dynamic variable n. One could imagine creating a
table of precomputed values of 7 n for some values of n, but how are we to know
which values are relevant?
In many cases some of the control flow is determined by static variables, and
in these cases substantial speed-ups can be achieved by partial evaluation.
1.1 Notation
We can consider a program in two ways: as a function transforming inputs to
outputs, and also as a data object, being input to or output from other programs.
We need to distinguish the function computed by a program from the program
text itself.
Writing p for the program text, we write for the function computed by
or when we want to make explicit the language L in which p is written.
Consequently, denotes the result of running program p with input d on
an L-machine.
Now we can assert that power 5 is a correct residual program (in C) for
power and given input 5:
1.2 Interpreters and compilers
An interpreter Sint for language S, written in language L, satisfies for any S-
program s and input data d:
That is, running s with input d on an S-machine gives the same result as using the
interpreter Sint to run s on an L-machine. This includes possible nontermination
of both sides.
A compiler STcomp for source language S, generating code in target language
T , and written in language L, satisfies
That is, p can be compiled to a target program p 0 such that running p 0 on a
T-machine with input d gives the same result as running p with input d on
an S-machine. Though the equation doesn't specify this, we normally assume
compilation to always produce a target program.
Partial evaluators
2.1 What is a partial evaluator?
A partial evaluator is a program which performs partial evaluation. That is, it
can produce a residual program by specializing a given program with respect to
part of its input.
Let p be an L-program requiring two inputs x 1 and x 2 as above. A residual
program for p with respect to x is a program p d1 such that for all values
d 2 of the remaining input,
A partial evaluator is a program peval which, given a program p and a part d 1
of its input, produces a residual program p d1 . In other words, a partial evaluator
peval must satisfy:
peval
This is the so-called partial evaluation equation, which reads as follows: If partial
evaluation of p with respect to d 1 produces a residual program p d1 , then running
d1 with input d 2 gives the same result as running program p with input [d 1
As for compilers, the equation does not guarantee termination of the left-hand
side of the implication. In contrast to compilers we will, however, not always
assume partial evaluation to succeed. While it is desirable for partial evaluation
to always terminate, this is not guaranteed by a large number of existing partial
evaluators. See sections 2.2 and 5.5 for more about the termination issue.
Above we have not specified the language L in which the partial evaluator is
written, the language S of the source programs it accepts, or the language T of
the residual programs it produces. These languages may be all different, but for
notational simplicity we assume they are the same, . Note that
opens the possibility of applying the partial evaluator to itself (see below).
For an instance of the partial evaluation equation, consider
5, then from must follow that power(5,7)
2.2 What is achieved by partial evaluation?
The definition of a partial evaluator does not stipulate that the specialized program
must be any better than the original program. Indeed, it is easy to write a
program peval which satisfies the partial evaluation equation in a trivial way, by
prepending a new 'specialized' function power 5 to the original program. The
new function simply calls the original one with the given argument:
int n,x;
f int p;
while (n ?
if (n % 2 ==
else
int x;
f return(power(5, x)); g
While this program is a correct residual program, it is no faster than the original
program, and quite possibly slower. Even so, the construction above can be used
to prove existence of partial evaluators, a proof similar to Kleene's (1952) proof
of the s-m-n theorem [63], a theorem that essentially stipulates the existence of
partial evaluators in recursive function theory.
But, as the example in the introduction demonstrated, it is sometimes possible
to obtain residual programs that are arguably faster than the original pro-
gram. The amount of improvement depends both on the partial evaluator and
the program being specialized. Some programs do not lend themselves to spe-
cialization, as no computation can be done before all input is known. Sometimes
choosing a different algorithm may help, but in other cases the problem itself is
ill-suited for specialization. An example is specializing the power function to a
known value of x, as discussed in the introduction.
Looking at the definition of power, one would think that specialization with
respect to a value of x would give a good result: the assignments,
do not involve n, and as such can be executed
during specialization. The loop is, however, controlled by n. Since the termination
condition is not known, we cannot fully eliminate the loop. But x and p
will have different values in different iterations of the loop, so we cannot replace
them by constants. Hence, we find that we cannot perform the computations on
x and p anyway. We could force unfolding of the loop to keep the values of x
and p known, but since there is no bound on the number of different values x
and p can obtain, no finite amount of unfolding can eliminate x and p from the
program.
This conflict between termination of specialization and quality of residual
program is common. The partial evaluator must try to find a balance that
ensures termination often enough to be interesting (preferably always) while
yielding sufficient speed-up to be worthwhile. Due to the undecidability of the
halting problem, no perfect strategy exists, so a suitable compromise must be
found. See Section 5.5 for more on this subject.
3 Another approach to program specialization
A generating extension of a two-input program p is a program p gen which, given
a value d 1 for the first input of p, produces a residual program p d1 for p with
respect to d 1 . In other words,
The generating extension takes a given value d 1 of the first input parameter x 1
and constructs a version of p specialized for x
As an example, we show below a generating extension of the power program
from the introduction:
int n;
f
printf("int x;"n");
printf("f int p;"n");
while (n ?
if (n % 2 ==
else f printf("
printf(" return(p);"n");
Note that power-gen closely resembles power: those parts of power that depend
only on the static input n are copied directly into power-gen, and the parts that
also depend on x are made into strings, which are printed as part of the residual
program. Running power-gen with input yields the following residual
program:
int x;
f int p;
This is almost the same as the one shown in the introduction. The difference is
because we have now made an a priori distinction between static variables (n)
and dynamic variables (x, p). Since p is dynamic, all assignments to it are made
part of the residual program, even was executed at specialization
time in the example shown in the introduction.
Later we shall see that a generating extension can be constructed by applying
a sufficiently powerful partial evaluator to itself. One can even construct a
generator of generating extensions that way.
4 Partial evaluation, interpreters, and compila-
tion
4.1 Compilation using a partial evaluator
In Section 1.2 we defined an interpreter as a program taking two inputs: a
program to be interpreted and input to that program:
We often expect to run the same program repeatedly on different inputs. Hence,
it is natural to partially evaluate the interpreter with respect to a fixed, known
program and unknown input to that program. Using the partial evaluation
equation we get
[s; d] for all d
Using the definition of the interpreter we get
The residual program is thus equivalent to the source program. The difference
is the language in which the residual program is written. If the input and output
languages of the partial evaluator are identical, then the residual program is
written in the same language L as the interpreter Sint. Hence we have compiled
s from S, the language that the interpreter interprets, to L, the language in
which it is written.
4.2 Compiler generation using a self-applicable partial eval-
uator
We have seen that we can compile programs by partially evaluating an in-
terpreter. Typically we will want to compile many different programs, which
amounts to partially evaluating the same interpreter repeatedly with respect to
different programs. This situation calls for optimization by yet another application
of partial evaluation. Hence we use a partial evaluator to specialize a partial
evaluator peval with respect to a program Sint, but without the argument s of
Sint. Using the partial evaluation equation we get:
peval ]][peval;
peval Sint
Using the results from above, we get
peval Sint
for which we have
d for all d
We recall the definition of a compiler from Section 1.2:
We see that peval Sint
fulfills the requirements for being a compiler from S to T .
In the case where the input and output languages of the partial evaluator are
identical, the language in which the compiler is written and the target language
of the compiler are both the same as the language L in which the interpreter
is written. Note that we have no guarantee that partial evaluation terminates,
neither when producing the compiler nor when using it. Experience has shown
that while this may be a problem, it is often the case that if compilation terminates
for a few general programs then it terminates for all.
Note that the compiler peval Sint is a generating extension of the interpreter
Sint , according to the definition shown in section 3. This generalizes to any
program, not just interpreters: partially evaluating a partial evaluator peval
with respect to a program p yields a generating extension p
program.
4.3 Compiler generator generation
Having seen that it is interesting to partially evaluate a partial evaluator, we
may want to do this repeatedly: to partially evaluate a partial evaluator with
respect to a range of different programs (e.g., interpreters). Again, we may
exploit partial evaluation:
peval peval
Since which is a generating extension of p, we can see
that peval peval is a generator of generating extensions. The program peval peval
is itself a generating extension of the partial evaluator: peval peval peval .
In the case where p is an interpreter, the generating extension p gen is a compiler.
Hence, peval gen is a compiler generator, capable of producing a compiler from
an interpreter.
4.4

Summary

: The Futamura projections
Instances of the partial evaluation equation applied to interpreters, directly
or through self-application of a partial evaluator, are collectively called the
Futamura projections. The three Futamura projections are:
The first Futamura projection: compilation
peval
The second Futamura projection: compiler generation
peval ]][peval;
The third Futamura projection: compiler generator generation
The first and second equations were devised by Futamura in 1971 [40], and the
latter independently by Beckman et al. [12] and Turchin et al. [94] around 1975.
5 Techniques for partial evaluation
5.1 Polyvariant specialization
Polyvariant specialization is a technique for partial evaluation which works for
a range of languages. A program is thought of as a collection of program points ,
connected by control-flow edges . In a flow-chart language, program points and
control-flow edges are, respectively, labelled basic blocks and jumps ; in a functional
language, they are defined functions and function calls ; in a logic language,
they are predicates and predicate applications (atoms).
Polyvariant specialization constructs a residual program by creating zero
or more specialized variants of each program point, and connecting them by
residual control-flow edges.
5.1.1 The exponentiation example revisited
To illustrate polyvariant specialization, consider the power function from Section
1 in flowchart form, with explicitly labelled basic blocks:
lab1: if (n !=
if (n % 2 !=
goto lab1
goto lab1
lab3: return(p)
A program on this form is specialized to given values of the static variables by
specializing the basic blocks. For each basic block, and for each set of static
variable values with which it may be executed, one creates a specialized basic
block in the residual program. This is polyvariant specialization [24, 57].
For instance, the basic block labelled lab1 may be executed with static
Hence one creates a specialized basic block, whose label lab1 fn=5;p=1g
consists of the original label and bindings for the static variables. The body of
the specialized basic block consists of the specialized residual commands from
the original basic block. Naturally, the specialized version of a jump goto lab
is itself a jump goto lab f:::g
to a specialized (decorated) version of lab.
To see how this works, let us specialize the above program with the known
value and an unknown value for x. First we get to lab1 with
Using this information to specialize that basic block, we perform the conditional
ifs statically, find that (n != 0) is false and (n % 2 != 0) is true, and so must
jump to lab2, still with We create a residual goto command, and
a new specialized label lab2 fn=5;p=1g
goto lab2 fn=5;p=1g
The corresponding specialized basic block is the block at lab2 specialized with
respect to 1. The assignment specializes to the residual
since x is dynamic. This means that p is no longer static.
The assignment can be executed because n is static. The new static
environment has 4. Hence the goto lab1 specializes to goto lab1 fn=4g
and we get:
goto lab1 fn=4g
Note that we had to generate a constant expression 1 to represent the static
value 1 of p in the residual program. We say that the static value of p has been
lifted to appear in the residual program.
Next we must specialize the basic block at lab1 with respect to 4, and so
on. This process continues until specialized basic blocks have been created for
all specialized labels occurring in the residual program. In total, the following
residual program is obtained:
goto lab2 fn=5;p=1g
goto lab1 fn=4g
goto lab1 fn=2g
goto lab1 fn=1g
goto lab2 fn=1g
goto lab1 fn=0g
goto lab3 fn=0g
return(p)
This can be simplified by replacing jumps (gotos) with the code they jump to;
this is called transition compression or unfolding . The result is almost as in
Section 1:
return(p)
The technique of polyvariant specialization turns out to work for other languages
too; this is demonstrated in later sections for functional languages and logic
languages.
The specialization process builds a graph whose nodes are specialized program
points (labels), and whose edges are residual control-flow edges (jumps).
This may be done by maintaining a set pending of the specialized program
points still to be created, and a mapping out from specialized program points
to specialized program code fragments (basic blocks). One repeatedly chooses
and removes a program point pp from pending, constructs the corresponding
specialized program code fragment code pp , and extends the mapping out with
[pp 7! code pp ]. Moreover, one extends the set pending by any new specialized
labels reachable from code pp . More precisely, pending is extended with the set
is the set of program points
pp 0 to which there is a jump goto pp 0 from code pp .
To begin with, pending contains just the program's entry point together
with the initial values of its static variables, and out is empty. The procedure
terminates if and when pending becomes empty, in which case out contains the
residual program. This process may fail to terminate, as discussed in Section 5.5
below.
5.2 Online versus offline partial evaluation
There are two types of partial evaluators. An online partial evaluator is a kind
of generalized interpreter, which needs no a priori division of variables into
static and dynamic. During partial evaluation, the environment maps static
variables to concrete values, and dynamic variables to symbolic expressions.
When processing an expression e, the partial evaluator makes an online decision
whether to evaluate it (giving a concrete value), or to residualize it (giving a
residual expression), based on the current bindings of the variables appearing
in e.
An offline partial evaluator, by constrast, works in two phases. The first
phase is a binding-time analysis , which classifies the program's variables into
(definitely) static and (possibly) dynamic, and similarly classifies all operations.
The second phase is the specialization proper. This phase simply uses the
static/dynamic classification of variables and operations when processing an ex-
pression; all evaluate/residualize decisions have been made offline. It never uses
the actual value of a variable or expression, unless the binding-time analysis
guarantees that it is static and hence indeed is a concrete value.
Since offline partial evaluators rely on a program analysis, they are usually
more conservative than online partial evaluators, missing some opportunities for
specialization. On the other hand, offline specializers have a simpler structure,
and may exploit the global knowledge about the program gained by the binding-time
analysis. Experience shows that it is harder to construct self-applicable
online specializers than offline ones.
Hybrids of online and offline specializers have been constructed. For instance,
one may use a three-valued binding-time analysis, which classifies variables and
expressions as 'definitely static', `definitely dynamic', or 'undecided' [92]. The
specialization phase will just obey the static and dynamic annotations, but use
the actual (specialization time) value of variables to decide whether to evaluate
or residualize.
A generator of generating extensions is similar to an offline partial evaluator,
since a generating extension embodies an a priori distinction between early
(static) inputs and late (dynamic) inputs. A generator of generating extension
usually includes a binding-time analysis.
Online partial evaluation has been studied for Scheme by Ruf and Weise
[82, 100] and by many researchers in the logic programming community.
5.3 Binding-time analysis
The classification of variables into static and dynamic is called a division. The
division must be congruent : if the value of some dynamic expression e may be
assigned to a variable y, then y must be made dynamic. The expression e is
static if it contains no dynamic variables.
Considering again the flow-chart version of the power function in Section 5.1,
we see that if n is static and x is dynamic from the outset, then p must be
classified as dynamic because p   x is assigned to p, whereas n remains static: n
is never assigned a dynamic value.
A simple binding time analysis may be performed by means of an abstract
interpretation in which each variable and expression takes one of the abstract
values S (for static) or D (for dynamic). One builds an initial division in which
all variables are S, except for the dynamic input parameters. Now all assignments
in the program are abstractly executed, possibly reclassifying variables as
dynamic to satisfy the congruence requirement, until no more variables need to
be reclassified as dynamic.
Alternatively, binding-time analysis may be done by type inference with sub-
types, where S is considered a subtype of D, meaning that S may be coerced
to D (corresponding to the lifting of a static value). This kind of binding-time
analysis may be implemented efficiently by constraint solving [53].
When composite data structures (tuples, records, lists) are considered, a data
structure may be partially static. For instance, the value of a variable may be a
whose first component is static, and whose second component is dynamic.
This may be described by the binding-time S \Theta D. Similarly, a list of such
pairs may be described by the binding-time (S \Theta D) list. The type inference
approach to binding-time analysis is especially useful for handling partially static
data structures in strongly typed languages, such as Standard ML, Pascal, or C.
Latently typed languages, such as Scheme, are handled essentially by considering
dynamic expressions to be untyped.
When a division has been computed by the binding-time analysis, one must
decide for each operation in the program whether it must be evaluated or re-
sidualized (producing residual code) during partial evaluation. An arithmetic
operation must be residualized unless all its operands are static. An if statement
must be residualized unless the condition is static. We shall assume that
an assignment will be residualized unless the assigned variable is static. We also
assume that all gotos are residualized (any excess gotos may be removed by
subsequent transition compression).
To visualize the classification of operations, we annotate the dynamic operations
by underlining. For the power function, the annotation would be:
lab1: if (n !=
if (n % 2 !=
goto lab1
goto lab1
lab3: return(p)
Doing polyvariant specialization of this program with blindly following
the annotations, we obtain (after transition compression):
return(p)
which is just the result obtained by the generating extension in Section 3. This
is because the generator of generating extensions presuppose the a priori distinction
between the static (n) and dynamic (x; p) variables.
5.4 Residual programs containing loops
The residual program generated above contains no loops; all conditionals were
statically decidable and all transitions could be compressed. However, the machinery
in Section 5.1 suffices for creating residual programs containing loops.
Consider the following contrived example:
while (n ?
else
Written as a flow-chart, the program is
lab1: if (n !=
goto lab3
lab2:
goto lab3
lab3:
goto lab1
lab4: return(sum)
Let us specialize it with respect to static dynamic sum and n. Specializing
the basic block at lab1 with respect to must create a residual
version of the first conditional, because n is dynamic, whereas the second conditional
can be reduced, because k is static and non-zero, giving a residual jump
to lab2 fk=3g
if (n !=
goto lab2 fk=3g
Next we specialize the code at label lab2 with respect to
goto lab3 fk=3g
Continuing in this manner, we obtain this residual program:
if (n !=
goto lab2 fk=3g
goto lab3 fk=3g
goto lab1 fk=3g
return(sum)
After transition compression, we get:
if (n !=
goto lab1 fk=3g
return(sum)
The decorated labels lab1 fk=3g
and lab4 fk=3g
may be replaced by simple ones,
such as lab1r and lab4r. Then we see that partial evaluation has eliminated the
tests on k inside the loop; effectively, they were found to be loop-invariant. The
loop is recreated in the residual program simply because the jump at lab3 fk=3g
goes back to the specialized program point lab1 fk=3g
at the beginning of the
program.
5.5 Termination of partial evaluation
Transition compression should be applied with care in the program just shown.
An attempt to (repeatedly) unfold all remaining occurrences of goto lab1 fk=3g
would never terminate. Infinite looping due to transition compression is avoided
fairly easily; either by unfolding a jump to a (residual) label only if there is
exactly one way to reach that label [21], or by ascertaining that unfolding must
stop due to some descending chain condition [87].
Termination problems caused by infinite specialization are harder to deal
with. For illustration, consider again the power program in Section 5.1, but now
with static straightforward application of
polyvariant specialization will attempt to produce an infinite residual program:
if (n !=
if (n % 2 !=
goto lab1 fx=49;p=1g
goto lab1 fx=7;p=7g
if (n !=
if (n % 2 !=
goto lab1 fx=2401;p=1g
goto lab1 fx=49;p=49g
This program is incomplete, and it cannot be completed using a finite number
of program points, if we insist on keeping x and p static.
In an online partial evaluatior, one may recognize that the configuration
is 'similar' to the previously encountered
and that the two program points should therefore be merged into a single more
general one, e.g. by making x dynamic (which eventually forces p to be dynamic
also). This process is called generalization.
In an offline partial evaluator, one may recognize after binding-time analysis
that the tests are dynamic (not decided by the static variables), and that static
data are constructed under dynamic control. This is a sign of danger, indicating
that x and p should be made dynamic too, making specialization completely
trivial (but safe).
Holst developed a finiteness analysis and used it to ensure termination of
polyvariant specialization [54].
5.6 Generalized partial evaluation
One more lesson may be learnt from the (partially constructed) residual program
just shown. The basic block labelled lab3 fx=49;p=1g
is superfluous. Reaching it
would require the tests (n != 0) and (n % 2 != 0) to fail and the test ((n/2
!= to succeed, which is impossible for integral n; the former two imply that
2.
The superfluous basic block is created because the static environment (as
outlined above) takes into account only the values of static variables (x and p),
not the outcome of previously encountered dynamic tests (on n). Polyvariant
specialization may be enhanced to do so, giving generalized partial evaluation.
Then a theorem prover is required to decide static conditionals and to decide
whether two static environments are equivalent [41]. In certain data domains
and applications, less powerful methods may suffice [46].
6 Partial evaluation for other languages
6.1 Functional languages
6.1.1 First-order languages
Partial evaluation of a first-order functional language may be done by polyvariant
specialization as described in Section 5.1 above. The notions of label , basic block ,
and global variable must be replaced by the notions of function name, function
definition, and function parameter. Henceforth a specialized program point is a
specialized function name, and a residual program is a collection of specialized
function definitions.
For illustration, consider a functional version of the power program from
Section 1, here using Standard ML syntax:
else if n mod
else x * power(n-1, x)
Specializing the function power with respect to static dynamic x, we
obtain
fun power fn=5g
and power fn=4g
and power fn=2g
and power fn=1g
and power fn=0g
Note that a specialized function name power fn=5g
consists of an original function
name power together with a binding for the static parameters, here just n.
The residual program may be simplified by unfolding trivial function calls (and
reducing the subexpression (x * x) * 1 arising from this unfolding):
fun power fn=5g
and power fn=2g
This residual program is equivalent to that generated for the C version of power
in Section 1.
Binding-time analysis may proceed as for a flow-chart language. For each
application (f e) where e may be dynamic, reclassify the formal parameter of f
to dynamic. Since the language is first-order, f must be a known function.
As for flow-chart languages, a partial evaluator may either be offline or online.
An offline partial evaluator will perform a binding-time analysis of the program,
to classify all parameters as either static or dynamic, before embarking on the
specialization phase proper. A complete description of a simple offline self-
applicable partial evaluator for a first-order functional language may be found
in [58, Chapter 5 and Appendix A].
6.1.2 Higher-order functional languages
Polyvariant specialization can be applied to higher-order functional languages
(in which functions may be passed around as values) as well. The main new
challenges are: how to represent static functional values during partial evalu-
ation, how to lift functional values from static to dynamic, how to specialize
with respect to functional values, and how to do binding-time analysis.
A functional value may be represented by a closure (g; vs) consisting of a
function name g together with the values vs of the static free variables in g's
body.
Lifting of a (partially) static functional value to a dynamic value is complicated
and is usually avoided in offline partial evaluators, by requiring that every
(partially) static functional value must be applied to an argument. Any functional
value occurring in a dynamic context will be reclassified as dynamic by
the binding-time analysis.
Specializing a function f with respect to a fully static functional closure
(g; vs) is simple; just specialize with respect to the function name g and the
values vs of the (static) free variables.
Specializing f with respect to a partially static (g; vs) is more involved, since
the body of g may have dynamic free variables. These variables may be free also
in the residual expression resulting from applying (g; vs). Hence the dynamic
must be lifted out of g's body at specialization time, and must be
passed as extra parameters to the residual function f (g;vs) .
A higher-order functional program may contain applications
evaluates to some function. A closure analysis can provide an approximation to
the set of functions that e 1 may evaluate to; using this information, binding-time
analysis may proceed as for a first-order language [58, Chapter 15]. Alternatively,
the binding-time analysis may be based on type inference [53]; this is preferable
if one wants to permit partially static data structures also.
Self-applicable partial evaluators exist for realistic higher-order functional
languages such as Scheme [20, 21, 28, 29, 31] and Standard ML [70] as well as
for the call-by-value lambda calculus with some extensions [51], and for the pure
lambda calculus [74, 75]. For further information, see e.g. [58, Chapter 10]; for
full details, see the above-mentioned papers.
6.2 Logic programming languages (Prolog)
A distinguishing feature of Prolog and other logic programming languages is
the ability to run with incomplete input. While this seems similar to partial
evaluation, there are a number of differences:
ffl The result of running a Prolog program with incomplete input is a (pos-
sibly) infinite list of instantiations of both input and output variables.
Though this can be considered a list of facts, and hence a restricted form
of program, we generally want a partial evaluator to be able to produce
non-trivial residual programs, possibly containing loops.
ffl Prolog has some non-logical features that means that running a program
with incomplete input is not a generalization of running with complete
input. As an example, calling the predicate defined by
with partially instantiated input p(A,a) returns the result
running with complete input p(a,a) would fail.
Most of the research in partial evaluation (or partial deduction, as it is often
called) of logic languages has tended to avoid the second issue by working with
pure logic languages [43, 68]. Some systems, however, deal with non-logical
features of Prolog [76, 84].
Partial evaluation of logic languages is typically done using the same basic
techniques as for functional languages: call unfolding and polyvariant specializ-
ation, program points being predicates. A major source of speed-up in partially
evaluating logic programs is the ability to detect failing computations at specialization
time, and cut these away in the residual program. This way, not only
static computations but also dynamic computations in failing branches can be
eliminated by partial evaluation. This makes the potential speed-up by partial
evaluation greater in logic languages than in functional or imperative languages.
Online specialization has been the preferred technique in the logic language
community, usually combined with powerful techniques for avoiding non-termination
[23, 71]. In logic languages, online specialization presents more opportunities
for specialization than offline specialization, because unification will often
instantiate otherwise dynamic variables. When self-application has been a major
goal, offline specialization has been used also [52, 76].
An example of Prolog specialization is shown below. It specializes a program
for regular expression matching
accepts(R,[]) :- nullable(R).
accepts(R,[C-S]) :- first(R,C), next(R,C,R1), accepts(R1,S).
The program takes a regular expression and a string as arguments. If the string
is empty, the regular expression is tested for nullability (acceptance of empty
string). If the string starts with a character C, it is tested whether this is among
the first set of the regular expression. If this is the case, a new regular expression
for matching the rest of the string is produced by next. The predicates
nullable, first and next are not shown, but note that the set of Cs for which
first succeeds is determined by R. Hence, partial evaluation of first with respect
to a known R and unknown C will yield a number of instantiations of C.
Specializing the program above with respect to R being the regular expression
(ajb)   aba yields the following residual program:
accepts-3([]).
Since nullable depends only on static values, it is completely eliminated, only
visible as failed or true cases for the empty string. The call to first has
instantiated C with a or b. This instantiation has made it possible to fully
evaluate next, which has yielded a total of four different regular expressions,
each giving rise to a specialized version of accepts. For accepts-0, the regular
expression is (ajb)   aba, for accepts-1 it is (ajb)   abajba, for accepts-2 it is
(ajb)   abaja, and for accepts-3 it is (ajb)   abajbajffl.
6.3 A full imperative language (C)
We have seen that polyvariant specialization suffices for partial evaluation of
flow-chart languages, and hence for simple imperative languages. A realistic
imperative language, such as C, includes composite data structures (records and
indexed arrays), pointers and dynamic data structures, functions which may
have side effects on global variables, etc.
An offline partial evaluator for C needs a sophisticated binding-time analysis
to deal with pointers and composite data structures. For instance, a pointer
variable p may be dynamic, or the pointer may be static but point to a dynamic
object, or both the pointer and the pointed-to object may be static.
The binding-time analysis may require programs to be 'well-behaved'. Assume
that a is an array, and that the program contains an assignment of the form
e, where e is dynamic. Then in principle any variable in the program
may become dynamic as a result of this assignment, in case the address a[n] is
outside the allocated array a. This would be too conservative, making partial
evaluation trivial. Instead, one should require programs to be well-behaved, so
that any such address is indeed inside a.
For a taste of the difficulties caused by the combination of non-local side
effects and (recursive) functions, consider a function which has a side effect on
a static global variable, but where the side effect is controlled by some dynamic
expression dyn:
int global;
int
stmts
else
After the call to foo, the value of global may be either 1 or -1, but we cannot
know which one at partial evaluation time, because dyn is dynamic. The simplest
solution is to reclassify global as dynamic, but this wastes static information
which might be useful when partially evaluating stmts. Another solution is to
unfold the call to foo, giving a residual program of this form:
int global;
int
f if dyn f stmts fglobal=1g ; g
else f stmts fglobal=\Gamma1g ; g
Here stmts fglobal=1g
is a specialized version of stmts. However, when function
foo is recursive, such unfolding is impossible. A third solution is to introduce a
(dynamic) continuation variable cont, which will be assigned a different value
in each branch of the residual version foo' of foo. In function main, after the
call to foo', there will be a switch on cont:
int global;
int
switch (cont) f
case 1: stmts fglobal=1g ; break;
case 2: stmts fglobal=\Gamma1g ; break;
However, this will not work when foo is recursive, and the recursion is under
dynamic control, since the number of paths through foo will not be statically
bounded in that case. Hence for recursive procedures, the only feasible option
may be to reclassify global as dynamic.
These and many other problems were studied by Lars Ole Andersen, who
constructed two systems for specialization of C programs. The first one is a
self-applicable partial evaluator for a C subset, including procedures as well as
pointers and arrays [6, 8]. The second one is a generator of generating extensions
for all of ANSI C [9]; the latter system can be licensed from the University of
Copenhagen.
The techniques for C should carry over to e.g. Ada, Modula, or Pascal with
little modification, but to our knowledge this has not been done.
7 Partial evaluation in perspective
7.1 Program specialization without a partial evaluator
So far we have focused mainly on specialization using a partial evaluator. But
the ideas and methods presented here can be, and indeed have been, used without
using a partial evaluator.
Specialization by hand
It is quite common for programmers to hand-tune code for particular cases.
Often this amounts to doing partial evaluation by hand. As an example, here is
a quote from a paper [80] about the programming of a video-game:
How Nevryon manages to keep up its speed Basically there are
two ways to write a routine:
It can be one complex multi-purpose routine that does everything,
but not quickly. For example, a sprite routine that can handle any
size and flip the sprites horizontally and vertically in the same piece
of code.
Or you can have many simple routines each doing one thing. Using
the sprite routine example, a routine to plot the sprite one way,
another to plot it flipped vertically and so on.
The second method means more code is required but the speed advantage
is dramatic. Nevryon was written in this way and had about
separate sprite routines, each of which plotted sprites in slightly
different ways.
specialization is used. But it is doubtful that a general purpose partial
evaluator was used to do the specialization. Instead the specialization has been
performed by hand, possibly without ever explicitly writing down the general
purpose routine that forms the basis for the specialized routines.
Using hand-written generating extensions
We saw in Section 3 how a generating extension for the power function was
easily produced from the original code, using knowledge about which variables
contained values known at specialization time. While it is not always quite so
simple as in this example, it is often not particularly difficult to write generating
extensions of small to medium sized procedures or programs.
In situations where no partial evaluator is available, this is often a viable way
to obtain specialized programs. Using a generating extension instead of writing
the specialized versions by hand is useful when either a large number of variants
must be generated, or when it is not known in advance what values the program
will be specialized with respect to.
A common use of hand-written generating extensions is for run-time code
generation, where a piece of specialized code is generated and executed, all at
run-time. As in the sprite example above, one often generates specialized code
for each plot operation when large bitmaps are involved. The typical situation is
that a general purpose routine is used for plotting small bitmaps, but special code
is generated for large bitmaps. The specialized routines can exploit knowledge
about the alignment of the source bitmap and the destination area with respect
to word boundaries, as well as clipping of the source bitmap. Other aspects such
as scaling, differences in colour depth etc. have also been targets for run-time
specialization of bitmap-plotting code.
Hand-written generating extensions have been used for optimizing parsers by
specializing with respect to particular tables [78], and for converting interpreters
into compilers [77].
Handwritten generating extension generators
In recent years, it has become popular to write a generating extension generator
instead of a partial evaluator [9, 16, 55], but the approach itself is quite old [12].
A generating extension generator can be used instead of a traditional partial
evaluator as follows. To specialize a program p with respect to data d, first
produce a generating extension p gen , then apply p gen to d to produce a specialized
program p d .
Conversely, a self-applicable partial evaluator can produce a generating extension
generator (cf. the third Futamura projection), so the two approaches
seem equally powerful. So why write a generating extension generator instead
of a self-applicable partial evaluator? Some reasons are:
ffl The generating extension generator can be written in another (higher level)
language than the language it handles, whereas a self-applicable partial
evaluator must be able to handle its own text.
ffl For this reason, among others, it may be easier to write a generating
extension generator than a self-applicable partial evaluator.
ffl A partial evaluator must contain an interpreter, which may be problematic
for typed languages, as explained below. Neither the generating extension
generator, nor the generating extensions, need to contain an interpreter.
When writing an interpreter for a strongly typed language, one must use a single
type in the interpreter to represent an unbounded number of types used in the
programs that are interpreted. The same is true for a partial evaluator: a single
universal type must be used for the static input to the program that will be
specialized. Hence, the static input must be coded. This means that the partial
evaluation equation must be modified to take this coding into account:
peval
where overlining means that a value is coded, e.g. d 1 is the coding of the value
of d 1 .
When self-applying the partial evaluator, the static input is a program. The
program is normally represented in a special data type that represents program
text. This data type must now be coded in the universal type:
peval ]][peval;
This double encoding is space- and time-consuming, and has been reported to
make self-application intractable, unless special attention is paid to make the
encoding compact [67]. A generating extension produced by self-application
must also use the universal type to represent static input, even though this will
always be of the same type.
This observation leads to the idea of making generating extensions accept
uncoded static input. To achieve this, the generating extension generator simply
copies the type declarations of the original program into the generating extension.
The generating extension generator takes a single input: a program, and need
not deal with arbitrarily typed data. A generating extension handles values from
a single program, the types of which are known when the generating extension
is constructed. Hence, neither the generator of generating extensions, nor the
generating extensions themselves, need to handle arbitrarily typed values. The
equation for specialization using a generating extension generator is shown below.
Note the absence of coding.
We will usually expect generator generation to terminate, but, as for normal
partial evaluation, allow the construction of the residual program (performed by
gen ) to loop.
7.2 When is partial evaluation worthwhile?
In Section 2.2 we saw that we cannot always expect speed-up from partial eval-
uation. Sometimes no significant computations depend on the known input only,
so virtually all the work is postponed until the residual program is executed.
Even if computations appear to depend on the known input only, evaluating
these during specialization may require infinite unfolding (as seen in Section 2.2)
or just so much unfolding that the residual programs become intractably large.
On the other hand, the example in Section 1 manages to perform a significant
part of the computation at specialization time. Even so, partial evaluation will
only pay off if the residual program is executed often enough to amortize the
cost of specialization.
So, we must have two conditions before we can expect any benefit from
partial evaluation:
There are computations that depend only on static data.
These are executed repeatedly, either by repeated execution of the program
as a whole, or by repetition (looping or recursion) within a single execution
of the program.
The static (known) data can be obtained in several ways: it may be constants
appearing in the program text or it can be part of the input.
It is quite common that library functions are called with some constant para-
meters, such as format strings, so in some cases partial evaluation may speed
up programs even when no input is given. In such cases the partial evaluator
works as a kind of optimizer, often achieving speed-up when most optimizing
compilers would not. On the other hand, most partial evaluators may loop or
create an excessive amount of code while trying to optimize programs, and hence
are ill-suited as default optimizers.
Specialization with respect to partial input is the most common situation.
Here there are often more opportunities for speed-up than just exploiting constant
parameters. In some cases (e.g., when specializing interpreters) most of the
computation can be done during partial evaluation, sometimes yielding speed-ups
by an order of magnitude or more, similar to the speed difference between
interpreted and compiled programs. When you have a choice between running
a program interpreted or compiled, you will choose the former if the program
is only executed a few times and contains no significant repetition, whereas you
will want to compile it if it is run many times or involves much repetition. The
same principle carries over to specialization.
Partial evaluation often gets most of its benefit from replication: loops are
unrolled and the index variables exploited in constant folding, or functions are
specialized with respect to several different static parameters. In some cases this
replication can result in enormous residual programs, which may be undesirable
even if much computation is saved. In the example in Section 1 the amount
of unrolling and hence the size of the residual program is proportional to the
logarithm of n, the static input. This expansion is small enough that it doesn't
become a problem. If the expansion were linear in n, it would be acceptable for
small values of n. Specialization of interpreters typically yield residual programs
that are proportional to the size of the source program, which is reasonable. On
the other hand, quadratic or exponential expansion is hardly ever acceptable.
It may be hard to predict the amount of replication caused by a partial
evaluator. In fact, seemingly innocent changes to a program can dramatically
change the expansion done by partial evaluation, or even make the difference
between termination or nontermination of the specialization process. Similarly,
small changes can make a large difference in the amount of computation that is
performed during specialization and hence the speed-up obtained. This is similar
to the way parallelizing compilers are sensitive to the way programs are writ-
ten. Hence, specialization of off-the-shelf programs often require some (usually
minor) modification to get optimal benefit from partial evaluation. Ideally, the
programmer should write his program with partial evaluation in mind, avoiding
the structures that can cause problems, just like programs for parallel machines
are best written with the limitations of the compiler in mind.
7.3 Partial evaluation, optimizing compilers, and modern
machines
Many compilers perform transformations such as constant folding and inlining
(of small functions) to improve target programs. These transformations are
similar to some of those performed by a partial evaluator. However, in contrast
to a partial evaluator, a compiler rarely produces more than one specialized
version of a given piece of code (except possibly by inlining). This kind of
specialization is essential in partial evaluators, and must be handled correctly
also in the presence of loops and recursive procedures.
With the complex memory hierarchies of modern computer hardware it is
hard to know when a program modification actually achieves a speed-up. Exploiting
the memory hierarchy well (data registers and instruction pipeline, two
or more levels of cache, main memory, and virtual memory) is crucial for the
performance of modern machines. Hence it may be detrimental to unroll a loop
so that it does not fit in the cache, but beneficial to inline a procedure if this
replaces indirect jumps by linear code sequences. How much unrolling, inlining,
or replication to perform is machine dependent, and you often see optimizations
that improve performance on one machine but degrade it on others.
With the increasing degree of micro-parallelism in modern microprocessors,
one may even get no benefit from eliminating the static computations, as they
may not be part of the critical path and hence may be executed in parallel
with the dynamic computations. On the other hand, the elimination of variables
by specialization reduces register pressure, and unrolling of loops and inlining
of functions increase basic block size, giving more opportunities for low-level
optimization.
This means that it is hard to predict the amount of speed-up obtained by
partial evaluation. Examples exist where a residual program is twice as fast as
the original program on one machine is, and slower than the original on another
machine. The speed-up is also affected by the optimizations performed when
compiling the residual programs.
8 Applications of partial evaluation
We saw in Section 4 that partial evaluation can be used to compile programs
and to generate compilers. This has been one of the main practical uses of
partial evaluation. Not for making compilers for C or similar languages, but for
rapidly obtaining implementations of acceptable performance for experimental
or special-purpose languages. Since the output of the partial evaluator typically
is in a high-level language, a traditional compiler is used as a back-end for the
compiler generated by partial evaluation [1, 14, 25, 27, 30, 33, 61]. In some
cases, the compilation is from a language to itself. In this case the purpose is to
make certain computation strategies explicit (e.g., continuation passing style) or
to add extra information (e.g., for debugging) to the program [20, 42, 83, 93].
Many types of programs, e.g. scanners and parsers, use a table or other
data structure to control the program. It is often possible to achieve speed-up
by partially evaluating the table-driven program with respect to a particular
table [7, 78]. However, this may produce very large residual programs, as tables
(unless sparse) often represent the information more compactly than does code.
These are examples of converting structural knowledge representation to procedural
knowledge representation. The choice between these two types of representation
has usually been determined by the idea that structural information
is compact and easy to modify but slow to use while procedural information
is fast to use but hard to modify and less compact. Automatically converting
structural knowledge to procedural knowledge can overcome the disadvantage
of difficult modifiability of procedural knowledge, but retains the disadvantage
of large space usage.
Section 7.1 mentioned a few applications of specialization to computer graph-
ics. This has been one of the areas that have seen most applications of partial
evaluation. An early example is [49], where an extended form of partial evaluation
is used to specialize a renderer used in a flight simulator.
In a flight simulator the same landscape is viewed repeatedly from different
angles. Though the occlusion of surfaces depend on the angle of view, it is
often the case that the knowledge that a particular surface occludes (or not)
another can decide the occlusion question of other pairs of surfaces. Hence, the
partial evaluator simulates the sorting of surfaces and when it cannot decide
which of two surfaces must be plotted first, it leaves that test in the residual
program. Furthermore, it uses the inequalities of the occlusion test as positive
and negative constraints in the branches of the conditional it generates. These
constraints are then used to decide later occlusion tests (by attempting to solve
the constraints by the Simplex method). Each time a test cannot be decided
more information is added to the constraint set (which effectively constrains the
view-angle), allowing more later tests to be decided. Goad reports that for a
typical landscape with 1135 surfaces (forming a triangulation of the landscape)
the typical depth of paths in the residual decision tree was 27, compared to the
more than 10000 comparisons needed for a full sort [49]. This rather extreme
speed-up is due to the nature of landscapes: many surfaces are almost parallel,
and hence can occlude each other only in very narrow viewing angles.
Another graphics application has been ray-tracing. In ray-tracing, a scene is
rendered by tracing rays (lines) from each pixel on the screen into an imaginary
world behind the scene, testing which objects these rays hit. The process is
repeated for all rays using the same fixed scene. Since there may be millions of
pixels (and hence rays) in a typical ray-tracing application, specialization with
respect to a fixed scene but unknown ray can give speed-up even for rendering
single pictures. Speed-ups of more than 6 have been reported for a simple ray-tracer
[73]. For a more realistic ray-tracer, speed-ups in the range 1.5 to 3 have
been reported [10]. The speed-up is gained from several sources: the ray/object
intersection routine is specialized for each object and the (highly parametrized)
shading (colouring) function is specialized for each object. Furthermore, the
representation of the scene is converted to procedural form.

Figure

1 is an example of a ray-traced picture made by the ray-tracer from
[73]. The picture shows a 3D diagram of the process of partial evaluation: A
program P and one of its inputs x are fed to the partial evaluator PE yielding
a residual program P x .
Partial evaluation has also been applied to numerical computation, in particular
simulation programs. In such programs, part of the model will be constant
during the simulation while other parts will change. By specializing with respect
to the fixed parts of the model, some speed-up can be obtained. An example
is the N-body problem, simulating the interaction of moving objects through
gravitational forces. In this simulation, the masses of the objects are constant,
whereas their position and velocity change. Specializing with respect to the
mass of the objects can speed up the simulation. Berlin reports speed-ups of
more than 30 for this problem [15]. However, the residual program is written
in C whereas the original one was in Scheme, which may account for part of
the speed-up. In another experiment, specialization of some standard numerical
algorithms gave speed-ups ranging from none at all to about 5 [47].
When neural networks are trained, they are usually run several thousand
times on a number of test cases. During this training, various parameters will
be fixed, e.g. the topology of the net, the learning rate and the momentum.
By specializing the trainer to these parameters, speed-ups of 25 to 50% are
reported [56].
This list of applications is not exhaustive, but should give an impression of
the range of possibilities.
9 Further reading
Here we first sketch the history from 1952 to 1984, then give a number of pointers
to the literature on partial evaluation and some related topics. The book by
Jones, Gomard, and Sestoft [58] includes more material on the subjects mentioned
above, and a large bibliography; the updated source text for that bibliography
is available for anonymous ftp from ftp.diku.dk as file
pub/diku/dists/jones-book/partial-eval.bib.Z.
9.1 History
Kleene's s-m-n theorem (1952) asserts the feasibility of partial evaluation [63],
and his constructive proof provides the design for a partial evaluator. This design
did not, and was not intended to, provide any improvement of the specialized
program. Such improvement, by symbolic reductions or similar, has been the
goal in all subsequent work in partial evaluation.
Lombardi is probably the first one to use the term 'partial evaluation' [69].
Futamura is the first researcher to consider a partial evaluator as a program as
well as a transformer, and thus to consider the application of the partial evaluator
to itself [40]. Futamura's paper gives the equations for compilation and compiler
generation by partial evaluation, but not for compiler generator generation. The

Figure

1: Partial evaluation in action
three equations were called the Futamura projections by Andrei Ershov [38].
Futamura's early ideas were not implemented.
Around 1975, Beckman, Haraldsson, Oskarsson, and Sandewall developed
a partial evaluator called Redfun for a substantial subset of Lisp [12], and described
the possibility of compiler generator generation by double self-application.
Turchin and his group also worked with partial evaluation in the early 1970s,
in the context of the functional language Refal, and gave a description of self-application
and double self-application [94]. The history of that work is briefly
summarized in English in [95].
Andrei Ershov worked with imperative languages, and used the term mixed
computation to mean roughly the same as partial evaluation [34, 35].
In 1984, Jones, Sestoft, and S-ndergaard constructed a self-applicable partial
evaluator for a simple first-order functional language [59, 60, 86]; until then
neither single nor double self-application had been carried out in practice.
At the same time the interest in partial evaluation in logic programming and
other areas was increasing. This was the background for the 1987 Workshop on
Partial Evaluation and Mixed Computation [19, 39]. Subsequent proceedings on
partial evaluation may be found in [2, 3, 4, 5, 32, 88].
9.2 Partial evaluators
Imperative languages: Early papers on partial evaluation for imperative languages
include [34, 36, 37]. Bulyonkov and Ershov reported a self-applicable
partial evaluator for a flow chart language [25]; so did Gomard and Jones [50].
Gl-uck et al. created a (non-self-applicable) specializer for numeral algorithms in
Fortran [11, 47]. Andersen [6, 8, 9] developed two systems for specialization of
C programs; see Section 6.3.
Lisp and Scheme: The first major partial evaluator for Lisp was Redfun,
reported by Beckman et al. [12]. Weise et al. constructed a fully automatic online
partial evaluator for a subset of Scheme [100]. Jones et al. constructed a self-
applicable partial evaluator for a first-order functional language [59, 60]; Romanenko
improved it in various respects [81]. Consel constructed the self-applicable
partial evaluator Schism for a Scheme subset, handling partially static structures
and polyvariant binding times [28, 29, 31]. Bondorf and Danvy constructed the
self-applicable partial evaluator Similix for a subset of Scheme [20, 21].
Standard ML: Danvy, Heintze, and Malmkjaer developed the partial evaluator
Pell-Mell [70]. Birkedal and Welinder created a generator of generating
extensions [17, 18].
Refal and supercompilation: Turchin created the Refal language and developed
the program transformation techniques of driving and supercompilation,
which generalize partial evaluation [95, 96, 97]. A number of recent surveys on
driving and supercompilation exist [48, 89, 90, 91].
Prolog partial evaluation was pioneered by Komorowski [64, 65]; subsequent
work on Prolog includes [13, 44, 45, 66, 93, 98, 99]. Sahlin constructed a practical
but non-self-applicable partial evaluator for full Prolog [84, 85]. Bondorf and
Mogensen [76] constructed a self-applicable partial evaluator for a Prolog subset,
Gurr one for the logic language G-odel [52]. J-rgensen and Leuschel created a
generator of generating extensions for Prolog [62].
9.3 Related topics
McCarthy used program transformation rules in calculational proofs for recursive
functional programs [72]. Boyer and Moore automated some proofs of this
kind [22].
Burstall and Darlington viewed 'manual' program transformation as the application
of a few types of meaning-preserving program rewritings: definition,
instantiation, unfolding, folding, abstraction, and laws [26].
Partial evaluation specializes a program forwards by using knowledge about
available input. Conversely, program slicing specializes a program backwards,
using knowledge about the demand for output [79].



--R

A compiler based on partial evalu- ation
New Haven



Partial evaluation of C and automatic compiler generation (extended abstract).


Program Analysis and Specialization for the C Programming Language.
Partial evaluation applied to ray tracing.
Partial evaluation of numerical programs in Fortran.
A partial evaluator
A partial evaluation procedure for logic pro- grams
Compiling scientific code using partial evaluation.
Partial evaluation applied to numerical computation.
Partial evaluation of Standard ML.


Partial Evaluation and Mixed Computation.

Automatic autoprojection of higher order recursive equations.
Proving theorems about Lisp functions.
A general criterion for avoiding infinite unfolding.
Polyvariant mixed computation for analyzer programs.
How do ad-hoc compiler constructs appear in universal mixed computation processes? In
A transformation system for developing recursive programs.
Compiling or-parallelism into and-parallelism
New insights into partial evaluation: The Schism experiment.
Binding time analysis for higher order untyped functional lan- guages

The Schism Manual
Dagstuhl Seminar on Partial Evaluation
On compiling embedded languages in Lisp.
On the partial computation principle.
Mixed computation in the class of recursive program schemata.
On the essence of compilation.
Mixed computation: Potential applications and problems for study.
On Futamura projections.
Special Issue: Selected Papers from the Workshop on Partial Evaluation and Mixed Computation
Partial evaluation of computation process - an approach to a compiler-compiler
Generalized partial computation.
Transforming logic programs by specialising interpreters.
Tutorial on specialisation of logic programs.
Some low-level source transformations for logic programs
Specialisation of Prolog and FCP programs using abstract interpretation.
Generating optimizing specializers.

Application of metasystem transition to function inversion and transformation.
Automatic construction of special purpose programs.
Compiler generation by partial evaluation.
A partial evaluator for the untyped lambda- calculus

Efficient type inference for higher-order binding-time analysis
Finiteness analysis.
Handwriting cogen to avoid problems with static typing.
Speeding up the back-propagation algorithm by partial evaluation
Automatic program specialization: A re-examination from basic principles
Partial Evaluation and Automatic Program Generation.
An experiment in partial evaluation: The generation of a compiler generator.

Generating a compiler for a lazy language by partial eval- uation
Efficiently generating efficient generating extensions in Prolog.
Introduction to Metamathematics.
A Specification of an Abstract Prolog Machine and Its Application to Partial Evaluation.
Partial evaluation as a means for inferencing data structures in an applicative language: A theory and implementation in the case of Prolog.
A Prolog partial evaluation system.
A strongly-typed self-applicable partial evaluator
Partial evaluation in logic program- ming
Lisp as the language for an incremental computer.
ML partial evaluation using set-based analysis
Ensuring global termination of partial deduction while allowing flexible polyvariance.
A basis for a mathematical theory of computation.
The application of partial evaluation to ray-tracing



Converting interpreters into compilers.
Comparative efficiency of general and residual parsers.
Program specialization via program slicing.
The realm of Nevryon.
A compiler generator produced by a self-applicable specializer can have a surprisingly natural and understandable structure
On the specialization of online program specializers.
Meta interpreters for real.
The Mixtus approach to automatic partial evaluation of full Prolog.
An Automatic Partial Evaluator for Full Prolog.
The structure of a self-applicable partial evaluator
Automatic call unfolding in a partial evaluator.
Special Issue on Partial Evaluation and
Turchin's supercompiler revisited.
An algorithm of generalization in positive supercompilation.
Towards unifying partial eval- uation
How to have your cake and eat it
Partial evaluation of Prolog programs and its application to meta programming.
Basic Refal and Its Implementation on Computers.
A supercompiler system based on the language Refal.
The concept of a supercompiler.
Program transformation with metasystem transitions.
A Prolog meta-interpreter for partial evaluation and its application to source to source transformation and query-optimisation
A partial evaluation system for Prolog: Some practical considerations.
Automatic online partial evaluation.
--TR

--CTR
Mohan Rajagopalan , Saumya K. Debray , Matti A. Hiltunen , Richard D. Schlichting, Profile-directed optimization of event-based programs, ACM SIGPLAN Notices, v.37 n.5, May 2002
Arvind S. Krishna , Aniruddha Gokhale , Douglas C. Schmidt , Venkatesh Prasad Ranganath , John Hatcliff, Towards highly optimized real-time middleware for software product-line architectures, ACM SIGBED Review, v.3 n.1, p.13-16, January 2006
Arvind S. Krishna , Aniruddha S. Gokhale , Douglas C. Schmidt, Context-specific middleware specialization techniques for optimizing software product-line architectures, ACM SIGOPS Operating Systems Review, v.40 n.4, October 2006
Yasushi Shinjo , Calton Pu, Achieving Efficiency and Portability in Systems Software: A Case Study on POSIX-Compliant Multithreaded Programs, IEEE Transactions on Software Engineering, v.31 n.9, p.785-800, September 2005
Anne-Franoise Le Meur , Julia L. Lawall , Charles Consel, Towards bridging the gap between programming languages and partial evaluation, ACM SIGPLAN Notices, v.37 n.3, p.9-18, March 2002
Jacques Carette, Gaussian elimination: a case study in efficient genericity with MetaOCaml, Science of Computer Programming, v.62 n.1, p.3-24, September 2006
Anne-Franoise Le Meur , Julia L. Lawall , Charles Consel, Specialization Scenarios: A Pragmatic Approach to Declaring Program Specialization, Higher-Order and Symbolic Computation, v.17 n.1-2, p.47-92, March-June 2004
interpreters;software architectures;program specialization;genericity;adaptability;selective broadcast;partial evaluation;software layers;extensibility;pattern matching