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

Call unfolding on the y 121

The parameters to f are the free variables of (ifd . . . ). The inserted calls are annotated as dynamic to appear in the residual program and all other calls are unfolded. This strategy is a slight variant of the compression strategy of Chapter 4 and the Scheme0 strategy of Section 5.5.1 and its termination properties are the same: unfolding will loop in nitely only if the subject program contains an in nite static loop.

The `moving' of the cut points for unfolding to the dynamic conditionals has reduced code duplication in many practical applications. For an example, suppose that function f has a static parameter x (possible values 2 and 3) and dynamic parameter y.

(define (f x y) (+d (*s x x) (ifd (=d y 0) 1 (calld g y))))

The Scheme0 strategy would duplicate the conditional and deliver specialized functions

(define (f-2 y) (+ 4 (if (= y 0) 1 (call g y)))) (define (f-3 y) (+ 9 (if (= y 0) 1 (call g y))))

Instead we could introduce a new function h and transform the subject program into:

(define (f x y) (+d (*s x x) (calld h y))) (define (h y) (ifd (=d y 0) 1 (calls g y)))

which partially evaluates to:

(define (f-2 y) (+ 4 (call h y))) (define (f-3 y) (+ 9 (call h y)))

where the conditional is not duplicated.

The compression strategy from Chapter 4 has a tendency to duplicate conditionals since the cut points for unfolding are in the branches instead of before the conditional. See for example the residual program in Figure 4.5.

5.5.5Harmless duplication

Consider unfolding a call (calls (f (. . . ) (. . .ej . . . ))) where ej is duplicable. The duplication is harmless if the reduced form ej0 of ej is just a variable. Substituting one variable for another will make the resulting expression neither larger nor more expensive to evaluate. Thus before annotating the calls, we would like to detect when ej0 must be a variable. Unfortunately, we can detect only when it cannot be a variable.

Let ej be a dynamic expression. If ej is not a variable, then its reduced form ej0 will also not be a variable. When ej is a variable w, then ej0 is not necessarily a variable, since w may be bound (by an unfolded call) to a non-variable dynamic expression:

122 Partial Evaluation for a First-Order Functional Language

(define (f () (v)) (calls g () ((consd v v)))) (define (g () (w)) (calls h () (w)))

(define (h () (z)) (consd z z))

Here w will be bound to the residual expression (consd v v); unfolding the call to h would duplicate that expression.

Before annotating a call we cannot detect when ej must reduce to a variable. However, during specialization we can easily detect whether the reduced form of ej is a variable. This suggests a call unfolding strategy which does not require insertion of lets, and which works in two stages: during annotation, and during specialization.

5.5.6A two-stage call unfolding strategy

When annotating the program, we count the occurrences of dynamic variables, then annotate function calls as follows. A call is made static (calls) if it has no dynamic arguments, or if it is not in a branch of a dynamic conditional and all its duplicable dynamic arguments are variables. The call is made dynamic (calld) in all other cases, that is, if it has a dynamic argument, and either appears in a branch of a dynamic conditional or has a duplicable non-variable dynamic argument.

When specializing the program, a dynamic call will never be unfolded. This is su cient to avoid in nite unfolding (disregarding in nite static loops). To avoid code duplication, a static call may be unfolded if all of its duplicable dynamic argument expressions reduce to variables. For a static call without dynamic arguments this requirement is trivially satis ed, so it will always be unfolded.

Note that the meaning of static call has changed: a static call will possibly but not necessarily be unfolded. The two-stage call unfolding strategy therefore requires a change to the reduce function in the specializer. The calls case must check that each dynamic argument expression either is not duplicable or reduces to a variable. The necessary changes are shown in Figure 5.9. Note that this unfolding strategy, as opposed to those presented previously, is partially but not exclusively steered by the annotations. Thus the strategy combines online and o ine techniques (see Section 4.4.7 and Chapter 7).

5.6Implementation

An implementation of the Scheme0 specializer using the ideas described so far in this chapter is given in Appendix A. The implementation includes monovariant and polyvariant binding-time analysis, annotation, and the specializer.

The implementation can be obtained electronically (via the Internet) by anonymous ftp from ftp.diku.dk as le pub/diku/dists/jones-book/Scheme0.tar.Z.

Using type rules for binding-time checking 123

case e of

.

.

.

Figure 5.9: On the y call unfolding with online `variable test'.

On a Unix system, proceed as follows:

1.Type `ftp ftp.diku.dk' on your terminal.

2.In response to `Name (freja.diku.dk:...):', type `ftp'

3.In response to `Password:', type your own e-mail address.

4.Type `binary'

5.Type `cd pub/diku/dists/jones-book'

6.Type `get Scheme0.tar.Z' to get the packed Scheme0 les.

7.Type `bye' to terminate the ftp session.

8.Type `zcat Scheme0.tar.Z j tar xf -' to unpack the les.

5.7Using type rules for binding-time checking

Section 5.2 presented binding-time analysis as an interpretation of the subject program over the abstract value domain fS,Dg. This section applies the notion of type inference rules (see Section 2.2.2) to annotated (two-level) Scheme0 expressions. The type inference rules can immediately be used for checking the correctness of binding-time annotations. In Chapter 8 we show how to use such rules for inferring binding-time annotations. Type inference methods can pro tably be used for binding-time analysis, especially for languages such as the lambda calculus which are more powerful than Scheme0.

The set of binding-time checking rules for two-level Scheme0 are shown in Figure 5.10. The judgement ` e : t asserts that the annotations of expression e are consistent and that its binding time is t, given that the variables in e have the binding times determined by environment .

124 Partial Evaluation for a First-Order Functional Language

In a judgement ` e : t, the parameter is a binding-time environment, e is a two-level Scheme0 expression, and t 2 fS; Dg is the binding time of e in binding-time environment .

` c : S

[x 7!t] ` x : t

` e1 : S . . . ` ea : S

` (ops e1 . . . ea) : S

` e1 : D . . . ` ea : D

` (opd e1 . . . ea) : D

` e1 : S ` e2 : t ` e3 : t

` (ifs e1 e2 e3) : t

` e : S

` (lift e) : D

Figure 5.10: Binding-time checking rules for annotated Scheme0.

The rules can be read as follows. A constant c is static in any binding-time environment. Variable x has binding time t if the environment maps x to t. An application of a static base function ops must have static arguments and its result is static. An application of a dynamic base function opd must have dynamic arguments and its result is dynamic. A static conditional ifs must have a staticrst argument e1, its branches must both have the same binding time t, and this is the binding time of the result. A dynamic conditional ifd must have all three subexpressions dynamic, and its result is dynamic. The result of a function call without dynamic arguments is static. The result of a function call with dynamic arguments is dynamic. Finally, if the result of expression e is static, then the result of (lift e) is dynamic.

An annotated Scheme0 program (def1 . . . defn) is checked by checking each function de nition defi as follows. Assume the de nition has the form:

Constructing the generating extension 125

(define (f (x1 . . . xm) (xm+1 . . . xa)) e)

The two parameter lists show that the relevant binding-time environment is = [x1 7!S; . . . ; xm 7!S; xm+1 7!D; . . . ; xa 7!D]. Then we must check that ` e : t, where t = S if the function has no dynamic arguments (that is, if m = a), and t = D if it has a dynamic argument (that is, if m < a).

Together with the well-formedness requirements on two-level Scheme0 programs, this su ces to ensure binding-time safety. If the annotated subject program is correct with respect to these rules, the specializer will not fail: it will never attempt to add one to a residual expression, or mistake a value (such as a data structure) for an expression. However, the specializer may well loop, attempting to produce an in nite residual program or unfolding a function in nitely often. Handling thisniteness aspect of specializer safety is addressed in Chapter 14.

5.8Constructing the generating extension

Let a Scheme0 program pgm be given, and let pgma be a two-level (annotated) version of pgm, the rst parameter of which is static, and the second one dynamic. A generating extension of pgma is a program pgmgen for which

[[[[pgmgen]] in1 ]] in2 = [[pgm]] [in1, in2]

for all inputs in1 and in2. That is, the result of applying pgmgen to an argument in1 is a version of pgm specialized to the value in1 of its rst argument.

As seen in Section 1.5.3, the program pgmgen can be generated by cogen or mix:

pgmgen = [[cogen]] pgma = [[mix]] [mix, pgma]

Sergei Romanenko noticed that the machine-generated cogen contains a rather natural function gex, shown in Figure 5.11, which transforms the two-level Scheme0 expressions of pgma into the Scheme0 expressions in pgmgen [227, p. 460].

Holst and Launchbury suggest that for strongly typed languages, it is easier to hand-code cogen (including gex) than to generate it by partial evaluation, because types make self-application more complicated (see Section 11.7 and [69,169]).

5.9Exercises

Exercise 5.1 Specialize the Scheme0 function power with x dynamic and n static:

(define (power x n) (if (= n 0)

1

(* x (power x (- n 1)))))

De ning and measuring speedup 129

6.1.2A range of examples

Specialization is advantageous if sus(d) > 1 for all s and d, and if d changes more frequently than s. To exploit it, each time s changes one may construct a new specialized ps. This will be faster than p, and may be run on various d until s changes again.

If s and d both change frequently, the time to do specialization must also be accounted for. Partial evaluation will be advantageous in a single run if

tmix(p; s) + tps (d) < tp(s; d)

A correct analogy is that compilation plus target run time can be faster than interpretation in Lisp:

tcompiler(source) + ttarget (d) < tinterpreter(source; d)

We investigate the growth of sus(d) as a function of d, for various values of s. The speedup function is often nearly independent of s; for instance speedups resulting from specializing an interpreter p to various source programs s are not strongly dependent on s. On the other hand, some algorithms, e.g. pattern matching programs, have a speedup strongly dependent on s.

Change of algorithm

Spectacular speedups can be achieved by changing p's computational method. Theeld of program transformation [43] has many examples; a typical example is to optimize the Fibonacci function by memoizing, decreasing its computation time from exponential to linear (or even logarithmic).

Use of non-uniform methods seems not to be in the spirit of full automation; it is more like arti cial intelligence. In practice, program transformation systems are not yet as fully automated as partial evaluators.

This achieves no speedup: tp(s; d) =: tps (d) so in the limit sus(d) approaches 1 for each s. (This holds even if we take into account the time to specialize p to s since this is independent of dynamic inputs.)

Additive running times

Suppose p's running time is an additive function of static and dynamic input sizes: tp(s; d) = f(jsj) + g(jdj). Then specialization does not help much, even if we assume all static computations can be done at specialization time. The reason is that for any s, unboundedness of g(n) implies