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

Conclusion 201

Figure 9.6: Specialization of Prolog goals (part II).

202 Partial Evaluation for Prolog

The speedup gained from compilation by partial evaluation is of the same order as for functional languages, but the speedup from self-application is relatively small. This is because a large part of the operations in the specializer are dynamic at self-application time. The main culprits are the folding of sequences of dynamic uni cations into single uni cations (which, as described above, is a completely dynamic postprocess) and comparison of static values (which is static at partial evaluation time but dynamic at self-application time).

Improving Logimix

In general, Logimix is fairly sensitive to how a program is written. The regular expression example showed one example of this, but the fact that values are not propagated from dynamic goals to static goals also plays a part. As an example, consider the goal (s1,(d,s2)), where s1 and s2 are static subgoals and d is a dynamic subgoal. The binding of static variables in s1 are propagated to the second subgoal (d,s2), and through this to s2. If we instead write ((s1,d),s2), the binding of static variables in s1 are still propagated to d, but since the subgoal (s1,d) is dynamic, no static bindings are propagated from this to s2. This is normally not a problem, as one usually omits parentheses and writes s1,d,s2, which is parsed the `right' way.

When unfolding a call to a dynamic predicate, the bindings that occur in its static subgoals are not propagated out to later goals in the clause where it was called from. Essentially, there are parentheses around the unfolded goal that prohibit the propagation of static bindings. Solving this problem either requires thought when writing the programs that are to be specialized, or alternatively rewriting Logimix to be less restrictive. The requirement that specialization returns exactly one specialized goal (and no bindings) will have to be lifted, so specialization instead returns a list of pairs (residual goal, static bindings). The static bindings can then be used to produce specialized versions of the subsequent subgoals. An alternative approach that achieves the same e ect is to pass the following goals as a parameter to the procedure that specializes a goal, specifying a kind of continuation. Whenever a static binding occurs, it will have an a ect on the entire continuation. This is similar to the strategy used for improving the results of Similix [31,28].

9.4Exercises

Exercise 9.1 Consider the ap predicate for appending lists:

ap([],L,L).

ap([A|L],M,[A|N]) :- ap(L,M,N).

Assume that the intended call pattern to ap is with the rst two parameters instantiated and the third possibly (but not always) uninstantiated.

Chapter 10

Aspects of Similix: A Partial Evaluator for a Subset of Scheme

This chapter describes partial evaluation of a subset of the dynamically typed functional language Scheme, including higher-order functions and limited side effects. The presentation is based on the approach taken by Bondorf and Danvy in the partial evaluator Similix, but we focus here on the principles and do not give a completely faithful description of the actual Similix system. Similix uses polyvariant specialization of named functions and is an o -line partial evaluator, as is the Scheme0 specializer from Chapter 5. However, in addition to handling a more complex language, Similix also handles the problems of in nite unfolding and duplication in a new and illuminating way, and emphasizes preserving the termination properties of programs.

The binding-time analysis handles higher-order functions, using the closure analysis described in Chapter 15.

The Similix partial evaluator is rather more practical than those described in the preceding chapters. For instance, the set of basic functions is extensible, basic functions can be classi ed according to their e ects, side e ects are handled correctly, and the termination properties of residual programs are better. Moreover, the Similix system contains a binding-time debugger which provides useful feedback concerning the binding-time properties of programs. The result is a partial evaluator which is more complicated than those described earlier, but one which has had many practical applications.

Similix was initially developed by Bondorf and Danvy; the recent versions are due mainly to Bondorf. This chapter is based on their papers [28,30,31,32] and on Bondorf's thesis [27].

10.1An overview of Similix

Our version of the Similix subject language is called Scheme1. It extends Scheme0 from Chapter 5 with lambda abstractions (higher-order functions) and let bind-

204

An overview of Similix 205

ings. Lambda abstractions require some changes to the binding-time analysis and specialization, mainly because they may be partially static. Specialization with respect to higher-order values and partially static lambdas is explained in Section 10.2. Handling let-expressions requires a new occurrence counting!analysis to decide whether the let may be unfolded without risk of duplication.

In addition, the real Similix has a exible way to de ne new base functions, and allows limited side e ects in base functions. All side e ects must be dynamic (that is, they must take place after specialization). Moreover, expressions with side e ects cannot be discarded, nor duplicated, nor reordered. Base functions and side e ects will not be further discussed in this chapter.

Recent versions of Similix use continuation-based reduction, which improves the binding times of many programs. It is explained in Section 10.5. Continuationbased reduction also allows the handling of partially static data structures without duplicating or discarding expressions (see Section 10.6).

10.1.1The structure of Similix

Similix works in three main phases: preprocessing, specialization, and postprocessing. The preprocessing phase analyses, transforms, and annotates the subject program, based on a description of its input only. The specialization phase specializes the annotated subject program with respect to the given static input. The postprocessing phase unfolds calls to trivial residual functions.

1.Preprocessing The preprocessing is done in four main steps.

1.1Insert an identity let-binding (let (x x) . . .) around the body of each function and lambda, for every variable x. The purpose is to isolate the problem of duplication from that of in nite unfolding.

1.2Do binding-time analysis, including detection of lambdas that may appear in dynamic contexts. Such lambdas must have dynamic parameters and body, and cannot be applied at specialization time.

1.3Create a new named function, called an sp-function, for each dynamic if and for each dynamic lambda. All sp-functions (and the goal function) are called by dynamic calls (calld); all other functions are called by static ones (calls).

1.4Analyse the number of occurrences of dynamic let-bound variables; annotate let expressions as dynamic (letd) or static (lets).

2.Specialization Starting with the program point (g, vs0) where g is the goal

function and vs0 is the static input, repeatedly construct specialized functions until the program is complete (if ever), as for Scheme0.

208Aspects of Similix: A Partial Evaluator for a Subset of Scheme

(2)Lambdas in dynamic contexts

In Scheme0, all values were base values, and therefore a static value v could always be converted into a dynamic value, namely the expression (quote v). This conversion is called lifting and was indicated in the two-level Scheme0 syntax by the operator lift. Lifting is necessary when the static value appears in a dynamic context. A branch of a dynamic ifd is a typical example of a dynamic context: we must generate code for the if expression and therefore also for each branch, even when its value v is static.

It is far more complicated to lift functional values. In fact, such values are never lifted during specialization. Instead, all lambda abstractions that might need to be lifted are classi ed as dynamic lambdad before specialization. The reason is that lifting in uences the binding times of other functions in the program.

To see this, consider lifting a functional value. The lifting should result in a lambda expression (lambda (x) e), that is, a piece of Scheme1 code. But then the lambda variable x must be dynamic: it will not be bound to a static value during specialization. Furthermore, if e contains a call (f x) of a named function, then (re)classifying x as dynamic will in uence the binding times of function f and thus the rest of the program. Therefore the binding-time analysis must detect all lambdas that need to be lifted, and must reclassify their bound variables as dynamic, before specialization.

A lambda needs to be lifted if it appears in a dynamic context. A lambda is in a dynamic context if it is a possible value of: a (sub)expression whose binding time is dynamic, a dynamic variable (whether function-, lambdaor let-bound), the argument of a dynamic lambda application, or the body of a dynamic lambda.

(3) Binding-time analysis of let-expressions

It is tempting to think that the result of (let (x e1) e) is static when the result of e is, even if e1 is dynamic (for instance, when x does not appear in e). However, this is not safe, as it would require the specializer to discard the dynamic expression e1. If the evaluation of e1 is non-terminating, then discarding it would change the termination properties of the program. Therefore the binding-time analysis must assume that the result of (let (x e1) e) is dynamic if e1 is dynamic, even when e is static.

Thus Be[[(let (x e1) e)]] equals Be[[e1]] t Be[[e]] in the Scheme1 binding-time analysis to be presented in Section 15.3. However, Section 10.5 shows one way to improve the handling of let-expressions.

10.1.5Specialization of Scheme1 programs

As in Scheme0, the named program points are the named functions, and a specialized program point is a pair (f . vs) of a named function and values for its static parameters. We generate a residual function for each specialized program point as

210 Aspects of Similix: A Partial Evaluator for a Subset of Scheme

environment components vv are equal. Equal closures de ne extensionally equal functions. The converse does not hold.

10.1.7Reduction of two-level Scheme1 expressions

Reduction of two-level Scheme1 expressions is almost as simple as that for Scheme0 (Figure 5.7). The only complicated case is dynamic function application (calld), which involves function specialization. Since we may need to specialize with respect to higher-order values, we discuss calld separately in Section 10.2 below.

The function reduce for reduction of Scheme1 expressions is shown in Figure 10.3. The auxiliary function successors (not shown) must be extended to traverse Scheme1 expressions. The new cases of reduce are explained as follows.

A static lambda (lambdas` (x) e) reduces to a closure (closure ` vv) where vv is a list of the (static and dynamic) values of the variables free in the lambda.

A dynamic lambda (lambdad` (x) e) reduces to a residual lambda expression (lambda (z) e0) where the body e0 is the reduced form of e, and z is a fresh variable.

A static lambda application (e0 e1) is reduced by reducing e0 to a closure (closure ` vv), then reducing the corresponding lambda body e` in an environment where x is bound to the reduced form e01 of e.

A dynamic lambda application (e0 @d e1) reduces to the residual application (e00 e01) where e00 is the reduced form of e0 and e01 is the reduced form of e1 .

A static let-binding (lets (x e1) e) reduces to the result of reducing e in an environment where variable x is bound to the reduced form e01 of e1.

A dynamic let-binding (letd (x e1) e) reduces to the residual let-binding (let (z e01) e0) where e01 and e0 are the reduced forms of e1 and e, respectively, and z is a fresh variable.

10.2Specialization with respect to functional values

10.2.1Specialization with respect to fully static functions

Let us rst consider the simple case where no static lambda (lambdas` (x) . . . ) has any free dynamic variables. Then every static lambda reduces to a static closure, consisting of a label ` and values for its free variables (which are all static by assumption). For example, consider the program

(define (f b)

(g (lambda1 (z) (+ z b)))) (define (g h)

(h 3))

and assume that b, z, and h are static. The superscript 1 is a label. Further assume