Jones N.D.Partial evaluation and automatic program generation.1999

Exercises 141

int2	:= [[mix]]				[int1	;	int2	]	satisfying
0			L0		0		1
out = [[int2		]]	L0	[p2, in]
	0

4.By partial evaluation of int20 , L2-programs can be compiled to L0-programs. Better still, one may construct a compiler from L2 into L0 by

comp20 := [[cogen]]L0 int20

The net e ect is that metaprogramming may be used without order-of-magnitude loss of e ciency.

The development above, though conceptually complex, has actually been realized in practice by partial evaluation [71,138,139]. The rst two describe how J rgensen began with an interpreter for denotational semantics, and used partial evaluation to transform denotational de nitions into interpreters written in Scheme. An application was to a denotational de nition of a Miranda-like lazy programming language with pattern matching. The interpreter generated as in step 3 above was then converted to a compiler as in step 4. The target programs it produces run faster than those produced by a commercial Miranda compiler.

More theoretically, a thesis by Dybkj r concerns the use of category theory as a very general framework for designing programming languages [71]. The framework is constructive but extremely slow to implement directly. Dybkj r used exactly the technique above | partial evaluation of machine-produced programs | to obtain substantial speedups and to allow experiments that would not otherwise have been possible.

6.6Exercises

Exercise 6.1 Consider a program p that has one input variable x and assume that x is dynamic.

1.Can partial evaluation optimize p?

2.Now assume that the input to p is known to be a one-digit prime number. Describe how this knowledge can be used to achieve better results from partial evaluation and show the structure of the residual program.

3.Could the weaker knowledge that the input would be prime have been exploited in a similar way?

2

Exercise 6.2 Use the algorithm in Section 6.3.3 to determine the speedup interval

for the program in Figure 4.2.

2

142 E ciency, Speedup, and Optimality

Exercise 6.3

1.Use the algorithm in Section 6.3.3 to determine the speedup interval for the Turing interpreter in Figure 4.4.

2.What Turing programs bring the actual speedups as close to the upper and lower bounds as possible?

2

Exercise 6.4 Theorem 6.1 places an upper bound on the speedup that can be obtained by partial evaluation. State and prove a theorem about the lower bound.

Hint: A `no slowdown' theorem.

2

Exercise 6.5

1.Is Theorem 6.1 valid for the partial evaluator for Scheme0 as presented in Chapter 5? If not, can supplementary restrictions make it valid?

2.Same question, but for the `no slowdown' theorem from Exercise 6.4.

2

Exercise 6.6 Formulate the algorithm in Section 6.3.3 for Scheme0 programs. 2

Exercise 6.7 Find an example program which shows that in De nition 6.2 the condition

8" > 0 : 9k : 8j > k : jp(sj ; dj)j 2 [u , "; v + "]

jpsj (dj )j

is preferable to the simpler

9k : 8j > k : jp(sj; dj )j 2 [u; v]

jpsj (dj)j

2

Exercise 6.8 In Section 6.3.3 it is stated that SU(l1) SU(l2 ) < 1, implies:

SU(l1 ) SU(l) = Cs(l) + Cd(l) SU(l2)

Cd(l)

Prove it.

2

Exercise 6.9 A meta-interpreter mint is a program that takes as input: a speci cation spec for a language S, an S-program p, and input data d. Then mint returns the value of p on input d.

1. Write the de ning equation for mint.

Exercises 143

2.Demonstrate compiler generation using mix, mint and spec.

3.Demonstrate generation of a program mcogen that generates an S-compiler when applied to spec.

		2
Exercise 6.10	Write a self-interpreter sint for the ow chart language (hint: just
remove the code generation parts from mix, and the division input).		2
Exercise 6.11	Annotate this to obtain sintann, assuming the program input is

static and the data input is dynamic. Specialize sintann with respect to a small

source program using the ow chart mix.

2

Exercise 6.12 Is the ow chart mix optimal? Explain your answer, and what is

lacking if it is not optimal.

2

Chapter 7

Online, O ine, and

Self-application

This chapter concerns the de nition, use, and comparison of online and o ine partial evaluation techniques, as described in the next paragraph. All early partial evaluators were online, but o ine techniques seem necessary to allow selfapplication and the generation of program generators (compilers, parser generators, etc.). Both online and o ine partial evaluation are still being actively researched, with no conclusion that either one is the best approach.

The partial evaluators seen heretofore are all o ine as described in Section 4.4.7. This means that they treat their static data in a rather uniform way, based on preprocessing the subject program. The general pattern is that given program p and knowledge of which of its inputs are to be static but not their values, an annotated program pann is constructed (or a division is computed, which amounts to the same thing). Once static data values are available, specialization proceeds by obeying the annotations (e.g. `compute this', `generate code for that'). In e ect pann is a program-generating program, and the static data is its input (just this viewpoint is seen in Chapters 5 and 8).

Even though the static data determines the code that is generated, the particular static values computed during partial evaluation have no e ect on the choice of actions made by the partial evaluator. Thus an expression x+y, in which x, y have been classi ed respectively as static and dynamic, will always generate code to perform the addition at run time, even in circumstances where y has a known constant as value. In contrast, online partial evaluators typically have no preprocessing, make more decisions on the y, and so are better able to exploit computational opportunities such as the one just given.

In the following we shall mostly use the framework and terminology from Chapter 5, but the content of this chapter applies equally well to other languages.

144

Decision making as a prephase? 145

7.1Decision making as a prephase?

A partial evaluator typically has to choose an action in the following situations:

1.For each operator (+, if, . . . ), should/can the operator be reduced at partial evaluation time or should residual code be generated?

2.For each variable/parameter at each program point, should/can it be considered static or should it be dynamic?

3.For each function call/jump should it be unfolded/compressed or should it be residualized?

All o ine specializers (to our knowledge) rely on a prephase (see Figure 7.1), including binding-time analysis and possibly other analyses, to resolve the problem of choosing the proper actions independently of the concrete static values. (An exception which we will not discuss here is by Gl•uck [98].) Not shown in the gure is the postphase, often used by both online and o ine specializers to perform lastminute reductions, unfoldings, or other transformations.

Chapters 4 & 5 presented typical o ine program specializers. Static and dynamic computations were distinguished by a division or by program annotations constructed independently of the concrete values. Transition compression (Section 4.4.4) was applied everywhere except in the branches of a dynamic conditional statement (dynamic by the division, that is). In Section 5.5 a similar o ine unfolding strategy was proposed for Scheme0. Section 5.5.6 suggested a hybrid strategy. The o ine part: a call was annotated as `de nitely dynamic' (calld) if it appeared in a branch of a dynamic conditional or if it had a duplicable, non-variable, dynamic actual parameter. The online part: for calls annotated `perhaps static' (calls) it was tested during specialization whether all duplicable, dynamic parameters would by bound to variables by a possible unfolding. If so, the unfolding would be performed.

Many partial evaluators use a combination of online and o line techniques. Almost all specializers called `o ine' (including those in the previous chapters; Chapter 8 presents an exception) use an online technique to ensure that multiple appearances of the same specialized program point share residual code. Concretely, the manipulation of the sets pending and marked involves comparison of values, and the choice of action depends on the outcome.

7.2Online and o ine expression reduction

In this section we compare the reduction of expressions as performed by online and o ine specializers. We compare typical online and o ine reduction algorithms and give examples of the advantages of the respective methods. The o ine expression

Values of the static inputs

146 Online, O ine, and Self-application

Online partial evaluation is (usually) a one-phase process: p? = in1

SPEC-ON

Values are consulted during specialization

to avoid: violations of congruence,

$

??

code duplication, nontermination, etc.

p'in1

&%

O ine partial evaluation is (usually) a two-phase process:

p Which inputs will be static?

? =

binding-time separation for whole program p

PRE

Program analyses (e.g. control ow analysis)

Annotate to avoid: violations of congruence,

??

code duplication, nontermination, etc.

ann

p

in1

Values of the static inputs

?

The specializer just obeys the annotations:

SPEC-OFF

- compute static values, and

- generate code for dynamic expressions

??

p '$

in1

&%

Figure 7.1: Structure of online and o ine partial evaluators.

reducer, OffPE, takes an annotated expression (two-level Scheme0, Figure 5.5) as input and is in essence identical to the reduce-function de ned in Section 5.4.2. The online expression reducer, OnPE, takes a plain Scheme0 expression as input and reduces it as much as possible.

In OffPE both values and residual expressions are represented as Scheme lists. There is no risk of confusion since the annotated syntax, as opposed to inspection of generated values/expressions, controls the actions of OffPE. This does not hold

Online and o ine expression reduction 147

for OnPE: it is impossible to tell whether the three-element list (+ x y) represents an expression to be reduced or a nal value (which could occur if the program to be specialized was a symbolic equation solver). The solution is to introduce coding or tagging of the data manipulated by OnPE such that the tag distinguishes between values and expressions.

Figure 7.2 shows the functions OnPE and OffPE. For clarity, the specializers are written using syntactic sugar, so to be self-applied they would have to be translated into Scheme0. We use case-expressions with simple pattern matching, double brackets [[ ]] around syntactic objects, and sum injections inVal(. . . ) and inExp(. . . ) as in Section 2.2.3 to tag values and expressions as such in the sum domain On-Value.

The auxiliary function build-cst constructs a residual constant expression from a value (`adds a quote'). The functions build-car, build-cons, etc., construct compound residual expressions, and the functions car, cons, etc., perform the usual computations on ordinary values. Below are the domains of values used in OnPE and OffPE. Again, note that input expressions to OffPE are annotated and that the values computed by OnPE are tagged:

Expression	=	Scheme0 expressions (Figure 5.1)
2Expression	=	Two-level Scheme0 expressions (Figure 5.5)
On-Value	=	inVal Value + inExp Expression
Off-Value	=	Value [ Expression
On-Env	= Var ! On-Value
Off-Env	=	Var ! Off-Value

Now consult Figure 7.2 to see the fundamental di erence: OnPE chooses its action on the basis of input syntax and computed values, OffPE only examines input syntax.

7.2.1Advantages of online methods

The main advantages of online over o ine methods stem from their non-approxi- mative distinction between static and dynamic calues.

A safe (o ine) binding-time analysis always produces a congruent division, ensuring that there is su cient information to do static computations. Binding-time improvements allow improvements in binding-time separation as in Chapter 12, but BTA still has to do a `worst-case' analysis before the static input is given. For computability reasons it will inevitably classify some expressions as dynamic even though they may sometimes assume values computable by the specializer.

Online partial evaluators have more information available to inspect for staticness during specialization, to exploit for better binding-time determination. Online partial evaluators can thus perform some static computations which o ine strategies would rule dynamic. Below we shall show a couple of examples (for more see

148 Online, O ine, and Self-application

Online expression reduction:

OnPE: Expression ! On-Env ! On-Value

OnPE[[x]] = lookup [[x]] OnPE[[car e]] = case (OnPE[[e]] ) of

inVal(val): inVal(car val) inExp(re): inExp(build-car re)

OnPE[[cons e1 e2]] =

case (OnPE[[e1]] ),(OnPE[[e2]] ) of inVal(v1),inVal(v2) : inVal(cons v1 v2)

inVal(v1),inExp(re2) : inExp(build-cons (build-cst v1) re2) inExp(re1),inVal(v2) : inExp(build-cons re1 (build-cst v2)) inExp(re1),inExp(re2): inExp(build-cons re1 re2)

OnPE[[if e1 e2 e3]] = case (OnPE[[e1]] ) of

inVal(true) : (OnPE[[e2]] ) inVal(false): (OnPE[[e3]] )

inExp(re1): (build-if re1 (resid(OnPE[[e2]] ))(resid(OnPE[[e3]] )))

resid pv = case pv of

inVal(v) : build-cst v inExp(re): re

O ine expression reduction:

OffPE: 2Expression ! Off-Env ! Off-Value

OffPE[[x]]			= lookup [[x]]
OffPE[[card e]]			= build-car (OffPE[[e]] )
OffPE[[cars e]]			= car (OffPE[[e]] )
OffPE[[consd e1		e2]]	= build-cons (OffPE[[e1]] ) (OffPE[[e2]] )
OffPE[[conss e1		e2]]	= cons (OffPE[[e1]] ) (OffPE[[e2]] )
OffPE[[ifd e1	e2 e3]] = build-if(OffPE[[e1]] )(OffPE[[e2]] ) (OffPE[[e3]] )
OffPE[[ifs e1	e2	e3]] = if(OffPE[[e1]] )(OffPE[[e2]] )(OffPE[[e3]] )

Figure 7.2: Fragments of online and o ine partial evaluators

Ruf and Weise [230]).

Greater opportunities for static computation correspondingly increase the risk of non-termination or useless specialization. Examples are given in the literature, explaining the sometimes conservative and usually complex online methods used to avoid in nite unfolding. This should not be held against the online approach, because solution of these problems using an approximative BTA can be even more

Online and o ine expression reduction 149

conservative. The real solution appears to be more powerful program analyses which, although exploited at di erent times, can improve the results of both online and o ine partial evaluators.

Conditionals with mixed binding times

With monovariant BTA an expression must be classi ed as `always dynamic' or `always static'. This can lead to undesired generalization if, say, a function is sometimes called with static and sometimes with dynamic arguments. A polyvariant BTA can often handle this particular problem for o ine methods, but other instances of mixed binding times are harder to deal with.

Consider a conditional expression e = (if e1 e2 e3) where e1 and e2 are static and e3 is dynamic. BTA must classify e as dynamic but an online test would discover that e is static if e1 evaluates to true. If expression e was the argument to a function f, an online partial evaluator could apply the function whenever e1 was true, but it would take more than just polyvariance to make an o ine specializer do that.

In the expression (f (if e1 e2 e3)), polyvariant analysis of function f is of no use because the argument is ruled dynamic by BTA. A transformation to (if e1 (f e2) (f e3)) with subsequent polyvariant analysis would solve the problem. Another possibility is to convert the program to continuation passing style [56].

Static knowledge about `dynamic' conditionals/calls

Consider a conditional expression e = (if e1 e2 e3) and assume that e1 is dynamic. Hence the conditional is dynamic and must appear in the residual program. In general, neither o ine nor online specializers can infer any static information about the result of the dynamic conditional, but online methods can do this in a special case: when both e2 and e3 are static and have common characteristics. The extreme case where e2 and e3 have the same value is perhaps uncommon, but the values may have a common structure [230,281]. For example, suppose an interpreter for a language with dynamic typing is to be specialized with respect to a well-typed source program. Tagged values are pairs of type tags and `raw' values, dynamic choices between tagged values with identical tags are not uncommon. An o ine specializer cannot detect this in general because the equality of the tags depends on the well-typedness of the source program.

Very similar remarks apply to dynamic function calls. It can be possible to infer static information about the return value of a function call even though the call is dynamic. In an interpreter for an imperative language with recursive procedures, it could be that the evaluation function for recursive calls should not be unfolded for termination reasons. Still, it is very likely that the return value, an updated store, would have the same structure (an array, an association list, etc.) for all possible dynamic inputs. This would be easier to detect in an online specializer.

For o ine specializers the pattern is the usual one: there exist binding-time improvements to reclaim some of the lost territory. For an example of tag elimination

150 Online, O ine, and Self-application

by o ine partial evaluation, see Consel and Danvy [57].

Generating optimizing compilers

Section 7.3 gives detailed reasoning why o ine methods lead to e cient self-appli- cation, and reading that section might help to clarify the claims below.

The introduction of o ine methods made it possible to self-apply partial evaluators, and compiler generation has been by far the favourite application for selfapplicable partial evaluators. To our knowledge, the generated compilers seen in the literature have in common the fact that they do not perform compile-time optimizations such as constant folding. This is due to the o ine strategy: prior to compiler generation by self-application all interpreter actions are classi ed as either compile-time (= static) or run-time (= dynamic). The classi cation is done at compiler generation time and is thus source program independent. This contradicts the idea of constant folding which is to evaluate expressions which are variable independent, a property which holds for some source programs and not for others.

Switching to pure online techniques is no real solution because compilers generated by self-application of an online specializer are large and slow. We believe that the solution is to nd a compromise between o ine and online methods, as suggested by,for example, Bondorf [26]. Ruf and Weise [230] have taken a step in another direction and used a strong and large online specializer to specialize a weaker and simpler online specializer with respect to an interpreter thus obtaining compiler generation [230].

7.2.2Advantages of o ine methods

O ine partial evaluation was invented in 1984 and made self-application of partial evaluators feasible in practice [135]. It was realized as early as 1971 that it would in principle be possible to generate compilers by self-application, but all computer experiments achieved little apart from using enormous amounts of memory and disk space. Section 7.3 shows in detail why the o ine technique leads to compact and e cient compilers; here we will review other advantages of o ine partial evaluation.

Problem factorization

The component of an o ine partial evaluator that performs the reduction of the annotated program (= function OffPE in Figure 7.2) is often called the specialization kernel. The other principal component in an o ine partial evaluator is the BTA. The splitting of partial evaluation into two separate phases has proven helpful in both the design and implementation phases of several partial evaluation projects. (Section 7.4 presents a recipe which has been successfully followed a number of times.)

Much research in the eld has been concentrated on the phases one at a time,