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

Online and o ine expression reduction 151

and this has contributed to a better understanding of central problems in partial evaluation. A specialization kernel can be tested without BTA by supplying suitable annotations manually, and the results of a new BTA can be evaluated by inspecting the annotations it produces.

E ciency

Given recent developments in BTA technology (work by Henglein, see [114] and Chapter 8), the o ine approach BTA + specialization kernel is also more e cient than online. The reason is obvious by inspection of Figure 7.2: for each reduction or code generation step OnPE does twice as much testing as OffPE in addition to the overhead introduced by tagging all values.

Fast multistage specialization

Specializing the specializer can speed up the partial evaluation process. (An analogy: compilation followed by target code execution can be faster than interpretation.) If the specialized specializer is used several times, the gain can be substantial.

Fast multistage specialization follows the scheme below. BTA is the binding-time analyser, SPEC is the annotated specialization kernel.

1.	pann	:=	[[BTA]] p	Preprocessing time
2.	p-gen	:=	[[mix]][ SPEC, pann ]
3.	pin1	:=	[[p-gen]] in1	Specialization time
4.	output	:=	[[pin1]] in2	Run time

The main goal is to make stage 4 fast, i.e. to generate a good specialized program. The second goal is to make stage 3 fast, i.e. to specialize fast. It is not a problem if Stages 1 and 2 are slow, if that speeds up stage 3: the result is slow generation of a good specializer, and the generation is performed only once.

As the table indicates, the automatically generated specializer p-gen contains no preprocessing. A special case is generation of a compiler comp = int-gen from an interpreter int.

Binding-time annotations as a user interface

Explicit binding times in the form of divisions or annotations have been used in several tools that are useful to the user of a partial evaluator. The bindingtime analyser itself can be considered such a tool because the annotations allow the user to see whether the program has the desired binding-time properties. If the analysed program were an interpreter, something is probably rotten if the interpreter's program argument is classi ed as dynamic. This would be much easier to detect by inspection of an annotated interpreter than by inspection of a residual program produced by a partial evaluator.

A re nement of this idea is the binding-time debugger, which is roughly a stepwise binding-time analysis, allowing the user to see more clearly when things `go wrong' [60,196].

152 Online, O ine, and Self-application

Annotated programs can also be used to estimate the feasibility of partial evaluation. One example is the automatic speedup analysis presented in Section 6.3. In Chapter 13 the classes of `oblivious' and `weakly oblivious' programs are de ned in terms of binding-time properties of programs (restrictions on the dynamic conditionals). The class of oblivious programs will be seen to yield compact, linear residual programs.

Program analysis

Binding-time analysis is often combined with other program analyses to satisfy other requirements than just congruence. Typical goals are to achieve niteness, to avoid computation duplication, and to avoid specialization with respect to dead static variables. Though it is natural to combine these analyses with plain bindingtime analysis, they are not all dependent on the availability of binding-time information. An example is liveness analysis, which can be used by online partial evaluators as well. The online partial evaluator then uses the rule: `dead variables are de nitely dynamic and live variables are checked online as usual', which achieves the same bene cial generalization as the o ine partial evaluator without sacri cing the online potential.

On the other hand, some analyses do depend on binding-time information. An example is Holst's poor man's generalization, which is a re nement of liveness analysis: a variable should be generalized if no control decisions depend on its value [116]. This is clearly a combination of liveness and binding-time analysis.

Online partial evaluators often test a large part of the computation history to determine whether the partial evaluator is possibly entering an in nite loop. If a certain `danger criterion' (e.g. a growing parameter in a recursive function) is observed, then an online generalization is performed [235,281]. O ine partial evaluators cannot, by de nition, do this. At best the binding-time analysis can be re ned to classify, in advance, enough variables as dynamic to ensure niteness. This requires a more complicated program analysis (see Chapter 14).

In general, the use of various program analyses is much more widespread in the o ine than in the online community. This must be so by de nition for certain kinds of analyses (BTA, poor man's generalization [116]), but the di erences in culture seem to matter too. We feel that there is good use for program analysis in online partial evaluators.

7.2.3Which `line' is better?

Clearly, it is impossible to say which is best: online or o ine partial evaluation. Above we listed a number of advantages of the respective methods, but it depends greatly on the concrete problem to solve by partial evaluation how the advantages should be weighted. It would be hard to make general statements about this, and it would be more fruitful to study how the two schools of partial evaluation can

BTA and the taming of self-application 153

learn from each other.

A compromise strategy, mixline partial evaluation, results from augmenting the usual binding-time domain, fS,Dg, with a third binding time M . Now S should be interpreted as `always static' as usual, D should mean `always dynamic' as opposed to the usual `sometimes dynamic', and the new binding time M means `mixed binding times' to be tested online. This idea is not new (e.g. [26,53]), but large scale experiments have not been reported.

As brie y mentioned above we feel that many of the program analyses often used in o ine partial evaluators would also be useful in the online world. Examples include: liveness, duplication, control ow, and termination.

7.3BTA and the taming of self-application

In this section we argue that it is no accident that only o ine specializers have been successfully self-applied. By `successfully' we mean that the resulting program generators (typically compilers) have been reasonably small and e cient. Selfapplication of online specializers is of course possible in principle, but all such experiments have yielded large and slow program generators. For example, Lars Ole Andersen changed the o ine partial evaluator described in [136] into being online. The generated compilers then became around 2 to 3 times larger in code size and 2 to 6 times slower.

In this section we make a case study of compilation and compiler generation by online partial evaluation. We nd that result of compiler generation is not satisfactory and show how o ine partial evaluation provides a simple solution.

7.3.1Compilation by online partial evaluation

Let us compile program source by computing target = [[mix]]L [int, source] , where int interprets an imperative language. We use the online partial evaluator OnPE as our mix-program. Assume that the following expression appears in the interpreter int:

E = (cons (car names) (car values))

The role of this part of the interpreter is to bind a source program name to its run time value, where names and values are interpreter variables: names is a list of variable names from source and values is a list of values bound to these. The important thing to note is that names and values have di erent binding times. The value of names can be computed given source alone, but the value of values cannot.

At specialization time the symbolic environment in the OnPE may bind the interpreter's variable names to the On-Value inVal((a b c)), say, and the inter-

(lookupnames

154 Online, O ine, and Self-application

preter's variable values to the On-Value inExp(exp), where exp is some residual expression. Here a, b, and c correspond to variable names from the interpreted program source.

The value of OnPE[[E]] is the specialized version of the interpreter fragment E = (cons (car names) (car values)). In concrete residual syntax this could be written:

(cons (quote a) (car exp))

7.3.2Self-application of an online partial evaluator

By the second Futamura projection, mixint = [[mix]]L [mix,int] is a compiler from the language interpreted by int into L. We shall consider operationally what happens when we apply the program specializer mix to itself in this manner, with int being the interpreter discussed above.

Consider again the expression E = (cons (car names) (car values)). This expression is part of int, and function OnPE in mix deals with expressions, so the compiler mixint contains the result of specializing the function OnPE with respect to E. This compiler fragment is shown in Figure 7.31. Compare this specialized OnPE with the original OnPE shown in Figure 7.2. The dispatch on the input expression syntax has been reduced away by the program specialization, but the case-expressions testing for staticness have completely dynamic arguments and hence they appear in the specialized OnPE.

We make two observations on this compiler. The rst observation is the lack of distinction between binding times. The compiler treats all parts of the expression from the interpreter alike, although some parts are always `compile time' and others always `run time'. This behaviour is inherited from the online mix program, which handles both static and dynamic expressions by the OnPE function. This function can return both values and residual expressions, injected into the domain On-Value: values (inVal(. . . )) for static arguments and residual expressions (inExp(. . . )) for dynamic arguments. However, in the running compiler, the value of lookupnames will actually always have the form inVal(v). Hence (reduce-car

)) will always evaluate to a constant value inVal(. . . ). This can be inferred at compiler generation time | and that is precisely the goal of using explicit binding-time information.

The second observation concerns excessive generality. The compiler fragment above can be used to specialize int in at least two ways. First, it can generate the usual target program target when given a source program but not the source program's input. Second, it could generate a strange `target' program crazy when given as static data the input data to the source program, but not the source

1Many immaterial details, e.g. unfolding strategy, are left unspeci ed about the online partial evaluator used here. For readability, we have introduced two functions reduce-car and reduce-cons in the generated compiler.

BTA and the taming of self-application 155

OnPE(cons (car names) (car values)): On-Env ! On-Value

OnPE(cons (car names) (car values)) =

reduce-cons (reduce-car (lookupnames )) (reduce-car (lookupvalues ))

reduce-car: On-Value ! On-Value reduce-car pv =

case pv of

inVal(v): inVal(car v) inExp(e): inExp(build-car(e))

reduce-cons: On-Value ! On-Value ! On-Value reduce-cons pv1 pv2 =

case pv1,pv2 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)

Figure 7.3: A fragment of an overly general compiler.

program itself! The resulting program would take a source program and produce the result of running the source program on the given input data:

[[crazy]]L source = [[int]]L [source,data] = [[source]]S data = output

This compiler feature is a very useless one. Conclusion: the compiler mixint is much more general than necessary.

The generality of the compiler mixint is due to the lack of distinction between interpreter actions traditionally done at compile time (syntax analysis, environment manipulation, etc.) and those traditionally done at run time (evaluating source program expressions, etc.). Each time mix meets a cons operator, for example, it will decide online whether it is doing a compile time action or a run time action, and the compiler generated from the online mix inherits this behaviour.

To get the e ciency of traditional compilation, the expression (car names) in the interpreter fragment should be evaluated directly by the compiler since this is an instance of environment manipulation. On the other hand, residual code for (car values) should be generated directly by the compiler. In neither case should it bother to check whether or not the values are constant.

mix2 mix2

156 Online, O ine, and Self-application

7.3.3Removing generality by annotations

Below mix1 and mix2 may or may not be identical. The indexes are introduced for easier reference only.

During compiler generation

comp = [[mix1 ]]L [mix2,int]

is partially evaluated with respect to incomplete input, int. Recall that constantly tests whether the partial values are constants inVal(...) or residual expressions inExp(...), and that these tests are dynamic and appear in the generated compiler. This is intuitively wrong because it should be known at compiler generation time that the syntactic dispatch in the interpreter will be static at compilation time. To make these tests static in mix2 , extra information must be supplied because there is no way a priory that mix2 can infer that comp should

produce only normal target programs and no crazy programs as shown above. The interpreter int has two arguments, source and data, and mix2 must know

that the compiler is only intended for application to source. One convenient way to communicate this information to mix2 is to annotate the actions of int as either static or dynamic. This makes the binding times of int apparent as syntax,2 and the syntactic dispatch in mix2 is certainly reduced by mix1 .

The claim is thus that mix2 should be an o ine partial evaluator and that accordingly int should be annotated. In the annotated interpreter, intann, the annotated version of the subexpression E considered above, would be:

(consd (lift (cars names)) (card values))

Recall from the beginning of Section 7.2 that the Off-Values handled by OffPE are untagged. It is the correctness of the annotations ensures that lookup returns a constant value when applied to names and a residual expression when applied to names.

Let offmix be an o ine partial evaluator which uses OffPE to reduce expressions. Consider generation of a compiler from the annotated interpreter intann by

computing [[offmix]] [offmixann,intann] . The decisions in offmixann whether

L

to do evaluation or to generate code will not depend on offmixann's unavailable

input (the source program source), but only on the annotations in the interpreter. Thus the decision can be made when the compiler is generated and need not be made anew every time the compiler is applied to a source program.

A fragment of the compiler is given in Figure 7.4. We see that it simply generates code, as expected of a compiler. It does not contain any tests on residual expressions as did the corresponding fragment of the mix-generated compiler in Figure 7.3; it is de nitely shorter and quite a lot faster. So the use of binding-time annotations is indeed be very bene cial.

2Equipping the interpreter with an explicit division for each function would have the same e ect.

			A recipe for self-application 157
OffPE(cons (car	names)	(car	values)): 2Environment ! Exp
OffPE(cons (car	names)	(car	values)) =

build-cons(build-cst(car(lookupnames )))(build-car(lookupvalues ))

Figure 7.4: A fragment of a compiler generated by o ine partial evaluation.

One might note that OffPE does not always produce exactly the same residual expressions as OnPE does. Given another interpreter fragment, OffPE might produce a residual expression such as (build-+ (build-cst 1) (build-cst 2)) | if the

+ expression leading to this were a run time action according to the annotations. The function OnPE would reduce this to (build-cst 3), but the experiments performed so far have shown that this rarely occurs when OffPE is used for compiling. Furthermore, since most operations in an interpreter are compile time actions, extending OffPE by adding reductions on dynamic data would not increase the size (or decrease the speed) of the compiler dramatically, and it would then give the same result as OnPE, as also mentioned in Section 7.2.3.

Compiler generation is just one application where binding-time information gives a speedup in self-application. The essential point is that self-application stages programs. Self-application is analogous to applying cogen. Annotations attached to a program expression contain information on how to stage the expression: when the annotation says `static', cogen produces a program piece which, when executed, evaluates the expression. When the annotation says `dynamic', cogen produces an expression which, when executed, generates residual code.

7.4A recipe for self-application

Constructing a self-applicable partial evaluator for a new language is a tricky task and one that may require several iterations, both to re ne the subject language and to develop methods su cient to specialize it well. Following is a pattern that we have found to work well in practice, using o ine specialization. There are, however, always unexpected complications for each new language.

The recipe suggests that a self-interpreter is written as the rst programming step. We rst explain why this starting point is so very appropriate for constructing program generators by the second Futamura projection:

p-gen = [[ mix]] mix p

The reasoning, well supported by practical experience, is as follows.

Getting [[ mix]] mix p to give good results, or any at all, is very tricky.

Advice by Polya: to solve a hard problem, rst solve a similar but simpler problem. Then generalize the simpler problem's solution.

158Online, O ine, and Self-application

Related observation: in order to be able to perform its static computations, a non-trivial mix must contain a self-interpreter. Call this sint.

Thus a simple problem similar to obtaining p-gen = [[ mix]] mix p is to compute

p0 = [[ mix]] sint p

An good solution to this problem is the `optimality' criterion of Section 6.4, that p0 should essentially be identical to p. If one cannot at least make p0 very similar to p, an e cient [[ mix]] mix p will be hard or impossible to construct.

The recipe

1.Think carefully through general questions, particularly:

What is known data, and what is unknown?

Can each variable be thought of as completely static or completely dynamic, or are partially static and dynamic values needed?

What is a specialized program point?

2.Write a clean self-interpreter sint, perhaps for a small subset of the language.

3.Use ad hoc hand methods to see how it could be specialized to some very simple program p.

4.Devise a set of annotations, such as the s/d annotations used in Chapter 5 or the underlines from Chapter 8. These give extra information attached to parts of a subject program, so specialization can be done as follows:

do (perform, evaluate, execute) those parts annotated as mix-time (e.g. evaluate static expressions, unfold function calls, etc.);

generate code for those parts annotated as run-time.

5.See whether you can annotate the program p of step 3 and get the right specialized program (again by hand).

6.Annotate the self-interpreter.

7.Program a specializer to behave as in step 4, not necessarily written in the same language.

8.Use it to specialize the annotated self-interpreter to various simple programs; and then to itself. If the optimality criterion is not violated too much, all the hardest hurdles have been cleared.

Exercises 159

9.Program a specializer to behave as in step 4, in the language being specialized.

10.Introspect on the way the annotations were added, and devise a way to do as much as possible of it by machine.

11.Try [[ mix]] mix p for various p.

Warning: high-level control constructs such as while loops, pattern matching, and some deeply nested constructions can give problems. It is important to cut the language down to the bare bones before beginning, otherwise much time will be wasted on problems that distract attention from the hard central core of the exercise, especially steps 2 to 6. In our experience, many of these problems are easily cleared up in retrospect after the core is working, and many more can be dealt with by liberal usage of `syntactic sugaring' and `desugaring', done using the computer to translate into and out of a rudimentary core language.

Final Comment. This approach provides a very convenient factorization of the problem:

1.What should the annotations be? This is a problem of expressiveness | they must contain su cient information to be able to do specialization. The solution is often a two-level syntax, e.g. as used in Chapters 4, 5, 8, and in [202] by Nielson and Nielson.

2.How can one nd appropriate annotations? This is a program analysis problem, solvable by abstract interpretation or type inference. Consult the material on binding-time analysis found in this book.

7.5Exercises

Exercise 7.1 Write a simple online partial evaluator for Scheme0. Compare it to the o ine partial evaluator in Chapter 5 in the following areas: quality of residual programs, partial evaluation-time e ciency, termination properties, and unfolding

strategy.

2

Exercise 7.2 Write a simple online partial evaluator for ow charts, as done in Chapter 4. Compare it to the o ine partial evaluator in Chapter 4 in the following areas: quality of residual programs, partial evaluation-time e ciency, termination

properties, unfolding strategy.

2

Exercise 7.3 In Section 7.2.3 mixline, a compromise between o ine and online, is suggested. De ne the domains to be used by a mixline expression reducer and then

de ne the mixline expression reducer itself.

2

160 Online, O ine, and Self-application

Exercise 7.4 Consider the residual program in Figure 4.5. What residual program would be generated by a simple online partial evaluator which reduces and unfolds

whenever possible?

2

Exercise 7.5 A general parser gen-parser is a program that, given a grammar and a character string, returns a parse tree:

parse-tree = [[gen-parser]L grammar char-string

1.Show how to use a partial evaluator mix to generate a parser and a parser generator.

2.Will it make a di erence to the structures of the parser and the parser generator whether mix is o ine or online?

2