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

What is partial evaluation? 71

4.2.2Residual programs and program specialization

De nition 4.1 Let p be an L-program taking as input a two-element list, and let d1 2 D. Then an L-program r is a residual program for p with respect to d1 i

[[p]]L [d1, d2] = [[r]L d2
for all d2 2 D.	2

The equation expresses that running r on d2 yields the same result as running p on both d1 and d2. Intuitively, the input d1 is already incorporated in the residual program r. We now de ne a (correct) program specializer to be a program which given p and d1 yields as result a residual program r, such that the above equation holds.

De nition 4.2 An L-program mix is a program specializer i for every p, d1 2 D, the program r = [[p]]L d1 is a residual L-program for p with respect to d1. Expressed symbolically we get the mix equation:

[[p]]L [d1, d2] = [[([[mix]]L [p, d1] )]]L d2
for all d2 2 D.	2

The program p is called the subject program. Note that the right hand side of the mix equation involves two program executions. First, a residual program r = [mix]]L [p, d1] is generated. Second, the residual program r is run on data d2.

The equations can be generalized to the situation where p takes a xed number n pieces of input data, of which m are given to the program specializer, 0 m n. In the equations above, n = 2 and m = 1.

Example 4.1 Consider the program fragment in Figure 4.2. It might occur inside an interpreter which represents the runtime store of an interpreted program by a list namelist of names of variables, and a parallel list valuelist of their values. The `input data' to the program fragment are the three variables name, namelist, and valuelist, that is, n = 3.

while name =6 hd (namelist) do begin

valuelist := tl (valuelist); namelist := tl (namelist)

end;

value := hd (valuelist);

Figure 4.2: An L-program program fragment to look up a name.

Suppose the program specializer is given the initial values of the variables name and namelist, for example name = z and namelist = (x y z) but that valuelist

72 Partial Evaluation for a Flow Chart Language

is unknown, that is, m = 2. Since the program's control is entirely determined by name and namelist it can be symbolically executed, yielding as a residual program fragment:

valuelist := tl (valuelist); valuelist := tl (valuelist); value := hd (valuelist);

Note that the while-loop has disappeared, and the residual program fragment contains only those commands from the subject program whose e ect can not be computed at program specialization time. Note also that the command

valuelist := tl (valuelist)

appears twice in the residual program, once for each iteration of the loop, even though it appeared only once in the subject program. The two iterations stem from the fact that we had to take tl of namelist twice before its hd was equal to

name.

2

Three remarks in relation to the de nition of program specialization:

Further optimization: Since variable valuelist will not be used after the program fragment, it is tempting to optimize the resulting program to: value := hd (tl (tl (valuelist))). An appropriate technique for doing such transformations is to use `dags' [4]. Since the optimization is not essential to program specialization, we shall not pursue the idea further here.

The existence of residual programs: The general possibility of partially evaluating a program is known as Kleene's s-m-n theorem in recursive function theory. This, however, only states the existence of a residual program; nothing is said about e - ciency. The usual proof of the s-m-n theorem involves generating a trivial residual program such as:

name := 'z; namelist := '(x y z); while name =6 hd(namelist) do begin

valuelist := tl (valuelist); namelist := tl (namelist)

end;

value := hd(valuelist);

This residual program clearly satis es the de ning equation, but it is of no practical interest.

The language of the residual program: Note that the program specializer is assumed to generate residual programs, r, written in the same language as the input program p. This makes it much easier to understand the transformations mix performs as long as the aim is to understand principles and gain experience with

Partial evaluation and compilation 73

program specialization. If the goal were maximal e ciency it would be natural to let mix generate programs in a lower-level language [120].

4.3Partial evaluation and compilation

In this section we rst show by a concrete example that a partial evaluator can be used to compile, given an interpreter and a source program. We then show that this remarkable fact is a simple consequence of the mix equation as presented above and from the de nitions of interpreters and compilers from Section 3.1. This result is known as the rst Futamura projection.

4.3.1An interpreter for Turing machine programs

This section presents a concrete program that will be used to illustrate several points later in the chapter. The program is an interpreter for a Turing machine (Post's variant) with tape alphabet A = f0,1,Bg, where B stands for `blank'. A Turing program Q is a list (I0 I1 . . . In) of instructions each of form

right, left, write a, goto i, or if a goto i

A computational state consists of a current instruction Ii about to be executed, and an in nite tape of squares ai:

. . . a,2 a,1 a0 a1 a2 . . .

Only nitely many of the squares contain symbols ai not equal to B; a0 is called the scanned square. Instruction e ects: write a changes a0 to a, right and left change the scanning point, and if a goto i causes the next control point to be Ii in case a0 = a; in all other cases the next control point is the following instruction (if any).

An example program Q in the Turing language is given in Figure 4.3. The input to this program is a0a1 . . . an 2 f0,1g*, and the initial tape contains B in all other positions, that is, an+1, an+2,. . ., and a,1, a,2,. . . . Program output is the nal value of a0 a1 . . . (at least up to and including the last non{blank symbol) and is produced when there is no next instruction to be executed. Note that a di erent square may be scanned on termination than at the beginning.

0:if 0 goto 3

1:right

2:goto 0

3:write 1

Figure 4.3: A Turing machine program.

74 Partial Evaluation for a Flow Chart Language

The program nds the rst 0 to the right on the initial tape and converts it to 1 (and goes into an in nite loop if none is found). If the input to Q is 110101, the output will be 1101.

The Turing interpreter in Figure 4.4 has a variable Q for the whole Turing program, and the control point is represented via a su x Qtail of Q (the list of instructions remaining to be executed). The tape is represented by variables Left, Right with values in A*, where Right equals a0 a1 a2 . . . (up to and including the last non{blank symbol) and Left similarly represents a,1 a,2 a,3 . . . . Note that the order is reversed.

read (Q, Right);
init:	Qtail := Q;	Left := '();
loop:	if Qtail = '() goto stop else cont;
cont:	Instruction	:=	first		instruction(Qtail);
	Qtail	:=	rest(Qtail);
	Operator	:=	hd(tl(Instruction));

	if Operator = 'right goto do-right else cont1;
cont1:	if Operator = 'left				goto do-left	else cont2;
cont2:	if Operator = 'write goto do-write else cont3;
cont3:	if Operator = 'goto				goto do-goto	else cont4;
cont4:	if Operator = 'if				goto do-if	else error;
do-right: Left		:= cons(firstsym(Right), Left);
	Right	:= tl(Right); goto loop;
do-left:	Right	:= cons(firstsym(Left), Right);
	Left	:= tl(Left); goto loop;
do-write: Symbol		:= hd(tl(tl(Instruction)));
	Right	:= cons(Symbol,tl(Right)); goto loop;
do-goto:	Nextlabel	:= hd(tl(tl(Instruction)));
	Qtail	:= new		tail(Nextlabel, Q); goto loop;
do-if:	Symbol	:= hd(tl(tl(Instruction)));
	Nextlabel	:= hd(tl(tl(tl(tl(Instruction)))));
	if Symbol	= firstsym(Right) goto jump else loop;
jump:	Qtail	:= new		tail(Nextlabel,Q); goto loop;

error: return ('syntax-error: Instruction);

stop: return right;

Figure 4.4: Turing machine interpreter written in L.

The interpreter uses some special base functions. These are new tail, which takes a label lab and the program Q as arguments and returns the part (su x) of the

Partial evaluation and compilation 75

program beginning with label lab; first instruction, which returns the rst instruction from an instruction sequence; and rest, which returns all but the rst instruction from an instruction sequence. Moreover, we need a special version firstsym of hd for which firstsym () = B, and we assume that tl () is ().

Example 4.2 Let Q be (0: if 0 goto 3 1: right 2: goto 0								3: write 1).
Then
[[int]]L [Q, 110101]					=	1101
new		tail(2, Q)			=	(2: goto	0 3: write 1)
first				instruction(Q)	=	(0: if 0	goto 3)
rest(Q)					=	(1: right	2: goto 0 3: write 1)
are some typical values of these auxiliary functions.								2

Time analysis. The Turing interpreter in Figure 4.4 executes between 15 and 28 operations per executed command of Q, where we count one operation for each assignment, goto or base function call.

4.3.2The Futamura projections

Futamura was the rst researcher to realize that self-application of a partial evaluator can in principle achieve compiler generation [92]. Therefore the equations describing compilation, compiler generation, and compiler generation are now called the Futamura projections.

target	=	[[mix]]L [int, source program]
compiler	=	[[mix]]L [mix,	int]
cogen	=	[[mix]]L [mix,	mix]

Although easy to verify, it must be admitted that the intuitive signi cance of these equations is hard to see. In the remainder of this chapter we shall give some example target programs, and a compiler derived from the interpreter just given.

4.3.3Compilation by the rst Futamura projection

In this section we shall show how we can compile programs using only an interpreter and the program specializer. We start by verifying the rst Futamura projection, which states that specializing an interpreter with respect to a source program has the e ect of compiling the source program. Let int be an S-interpreter written in L, let s be an S-program, and d its input data. The equation is proved by:

76 Partial Evaluation for a Flow Chart Language

[[s]]S d =	[[int]]L [s,d]	by the de nition of
		an interpreter
=	[[([mix]]L [int,s] )]L d	by the mix equation
=	[[target]]L d	by naming the residual
		program: target

These equations state nothing about the quality of the target program, but in practice it can be quite good. Figure 4.5 shows a target program generated from the above interpreter (Figure 4.4) and the source program s = (0: if 0 goto 3 1: right 2: goto 0 3: write 1). Here we just present the result; a later section will show how it was obtained.

read (Right); lab0: Left := '();

if '0 = firstsym(Right) goto lab2 else lab1; lab1: Left := cons(firstsym(Right), Left);

Right := tl(Right);

if '0 = firstsym(Right) goto lab2 else lab1; lab2: Right := cons('1, tl(Right));

return(Right);

Figure 4.5: A mix-generated target program.

Notice that the target program is written in the same language as the interpreter; this comes immediately from the mix equation. On the other hand, this target program's structure more closely resembles that of the source program from which it was derived than that of the interpreter. Further, it is composed from bits and pieces of the interpreter, for example Left := cons(firstsym(Right), Left). Some of these are specialized with respect to data from the source program, e.g. if '0 = firstsym(Right) goto lab2 else lab1. This is characteristic of mix- produced target programs.

Time analysis. We see that the target program (Figure 4.5) has a quite natural structure. The main loop in the target program takes 8 operations while the interpreter takes 61 operations to interpret the main loop of the source program, so the target program is nearly 8 times faster than the interpreter when run on this source program.

4.4Program specialization techniques

We now describe basic principles su cient for program specialization; a concrete algorithm will be given in a later section.

Program specialization techniques 77

4.4.1States, program points, and divisions

A computational state at any instant during execution of a program in our simple imperative language is a pair (pp, store), where pp is a program point indicating the current point of control and store contains the current values of all program variables. A store containing the current values of variables X1,. . . ,Xn will be represented by a list of the form (v1 . . . vn). When an assignment is executed, the store is updated and pp reset to the next program point; when a conditional or a goto is executed, only the control point is updated.

Suppose now that only part of the input data is at hand. Then we cannot execute the program but we can specialize it with respect to the known input. In this case the initial and subsequent stores will be incomplete (at specialization time), hence we cannot expect to be able to evaluate at specialization time all expressions in the subject program.

What form should such an incomplete store take? A simple method is to classify every variable independently as static if its values can be determined at program specialization time, and as dynamic if not static. A partial computational state is thus a pair of form (pp, vs), where vs is a list of the values of the static variables, and the values of the dynamic variables are unknown.

Such a static/dynamic classi cation is called a division in [130], where more general versions are also considered. Where the opposite is not explicitly stated, we shall assume throughout this chapter that the same division is valid at all program points. Call such a division uniform. This assumption, which simpli es matters without being essential, often holds in practice although counterexamples may easily be found, e.g., it would be convenient to violate the assumption for a program that swaps two variables, one initially static and the other dynamic.

An essential requirement for use in program specialization is that the division is (uniformly) congruent. This means that in any transition from computational state (pp, store) to (pp0, store0), the values of the static variables at program point pp0 must be computable from the values of the static variables at pp. Expressed concisely: any variable that depends on a dynamic variable must itself be dynamic.

An expression exclusively built from constants and static variables is also called static, while it is called dynamic if it contains a dynamic variable. Suppose that the subject program contains the assignment

X := exp

If exp is dynamic then by the congruence condition X must also be dynamic. Consider the program fragment in Figure 4.2 and assume, as there, that name

and namelist are static, while value and valuelist are dynamic:

78 Partial Evaluation for a Flow Chart Language

while name =6 hd (namelist) do begin

valuelist := tl (valuelist); namelist := tl (namelist)

end;

value := hd (valuelist);

We see that none of the assignments violates the congruence condition.

4.4.2Program point specialization

The idea of program point specialization is to incorporate the values of the static variables into the control point. Suppose that at program specialization time we discover that if the program had been executed normally with all input data supplied, the computation might eventually be in a state with control at point pp and with vs as the values of the static variables. Then the pair (pp, vs) is made a program point in the residual program. The code that (pp, vs) labels in the residual program is an optimized version of the code at pp in the subject program. The potential for optimization is because we know the values of the static variables. As hinted by the examples, this means that a program point pp may appear in several residual versions, each with di erent values of the static variables.

Let us continue the above example. Since we need explicitly named program points, this time we use a desugared version of the program fragment.

search: if name = hd(namelist) goto found else cont; cont: valuelist := tl(valuelist);

namelist := tl(namelist); goto search;

found: value := hd(valuelist);

Assume our task is to specialize this fragment beginning at search, and that initially name is z and namelist is (x y z). Thus initially the value of vs in the specializer is the pair:

vs = (z, (x y z))

Now consider program execution on this initial vs and unknown variables value and valuelist. The list vs can assume three di erent values at search, namely:

(z, (x y z)), (z, (y z)), and (z, (z)). At label cont, vs can assume the tworst of the listed values, and at point found, vs has (z, (z)) as its only value.

De nition 4.3 A specialized program point is a tuple (pp, vs) where pp is a program point from the subject program and vs is a set of values of the static

variables.

2

A specialized program point (pp, vs) represents a set of states of the subject program's computation | all those with control point pp and static variable values

Program specialization techniques 79

vs. In the residual program the value of vs is `built in' to the specialized program point (pp, vs), and not explicit as it is at program specialization time.

De nition 4.4 The set of all specialized program points (pp, vs) that are reach-

able during program execution is called poly.

2

Note that poly thus represents the set of points of control in the residual program; in our example:

poly = f (search,	(z,(x	y z))),(search,(z,(y z))),(search,(z,(z))),
(cont,	(z,(x	y z))),(cont, (z,(y z))),
(found,	(z,(z)))		g

In the next sections we show how to compute poly and how to generate a residual program given poly. We address the latter question rst.

4.4.3Generating code for the various commands

Suppose we are given a specialized program point (pp, vs). In the subject program the label pp is attached to a basic block consisting of a sequence of commands. The generated code for a basic block is the concatenation of the code generated for the commands.

In the following we assume a rich library of basic functions. In particular, suppose exp is an expression and vs is a list of values of the program's static variables. We need two functions: eval(exp, vs), which returns the value of a static expression exp; and reduce(exp, vs), which performs constant folding [4] of static parts of a dynamic expression. If vs, for example, says that b = 2, the expression b b + a can be replaced by 4 + a.

Command		Done at specialization time			Generated code
X :=	exp	reduced		exp := reduce(exp, vs)	X := reduced		exp
(if X is dynamic)
X :=	exp	val		:= eval(exp, vs);
(if X is static)		vs		:= vs[X 7!val]
return exp		reduced		exp := reduce(exp, vs)	return reduced				exp
goto	pp0	goto (pp0, vs)

80 Partial Evaluation for a Flow Chart Language

Code generation for a conditional: if exp goto pp0 else pp00

	Done at specialization time			Generated code
(if exp is dynamic)	reduced		exp := reduce(exp,vs)	if reduced		exp
				goto(pp0,vs)
				else(pp00,vs)
(if exp is static and			val := eval(exp,vs)	goto (pp0, vs)
val = true)
(if exp is static and			val := eval(exp,vs)	goto (pp00,vs)
val = false)

Computing poly

Let pp0 be the rst label in the program and let vs0 be the initial values of the static data. It is clear that (pp0, vs0) should be in poly. Moreover, if any specialized program point (pp, vs) is in poly, all specialized program points reachable from (pp, vs) should be there. That is, poly is the closure of vs0 under the relation `reachable from'.

We now address this more carefully. Consider specialized program point (pp, vs), where pp is attached to a basic block of commands in the subject program: a sequence of assignments ended by a `passing of control'. Some assignments might reassign static variables, thus forcing the entry list of statically known values, vs, to be updated, so a new specialized program point has form (pp', vs'). The set of successors naturally depends on the form of control passage. Let us write successors(pp, vs) for the set of possible successors (it has two elements for a dynamic conditional, none for a return and otherwise one). In the earlier example,

successors(search,(z,	(x	y	z)))	=	f (cont, (z,	(x	y z))) g
successors(search,(z,	(z)))			=	f (found, (z,	(z))) g
successors(cont, (z, (x		y	z)))	=	f (search,(z,	(y	z)))	g

and so on. A rst approximation to the overall structure of mix can now be given (Figure 4.6).

poly := f (pp0, vs0) g;

while poly contains an unmarked (pp, vs) do begin

mark (pp, vs);

generate code for the basic block starting at pp using the values in vs; poly := poly [ successors(pp, vs)

end

Figure 4.6: A simple specialization algorithm.

Rules for computing successors are easily given. If the basic block labelled by pp