Jones optimality, binding-time improvements, and the strength of program specializers.
Jones optimality tells us that a program specializer is strong enough to remove an entire level of self-interpretation. We show that Jones optimality, which was originally aimed at the Futamura projections, plays an important role in binding-time improvements. The main results show that, regardless of the binding-time improvements which we apply to a source program, no matter how extensively, a specializer that is not Jones-optimal is strictly weaker than a specializer which is Jones optimal. By viewing a binding-time improver as a generating extension of a self-interpreter, we can connect our results with previous work on the interpretive approach.
INTRODUCTION
Binding-time improvements are semantics-preserving
transformations that are applied to a source program prior
to program specialization. Instead of specializing the original
program, the modified program is specialized. The goal
is to produce residual programs that are better in some
sense than the ones produced from the original program.
A classical example [6] is the binding-time improvement of
a naive pattern matcher so that an o#ine partial evaluator
[20] can produce from it specialized pattern matchers
that are as e#cient as those generated by the Knuth, Morris
(an o#ine partial evaluator
cannot achieve this optimization without a suitable binding-time
improvement).
It is well-known that two programs which are functionally
equivalent may specialize very di#erently. Binding-time improvements
can lead to faster residual programs by improving
the flow of static data, or make a specializer terminate
more often by dynamizing static computations. Numerous
binding-time improvements are described in the literature
(e.g., [3, 7, 20]); they are routinely used for o#ine and on-line
specializers. The main advantage is that they do not
require a user to modify the specializer in order to overcome
the limitations of its specialization method. Hence, they are
handy in many practical situations.
Not surprisingly, several questions have been raised about
binding-time improving programs: What are the limitations
of binding-time improvements, and under what conditions
can these modifications trigger a desired specialization ef-
fect? Is it good luck that a naive pattern matcher may be
rewritten so as to lead an o#ine partial evaluator to perform
the KMP-optimization, or can such binding-time improvements
be found for any problem and for any specializer?
This paper answers these and related questions on a conceptual
level. We will not rely on a particular specialization
method or on other technical details. We are interested in
statements that are valid for all specializers, and we have
identified such conditions.

Figure

1 shows the structure of a specializer system employing
a binding-time improver as a preprocessor. The
binding-time improver bti takes a program p and a division
SD, which classifies p's parameters as static and dynamic,
and returns a functionally equivalent program p # . This program
is then specialized with respect to the static data x
by the specializer spec. The specializer and the binding-time
improver take the division SD as input, but the static
specializer system
spec

Figure

1: Binding-time improver as preprocessor of
a program specializer
data x is only available to the specializer. This flow of
the transformation is common to virtually all specializer
systems. Usually, the specializer is an automatic program
transformer, while the binding-time improvements are often
done by hand. For our investigation, it does not matter how
these steps are performed.
The results in this paper extend previous work on Jones
optimality [18, 28, 22, 32] and the interpretive approach [11,
13, 34]. We will see that Jones optimality [18] plays a key
role in the power of binding-time improvers and, together
with static expression reduction, establishes a certain kind
of non-triviality. Among others, we will precisely answer the
old question whether an o#ine partial evaluator can be as
powerful as an online partial evaluator.
This paper is organized as follows. After reviewing standard
definitions of interpreters and specializers (Sect. 2), we
present the two main ingredients for our work, Jones optimality
(Sect. improvers (Sect. 4). The
main results are proven (Sect. 5) and additional theorems
are presented (Sect. 6). The connection with the interpretive
approach is established (Sect. 7) and opportunities for
optimizing our constructions are discussed (Sect. 8). We
conclude with related work (Sect. and challenges for future
work (Sect. 10).
We assume that the reader is familiar with partial evalu-
ation, e.g., as presented in [20, Part II].
2. PRELIMINARIES
This section reviews standard definitions of interpreters
and specializers. The notation is adapted from [20]; we use
divisions (SD) when classifying the parameters of a program
as static and dynamic. 1 We assume that we are always
dealing with universal programming languages.
2.1 Notation
For any program text, p, written in language L, we let
denote the application of L-program p to its input d
(when the index L is unspecified, we assume that a language
L is intended). Multiple arguments are written as list, such
as . The notation is strict in its arguments.
Equality between program applications shall always mean
strong (computational) equivalence: either both sides of an
This does not imply that our specializers use o#ine partial
evaluation.
equation are defined and equal, or both sides are undefined.
Programs and their input and output are drawn from a common
data domain D . Including all program texts in D is
convenient when dealing with programs that accept both
programs and data as input (a suitable choice for D is the
set of lists known from Lisp). We define a program domain
but leave the programming language unspecified.
Elements of the data domain evaluate to themselves. Programs
are applied by enclosing them in
When we define a program using #-abstraction, the expression
needs to be translated into the corresponding programming
language (denoted by p# .q # P). The translation
is always possible when L is a universal programming
language.
2.2 Interpreters and Specializers
What follows are standard definitions of interpreters and
specializers.
Definition 1. (interpreter) An L-program int # Int is an
Definition 2. (self-interpreter) An L-program sint # Sint
is a self-interpreter for L i# sint is an L/L-interpreter.
Definition 3. (specializer) An L-program spec # Spec is a
specializer for L i#p # P , #x , y
For simplicity, we assume that the programs which we specialize
have two arguments, and that the first argument is
static. Even though we make use of only division SD in the
definition, we keep it explicit (for reasons explained in [12]).
A specializer need not be total. The definition allows spec
to diverge on [ p, SD, x diverges on [ x , y ] for all y . In
practice, specializers often sacrifice the termination behav-
ior. For a discussion of termination issues see [19].
A specializer is trivial if the residual programs it produces
are simple instantiations of the source programs.
Definition 4. (trivial specializer) An L-specializer spec triv
# Spec is trivial
More realistic specializers evaluate static expressions in a
source program. An expression is static if it depends only
on known data and, thus, can be precomputed at specialization
time. We define a special case of static expression
reduction which is su#cient for our purposes. The definition
of running time is taken from [20, Sect. 3.1.7]. 2
Definition 5. (running time) For program data
d1 , ., dn # D , let t p (d1 , ., dn ) denote the running time to
Definition 6. (static expression reduction) A specializer
spec # Spec has static expression reduction if #q , q # P ,
2 The measure for the running time can be a timed semantics
(e.g., the number of elementary computation steps).
The definition tells us that, in terms of residual-program
e#ciency, there is no di#erence between specializing program
q with respect to a value specializing the
composition p of q and q # with respect to a value x . This
implies that the specializer contains at least an interpreter
(a universal program) to evaluate static applications (here
a in the definition of p).
A specializer with static expression reduction is non-trivial.
The definition implies that it has the power to perform universal
computations. Most specializers that have been im-
plemented, including online and o#ine partial evaluators,
try to evaluate as many static expressions as possible to improve
the e#ciency of the residual programs. They satisfy
the static expression reduction property given above.
3. JONES OPTIMALITY
When translating a program by specializing an interpreter,
it is important that the entire interpretation overhead is re-
moved. Let us look at this problem more closely and then
explain the definition of Jones optimality.
3.1 Translation by Specialization
Let p be an N -program, let intN be an N /L-interpreter,
and let spec be a specializer for L. Then the 1st Futamura
projection [9] is defined by
Using Defs. 1 and 3 we have the functional equivalence between
q and p:
Note that program p is written in language N , while program
q is written in language L. This N -to-L-translation
was achieved by specializing the N /L-interpreter intN with
respect to p. We say that q is the target program of source
program p. The translation can always be performed. Consider
a trivial specializer. The first argument of intN is
instantiated to p, and the result is a trivial target program:
Clearly, this is not the translation we expect. The target
program is ine#cient: it contains an entire interpreter. A
natural goal is therefore to produce target programs that
are as e#cient as their source programs. Unfortunately, we
cannot expect a specializer to produce e#cient target programs
from any interpreter. For non-trivial languages, no
specializer exists [16] that could make 'maximal use' of the
static input, here p, in all programs.
3.2 Jones-Optimal Specialization
A specializer is said to be "strong enough" [18] if it can
completely remove the interpretation overhead of a self-inter-
preter. The definition is adapted from [20, 6.4]; it makes use
of the 1st Futamura projection.
Definition 7. (Jones optimality) Let sint # Sint be a self-
interpreter, then a specializer spec # Spec is Jones-optimal
for sint i# Jopt(spec, sint) where
A specializer spec is said to be Jones-optimal if there exists
at least one self-interpreter sint such that, for all source
programs p, the target program p # is at least as e#cient for
all inputs d as the source program p. This tells us that spec
can remove an entire layer of self-interpretation.
The case of self-interpreter specialization is interesting because
it is easy to judge to what extent the interpretive overhead
has been removed by comparing the source and target
programs, as they are written in the same language. In
particular, when programs p and p # are identical, it is safe
to conclude that this goal is achieved. Also, as explained
in [25], the limits on the structure of residual programs that
are inherited from structural bounds in the source programs
are best observed by specializing a self-interpreter (e.g., the
arity of function definitions in a residual program).
It is easy to require Jones optimality, but it is not always
easy to satisfy it. For instance, for a partial evaluator
for a first-order functional language with algebraic data
types [25], a combination of several transformation methods
is necessary (constant folding, unfolding, polyvariant
specialization, partially static values, constructor specializa-
tion, type specialization).
Jones optimality was first proven [28] for lambda-mix; see
also [24]. The first implementation of a Jones-optimal specializer
was the o#ine partial evaluator [26] for a Lisp-like
language. An early o#ine partial evaluator [23] for a similar
language utilizes partially static structures to produce near-
identity mappings. For many specializers it is not known
whether they are Jones-optimal or not. For other partial
evaluators, such as FCL-mix [15], it is impossible to write
a self-interpreter that makes them Jones optimal. Recent
work [32] on Jones optimality concerns tag-elimination when
specializing self-interpreters for strongly typed languages.
Note that the definition of Jones optimality can be satisfied
by a simple construction
else
where mysint is a fixed self-interpreter for which we want
myspec to be Jones-optimal and spec triv is the trivial specializer
from Def. 4. Specializer myspec returns the last
argument, x , unchanged if the first argument, p, is equal
to mysint ; otherwise, myspec performs a trivial specializa-
tion. Clearly, such a specializer is not useful in practice, but
formally Jopt(myspec, mysint).
Finally, we show that a Jones-optimal specializer with
static expression reduction exists. This fact will play an
important role in the next sections. Both properties can be
satisfied by a simple construction
myspec stat
case p of
where case implements pattern matching: if program p consists
of a composition of two arbitrary programs, then p is
decomposed 3 into q and q # , and q is specialized with respect
to the result of evaluating [[sint
is a self-interpreter; otherwise p is specialized with respect
to x . The specializer is Jones-optimal for mysint and has
the expression reduction property of Def. 6. More realistic
3 We shall not be concerned with the technical details of
parsing an L-program p.
Jones-optimal specializers, for instance [26, 23, 25, 28], also
satisfy the property of static expression reduction.
4. BINDING-TIME IMPROVERS
Binding-time improvements [20] are semantics-preserving
transformations that are applied to a source program before
specialization with the aim to produce residual programs
that are better in some sense than those produced from the
original source program. Numerous binding-time improvements
have been described in the literature (e.g., [3, 7, 20]).
Formally, a binding-time improver is a program that takes
a program p and a division of p's arguments into static and
dynamic, and then transforms p into a functionally equivalent
program p # . A binding-time improver performs the
transformation independently of the static values that are
available to a specializer.
Definition 8. (binding-time improver) An L-program bti
# Bti is a binding-time improver for L
Using Defs. 3 and 8, we have the following functional equivalence
between the residual programs r and r # produced by
directly specializing p and specializing a binding-time improved
version of p:
In practice, we expect (and hope) that program r # is better,
in some sense, than program r . For example, binding-time
improvements can lead to faster residual programs by improving
the flow of static information at specialization time.
It is important to note that a binding-timer improver cannot
precompute a residual program since there are no static
values, nor can it make a table containing all possible residual
programs since in general the specialization of a source
program allows for an infinite number of di#erent residual
programs. (Compare this to a translator: a translator cannot
just precompute all results of a source program and store
them, say, in a table in the target program since, in general,
there is an infinite number of di#erent results.)
The term "binding-time improvement" was originally
coined in the context of o#ine partial evaluation [20] to improve
the flow of static information, but such easing transformations
are routinely used for all specialization methods.
This is not surprising since there exists no specialization
method that could make 'maximal use' of available information
in all cases. We use the term binding-time improvement
for any semantics-preserving pre-transformation and
regardless of a particular specialization method.
Note that Def. 8 does not require that each source program
is transformed: the identity transformation,
is a correct (but trivial) binding-time improver. Of course,
for a binding-time improver to be useful, it must perform
non-trivial transformations at least on some programs; oth-
erwise, the residual programs r and r # in (4) are always
identical.
5. JONESOPTIMALITY&BINDING-TIME
IMPROVEMENTS
In the previous sections, two di#erent streams of ideas
were presented, binding-time improvements and Jones optimality
for the specialization of programs. How are they
related? We put these ideas together and present the two
main results.
5.1 Sufficient Condition
The first theorem tells us that for every Jones-optimal
specializer spec 1 there exists a binding-time improver that
allows the specializer to achieve the residual-program e#-
ciency of any other specializer (Jones optimality is a su#-
cient condition). The proof makes use of a general construction
of such a bti .
Theorem 1. (Jones optimality is su#cient) For all specializers
reduction, the
following holds:
Proof: We proceed in two steps.
1. Let sint 1 be the self-interpreter for which spec 1 is Jones-
optimal. For each specializer spec 2 , define a binding-time
improver
| {z }
two stages
q .
The binding-time improver depends on sint 1 and spec 2 ,
but not on program p. Given a program p and a division
SD, program bti produces a new program that
performs p's computation in two stages: first, spec 2
specializes p with respect to x , then sint 1 evaluates
the residual program with the remaining input y . From
Defs. 2 and 3, it follows that the new program is functionally
equivalent to p. According to Def. 8, bti is a
binding-time improver since #p # P , #x , y
2. Consider the rhs of the implication in Thm. 1. For
each spec 2 , let bti be the binding-time improver defined
in (6). Let p be a program and let x be some data, then
we have the binding-time improved program
and obtain the residual program r # by specializing p #
with respect to x :
reduces static expressions and since p # is of
a form that suits Def. 6, we can rewrite (8) as (9) and
obtain a program r # :
After evaluating the application of spec 2 in (9), we obtain
(10); recall that in the rhs
of the implication. Then r # in (11) is the result of specializing
sint 1 with respect to r by spec 1 . Program r #
is as fast as r # according to Def. 6. From the specialization
in (10) and Jopt(spec 1 , sint 1 ), we conclude that
r # is at least as fast as r since #y # D :
This relation holds for any p and for any x . This proves
the theorem.
5.2 Necessary Condition
The second theorem tells us that a specializer spec 1 that is
not Jones-optimal cannot always reach the residual-program
e#ciency of another specializer spec 2 (Jones optimality is a
necessary condition).
Theorem 2. (Jones optimality is necessary) For all specializers
the following holds:
Proof: Assume that the rhs of the implication holds. Choose
Sint such that Jopt(spec 2 , sint 2 ) .
Such a specializer exists for any non-trivial programming
language (e.g., myspec in Sect. 3). Let bti be a binding-time
improver which satisfies the rhs of the implication with
respect to spec 2 , and define
sint
Since bti is a binding-time improver and sint 2 is a self-
sint 1 is also a self-interpreter. In the rhs of
the implication, let p be sint 2 , let x be a program q , and let
y be some data d . Then we have
where
Since Jopt(spec 2 , sint 2 ), we have that
By combining (14) and (16), we realize that
This relation holds for any q and for any d , thus we conclude
that Jopt(spec 1 , sint 1 ). This proves the theorem.
The second theorem does not imply that a specializer that
is not Jones-optimal cannot benefit from binding-time im-
provements, but that there is a limit to what can be achieved
by a binding-time improver if spec 1 is not Jones-optimal.
Observe from the proof of Thm. 2 that the rhs of the implication
can be weakened: instead of quantification "#spec 2 #
Spec", all that is needed is quantification "#spec 2 # Spec,
Remark: In the literature [22], Jones optimality is often
defined using r (y). Under this
assumption, it follows directly from the rhs in Thm. 2 that
must reduce static expressions if spec 2 does.
5.3 Discussion
1. By combining both theorems, we can conclude that, in
terms of residual-program e#ciency, a specializer that
is not Jones-optimal is strictly weaker than a specializer
that is Jones-optimal.
2. The question whether an o#ine partial evaluator can
be as powerful as an online partial evaluator can now
be answered precisely: an o#ine partial evaluator with
static expression reduction that is Jones-optimal can
achieve the residual-program e#ciency of any online
partial evaluator by using a suitable binding-time im-
prover. The binding-time improver depends on the
partial evaluators but not on the source programs.
3. Jones optimality is important for more than just building
specializers that work well with the Futamura pro-
jections. Previously it was found only in the intuition
that it would be a good property [17, 18]. The theorems
give formal status to the term "optimal" in the
name of that criterion.
4. The results also support the observation [25] that a
specializer has a weakness if it cannot overcome inherited
limits and that they are best observed through
specializing a self-interpreter (which amounts to testing
whether a specializer is Jones-optimal).
A way to test the strength of a specializer is to see whether it
can derive certain well-known e#cient programs from naive
and ine#cient programs. One of the most popular tests [10,
6, 29, 2] is to see whether the specializer generates, from
a naive pattern matcher and a fixed pattern, an e#cient
pattern matcher. What makes Jones optimality stand out
in comparison to such tests is that while a Jones-optimal
specializer with static expression reduction is guaranteed to
pass any of these tests by a suitable binding-time improvement
(Thm. 1), a specializer may successfully pass any number
of these tests, but as long as it is not Jones-optimal, its
strength is limited in some way (Thm. 2).
Even though the construction of the binding-time im-
prover used in the proof of Thm. 1 suggests that each source
program p is transformed into a new p # , such a deep transformation
may not be necessary in all cases. To what extent
each source program needs to be transformed in practice depends
on the desired optimization and the actual power of
the specializer spec 1 . More realistic binding-time improvers
will not need to transform each source program.
6. ROBUSTNESS
This section presents two results regarding Jones opti-
mality. They establish a certain kind of non-triviality for a
Jones-optimal specializers with static expression reduction.
In particular, they tell us that there is an infinite number of
self-interpreters for which a Jones-optimal specializer with
static expression reductions is also Jones-optimal.
Theorem 3. (Jones optimality not singularity) Let spec 1 ,
be two Jones-optimal specializers where spec 1
reduces static expressions, and let sint 1 , sint 2 # Sint be two
self-interpreters such that Jopt(spec 1 , sint 1 ) and Jopt(spec 2 ,
sint 2 ), then there exists a self-interpreter sint 3 # Sint , different
beyond renaming from sint 1 and sint 2 , such that
Proof: The proof uses a construction that combines two
self-interpreters and a specializer into a new self-interpreter
without breaking Jones optimality. Define the self-inter-
preter sint 3 by
sint 3
The new self-interpreter sint 3 is di#erent beyond renaming
from the self-interpreters sint 1 and sint 2 since sint 3 contains
both programs. To show Jopt(spec 1 , sint 3 ), we examine how
spec 1 specializes sint 3 . Since spec 1 reduces static expressions
and since sint 3 is of a form that suits Def. 6, we have
then we can conclude from
this relation holds for any p and any d , we have the desired
property Jopt(spec 1 , sint 3 ). This proves the theorem.
First, we observe that spec 1 can be 'more' Jones-optimal for
sint 3 than spec 2 for sint can be faster than p #
which in turn can be faster than p. This is not surprising
since specializers are usually not idempotent, and repeatedly
applying a specializer to a program can lead to further opti-
mizations. This is known from the area of compiler construction
where an optimization may enable further optimization.
This also underlines that it is realistic to choose the timing
condition (#) in Def. 7, as already discussed in Sect. 3.
Second, as a special case of Thm. 3, let spec
and sint . Then we can conclude by repeatedly
applying the theorem that for every Jones-optimal specializer
with static expression reduction there exists an infinite
number of self-interpreters for which the specializer is also
Jones optimal. We state this more formally in the following
theorem.
Theorem 4. (Jones optimality is robust) Let spec # Spec
be a specializer with static expression reduction and let sint #
Sint be a self-interpreter such that Jopt(spec, sint), then we
1. There exists an infinite number of self-interpreters sint i
Sint , which are pairwise di#erent beyond renaming,
such that Jopt(spec, sint i ).
2. There exists an infinite number of specializers spec i #
Spec, which are pairwise di#erent beyond renaming,
such that Jopt(spec i , sint).
Proof: Let copy 0 be a program such that
for all d # D . Define any number of programs copy i+1 as
copy
For all d # D , we have
copy j are di#erent beyond renaming (i # j # 0).
1. Define any number of programs sint i (i # 0):
sint i
Each sint i is a self-interpreter, and all self-interpreters
are di#erent beyond renaming since they contain different
copy programs. Each sint i is of the form used in
Def. 6 and we conclude Jopt(spec, sint i ) since
2. Define any number of programs spec i (i # 0):
Each spec i is a specializer, and all specializers are di#er-
ent beyond renaming since they contain di#erent copy
programs. We conclude that Jopt(spec i , sint) since
This proves the theorem. Remark: the first item can also
be proven by using the construction in the proof of Thm. 3.
The requirement for static expression reduction in both theorems
hints at a certain kind of non-triviality of such Jones-
optimal specializers (also suggested by Thm. 1). With static
expression reduction, we can be sure that Jones optimality is
not just a 'singularity' for a specializer, but that there is an
infinite number of such self-interpreters. A Jones-optimal
specializer with static expression reduction can be said to
be robust with respect to certain non-trivial modifications
of the self-interpreters. This e#ectively excludes the Jones-
optimal specializer myspec defined in Sect. 3. This may be
the kind of fairness sought for in earlier work [22].
7. THREE TECHNIQUES FOR BINDING-TIME
IMPROVING PROGRAMS
In this section we establish the connection between three
known techniques for doing binding-time improvements (Fig-
ure 2): using a stand-alone binding-time improver bti (c),
as we did in the previous sections, and stacking a source
program p with an instrumented self-interpreter (a, b). We
show that Thm. 1 and Thm. 2 cover the two new cases after
a few minor adaptions, and that all three techniques can
produce the same residual programs. Thus, they are equally
powerful with respect to doing binding-time improvements.
Consider the following fragments from Thm. 1 and Thm. 2
the binding-time improved version of p, is specialized
with respect to x :
Observe that bti has the functionality of a translator-if we
disregard the extra argument SD. It is well-known [20] that
the generating extension [8] of an interpreter is a transla-
tor. Since a binding-time improver has the functionality of
an L-to-L translator, it is a generating extension of a self-
interpreter for L.
Instead of binding-time improving p by bti , we can specialize
a suitable self-interpreter sint with respect to p. There
are two ways to produce a residual program by specializing
a self-interpreter: either directly by the specializer projections
[11] (a) or incrementally by the Futamura projections
[9] (b). We will now examine these two cases.
7.1 Incremental Specialization
Let bti be a binding-time improver, and suppose that
spec 0 is a specializer and sint 0 a self-interpreter such that 4
Using this equality, we obtain a new set of equations from
Thus, every binding-time improvement can be performed in
a translative way, as in (29), or in an interpretive way, as in
(32). An example [34] for the latter case is the polyvariant
expansion of a source program by specializing a suitable self-
interpreter, and then applying a binding-time monovariant
o#ine specializer to the modified program. The overall e#ect
of the transformation is that of a binding-time polyvariant
o#ine specializer, even though only a binding-time mono-
variant o#ine specializer was used to produce the residual
program. Similarly, it is known [21, 27, 30, 31] that optimizing
translators can be generated from suitable interpreters.
Such techniques can also be used in self-interpreters to improve
the specialization of programs.
Theorems 1 and 2 carry over to the interpretive case, provided
we replace in the rhs of their implication the quantification
by the quantification "#spec 0 # Spec,
#sint use (32, 33) instead of (29, 30).
7.2 Direct Specialization
The two steps (32, 33) can also be carried out in one step.
For notational convenience, let us first redefine the format of
a self-interpreter and of a specializer. This will make it easier
to accommodate programs with two and three arguments.
A self-interpreter sint # for interpreting programs with two
arguments can be defined by
and a specializer spec # for specializing programs with three
4 For every bti there exists a pair (spec 0 , sint 0 ) such
that (31), and vice versa (Prop. 1 and 2 in Appendix A).
arguments can be defined by
where program q is specialized with respect to one static
argument, a, in (35) and with respect to two static argu-
ments, a and b, in (36). The residual program then takes
the remaining arguments as input. Note that each case has
a di#erent division.
Using spec # , the two steps (32, 33) can be carried out in
one step. Let q be the self-interpreter sint # defined above,
let a be a two-argument program p, and let b and c be some
arguments x and y , respectively, then p can be specialized
with respect to x via sint # using (36):
That r # is a residual program of p follows from (34, 36):
Let bti be a binding-time improver and let spec 1 be a specializer
as in (29, 30), and suppose that spec # is a specializer
and sint # a self-interpreter such that 5
Equation (37) is the 1st specializer projection [11] but for
a self-interpreter instead of an interpreter. Specializing a
program via an interpreter is also known as the interpretive
approach [11]. An example [13] is the generation of a
KMP-style pattern matcher from a naive pattern matcher by
inserting an instrumented self-interpreter between the naive
pattern matcher and an o#ine partial evaluator (Similix).
As mentioned in Sect. 1, an o#ine partial evaluator cannot
achieve this optimization, but specializing the naive matcher
via an instrumented self-interpreter does the job. Another
example is the simulation of an online partial evaluator by
an o#ine partial evaluator [33], and the bootstrapping of
other program transformers [30].
Note that the transformation in (37) can be optimized at
another level: specializing spec # with respect to sint # yields a
new specializer. This internalizes the techniques of the self-
interpreter in the new specializer. This is know as the 2nd
specializer projection [11]; results on generating optimizing
specializers are reported elsewhere (e.g., [13, 33, 30]).
Again, both main theorems apply to this case by replacing
quantification "#bti # Bti " by "#sint # Sint " on the rhs of
the implication.
7.3

Summary

The three techniques for binding-time improving programs
are summarized in Fig. 2. They can produce the same residual
programs and, thus, are equally powerful with respect
to binding-time improving programs. Which technique is
preferable in practice, depends on the application at hand.
There exist example applications in the literature for each
case. The results in this section shed new light on the relation
between binding-time improvements and the interpretive
approach. Our two main theorems cover all three cases.
5 For every pair (spec 1 , bti) there exists a pair (spec # , sint # )
such that (39), and vice versa (Prop. 3 and 4 in Appendix A).
Direct specialization:
a. One step (1st specializer projection):
Incremental specialization:
b. Two steps (1st Futamura projection):
c. Three steps (2nd Futamura projection):

Figure

2: Three techniques for binding-time improving
programs
When we add to (29, 30) a step that generates the binding-time
improver from a self-interpreter, we obtain (40, 41, 42).
This is the 2nd Futamura projection. Detail: For formal
reasons, due to the definition of specializer spec # in (35), the
arguments of bti # are reordered.
8. OPTIMIZINGTHETHEORETICALCON-
The proof of Thm. 1 makes use of a general binding-time
improver. In many cases, only certain fragments that are relevant
to binding-time improving programs for a particular
specializer spec 1 need to be incorporated in a binding-time
improver, not the entire specializer (here spec 2 ). In the remainder
of this section, we will point out some possibilities
for optimizing the general construction by further program
specialization and program composition.
1. Specialization: We observe that the binding-time improved
produced by bti in (7) contains a specializer
whose argument is fixed to p. This makes the
program structure of p # much too general. Usually, not all
components of spec 2 are needed to specialize p. We can improve
the construction by replacing spec 2 by a generating
extension gen p of p, a program which is specified by
A generating extension gen p is a generator of p's residual
programs. We can use the following program instead of
| {z }
composition
x , y ]q . (44)
2. Composition: We notice the fixed composition of sint 1
and gen p in (44). An intermediate data structure, a residual
program, is produced by gen p and then consumed by
sint 1 . Methods for program composition may fuse the two
programs and eliminate intermediate data structures, code
generation, parsing and other redundant operations.
It will be interesting to examine whether some of the
known binding-time improvements can be justified starting
from the general construction, and whether new binding-time
improvers can be derived from the general construction
where spec 2 represents the desired level of specialization.
Lets us illustrate this with an example. Suppose onpe is
an online partial evaluator and o#pe is an o#ine partial evaluator
which reduces static expressions and is Jones-optimal
for self-interpreter sint . We have the specializers
According to Thm. 1 we have t r # (y) # t r (y) where the two
residual programs are produced by
and a binding-time improver defined by
After binding-time improving p with bti , the performance
of r # produced by o#pe is at least as good as the one of r
produced by onpe. Can we derive a useful binding-time im-
prover from bti by program specialization and program com-
position? Can we obtain automatically one of the binding-time
improved programs published in the literature (e.g., [6,
2]) by specializing bti with respect to a source program (e.g.,
a naive pattern matcher)?
Another challenging question is whether a binding-time
improver can be specified by combining 'atomic' binding-time
improvements, and how this relates to combining semantics
by towers of non-standard interpreters [1].
9. RELATED WORK
The first version of optimality appeared in [17, Problem
3.8] where a specializer was called "strong enough" if program
p and program are "essentially the
same programs". The definition of optimality used in this
paper appeared first in [18, p.650]; see also [20, Sect. 6.4].
Since the power of a specializer can be judged in many different
ways, we use the term "Jones optimality" as proposed
in [22]. These works focus on the problem of self-application;
none of them considers the role of Jones-optimal specialization
for binding-time improvements. Also, it was said [25]
that a specializer is 'weak' if it cannot overcome inherited
limits and that this is best observed by specializing a self-
interpreter. Our results underline this argument from the
perspective of binding-time improvements.
The term "binding-time improvement" was originally
coined in the context of o#ine partial evaluation [20], but
source-level transformations of programs prior to specialization
are routinely used in connection with any specialization
method. Binding-time improvements range from rearrangements
of expressions (e.g., using the associativity of arithmetic
operations) to transformations which require some ingenuity
(e.g., the transformation of naive pattern matchers
[6, 2]). Some transformations incorporate fragments of
a specializer [4]. A collection of binding-time improvements
for o#ine partial evaluation can be found in [3, Sect.7] and
in [20, Chapter 12]. The actual power of binding-time improvements
was not investigated in these works.
The idea [11] of controlling the properties of residual programs
by specializing a suitable interpreters was used to perform
deforestation and unification-based information propagation
[13, 14], binding-time polyvariant specialization [34,
30], and other transformations [30] with an o#ine partial
evaluator. These apparently di#erent streams of work are
now connected to binding-time improvements.
Related work [5] has shown that, without using binding-time
improvements, an o#ine partial evaluator with a maximally
polyvariant binding-time analysis is functionally equivalent
to an online partial evaluator, where both partial evaluators
are based on constant propagation. This paper shows
that any o#ine partial evaluator can simulate any online
partial evaluator with a suitable binding-time improver, provided
the o#ine partial evaluator is Jones-optimal.
10. CONCLUSION
Anecdotal evidence suggests that the binding-time improvement
of programs is a useful and inexpensive method
to overcome the limitations of a specializer without having
to modify the specializer itself. These pre-transformation
are often ad hoc, and applied to improve the specialization
of a few programs. It was not know what the theoretical limitation
and conditions for this method are, and how powerful
such pre-transformation can be.
Our results show that one can always overcome the limitations
of a Jones-optimal specializer that has static expression
reduction by using a suitable binding-time improve-
ment, and that this is not always the case for a specializer
that is not Jones-optimal. Thus, regardless of the binding-time
improvements which we perform on a source program,
no matter how extensively, a specializer which is not Jones-
optimal can be said to be strictly weaker than a specializer
which is Jones-optimal. This also answers the question
whether an o#ine partial evaluator can be as powerful as an
online partial evaluator.
Jones optimality was originally formulated to assess the
quality of a specializer for translating programs by specializing
interpreters. Our results give formal status to the term
"optimal" in the name of that criterion. Previously it was
found only in the intuition that it would be a good property;
indeed, it was proposed to rename it from "optimal special-
ization" to "Jones-optimal specialization" precisely because
it was felt to be wrong to imply that no specializer can be
better than a Jones-optimal one. This paper shows a way
in which this implication is indeed true.
The proofs make use of a construction of a binding-time
improver that works for any specializer. This construction
is su#cient for theoretical purposes, but not very practical
(it incorporates an entire specializer). In practice, there
will be more 'specialized' methods that produce the same
residual e#ect in connection with a particular specializer,
as evidenced by the numerous binding-time improvements
given in the literature. However, the universal construction
may provide new insights into the nature of binding-time
improvements. For instance, it will be interesting to
see whether some of the non-trivial binding-time improvements
(e.g., [6, 2]) can be justified by the universal construc-
tion, and whether new pre-transformations can be derived
from it (where the specializer incorporated in the universal
construction represents the desired specialization strength).
Eventually, this may lead to a better understanding of how
to design and reason about binding-time improvements.
Our results do not imply that specializers which are not
Jones-optimal cannot benefit from binding-time improve-
ments. For example, it seems that the KMP test can be
passed by an o#ine partial evaluator which is not Jones-
optimal. This leads to the question what are the practical
limits of specializers that are not Jones-optimal. More work
will be needed to identify cause and e#ect.
On a more concrete level, we are not aware of an on-line
partial evaluator that has been shown to be Jones-
optimal. This question should be answered positively, as it
was already done for o#ine partial evaluators. Also, there
is not much practical experience in building Jones-optimal
specializers for realistic programming languages. For in-
stance, more work will be needed on retyping transformations
for strongly typed languages to make these transformations
more standard, and more program specializers truly
Jones-optimal.

Acknowledgments

Comments by Sergei Abramov, Kenichi Asai, Mikhail Buly-
onkov, Niels Christensen, Yukiyoshi Kameyama, Siau-Cheng
Khoo, and Eijiro Sumii on an earlier version of this paper are
greatly appreciated. Special thanks are due to the anonymous
reviewers for thorough and careful reading of the submitted
paper and for providing many valuable comments. A
preliminary version of the paper was presented at the Second
Asian Workshop on Programming Languages and Systems,
Daejeon, South Korea.
11.



--R

Combining semantics with non-standard interpreter hierarchies
The abstraction and instantiation of string-matching programs
Similix 5.0 Manual.
Extracting polyvariant binding time analysis from polyvariant specializer.
On the equivalence of online and
Partial evaluation of pattern matching in strings.
For a better support of static data flow.
On the partial computation principle.
Partial evaluation of computing process - an approach to a compiler-compiler
Generalized partial computation.
On the generation of specializers.
On the mechanics of metasystem hierarchies in program transformation.
Generating optimizing specializers.
Generating transformers for deforestation and supercompilation.
Compiler generation by partial evaluation: a case study.
Partial evaluation and
Challenging problems in partial evaluation and mixed computation.
Partial evaluation
Program generation
Partial Evaluation and Automatic Program Generation.
Generating a compiler for a lazy language by partial evaluation.
On Jones-optimal specialization for strongly typed languages
Partially static structures in a self-applicable partial evaluator

Evolution of partial evaluators: removing inherited limits.
The structure of a self-applicable partial evaluator
ML pattern match compilation and partial evaluation.
Mechanical proof of the optimality of a partial evaluator.
A positive supercompiler.
Bootstrapping higher-order program transformers from interpreters
Realistic compilation by partial evaluation.
Tag elimination and Jones-optimality
The generation of a higher-order online partial evaluator
Polyvariant expansion and compiler generators.
--TR
Partial evaluation and MYAMPERSANDohgr;-completeness of algebraic specifications
The structure of a self-applicable partial evaluator
Partial evaluation of pattern matching in strings
Partial evaluation, self-application and types
For a better support of static data flow
Generating a compiler for a lazy language by partial evaluation
Partial evaluation and automatic program generation
Extracting polyvariant binding time analysis from polyvariant specializer
Realistic compilation by partial evaluation
Bootstrapping higher-order program transformers from interpreters
Program Generation, Termination, and Binding-Time Analysis
Tag Elimination and Jones-Optimality
On Jones-Optimal Specialization for Strongly Typed Languages
Polyvariant Expansion and Compiler Generators
Combining Semantics with Non-standard Interpreter Hierarchies
On the Mechanics of Metasystem Hierarchies in Program Transformation
Evolution of Partial Evaluators
MK Pattern Match Compilation and Partial Evaluation

--CTR
Niels H. Christensen , Robert Glck, Offline partial evaluation can be as accurate as online partial evaluation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.1, p.191-220, January 2004
futamura projections;metacomputation;interpretive approach;jones optimality;binding-time improvements;self-interpreters;specializer projections