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

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

for the sake of argument that g is to be specialized with respect to the fully static function (lambda1 (z) (+ z b)). If the static value of b is 10, then the residual program could be:

(define (f x) (g1))

(define (g1) 13)

In this case code generation for specialized functions can proceed exactly as for Scheme0. All static parameters are removed from the called function's parameter list, no matter whether their values are rst-order or higher-order.

10.2.2Specialization with respect to partially static functions

Specialization with respect to a partially static lambda (one having free dynamic variables) is more involved. Consider again the program

(define (f x)

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

(h 3))

but now assume that x is dynamic, while z and h are still static. Then g's argument (lambda1 (z) (+ z x)) is a partially static function, and reducing the application (h 3) in the body of g would give the residual expression (+ 3 x). The dynamic variable x appears in the specialized version g1 of g, and therefore x must be passed to g1 in the residual program.

The residual program could be:

(define (f x) (g1 x))

(define (g1 x) (+ 3 x))

For a slightly more complicated example, consider

(define (f x)

(g (let (w (* x x)) (lambda2 (z) (+ z w))))

)

(define (g h) (h 3))

Assume that x and w are dynamic and that z and h are static. The let binds w to the dynamic expression (* x x), and returns a closure (closure 2 (* x x)) in which w is a free dynamic variable, bound to (* x x).

Specializing g with respect to the closure (closure 2 (* x x)), we have to pass the dynamic value (* x x) of w to the residual version of g:

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

become new formal parameters of the specialized function. Function get-dynamic returns the corresponding list of dynamic values that become new arguments in the residual call.

When specializing a call (calls f . . . ) the fresh variable names returned by new-names have the general form (zh . . . . (z2 . (z1 . z0)) . . . ), h 1. Here z0 is a static formal parameter (of f), whose value is a partially static closure (closure `0 vv0). For j = 1; . . . ; h , 1, variable zj is a static free variable of closure `j,1 and its value is a partially static closure (closure `j vvj). Finally, zh is a dynamic free variable of `h,1.

10.2.4Finding the static skeleton

A specialized program point (f . vs) is a pair of a function name f and values vs of its static parameters. A specialized program point should contain only static information that can actually be used (cf. Section 4.9.2).

Only the static `skeleton' of a partially static closure (closure ` vv) is useful for specialization. More precisely, the label ` is useful, as are the values of fully static variables in vv. The dynamic value of a dynamic variable in vv is not useful during specialization. For partially static closures in vv, the useful parts are found recursively as for the top-level closure.

The recursive extraction of the static skeleton of a closure is done by function get-static:

(define (get-static v newx)

Function get-static extracts the static `skeleton' of a closure, recursively replacing every dynamic value in the closure's environment component vv with a fresh variable. The resulting new environment maps a static base-type variable to its value, maps a dynamic variable to its fresh name, and maps a static closure-type variable to the static skeleton of its value. The fresh variables used by get-static are precisely those returned by new-names.

Note that get-dynamic extracts all dynamic values bound in the closure's environment component vv, whereas get-static throws them away. Thus their results are complementary.

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

The modi ed lines are marked with an asterisk * below.

(define (specialize program vs0)

let ((define (f1 _ _ ) _ ) . _ ) = program in (complete (list (f1 :: vs0)) () program)

)

(define (complete pending marked program) if pending is empty then

() else

let (f . vs) 2 pending

let (define (f (x1. . . xm) (xm+1. . . xa)) e) = (lookup f program) let (vs1 . . . vsm) = vs

*let (y1. . . yk) = (append (new-names vs1 x1). . . (new-names vsm xm)) let evs = (reduce e (x1. . . xm xm+1. . . xa) (vs1. . . vsm xm+1. . . xa)) let newmarked = marked [ f(f . vs)g

let newpending = (pending [ (successors evs)) n newmarked

*let newdef = (list 'define (list (f . vs) y1. . . yk xm+1. . . xa) evs) in (newdef :: (complete newpending newmarked program))

)

Figure 10.4: Main loop of Scheme1 specialization algorithm.

is annotated as lets if the bound value x is static or occurs at most once in the residual code, otherwise it is annotated as letd.

The insertion of let-bindings means that a function call can be unfolded without risk of duplication: the function parameter is always used exactly once, namely in the let-binding. The annotation on the let-binding governs unfolding of the let, and unfolds only if no code duplication is possible.

The classi cation of a let as static or dynamic does not a ect its binding time. In particular, making it letd does not mean that its body changes from a static to a dynamic context. To see this, note that a let expression can be classi ed as a dynamic letd only if the bound variable is dynamic. In this case the binding-time analysis has already deemed the result of the entire let expression dynamic (cf. Section 10.1.4), so its body is in a dynamic context already.

For an example, consider (let (x e1) (lambda (x) e)). Assume that e1 (and thus x) is dynamic, so the binding-time analysis classi es the result of the entire let as dynamic. The lambda in the let body is a possible result of the entire let expression, and therefore is in a dynamic context. Classifying the let as lets or letd does not change this.

Call unfolding on the y 217

10.4Call unfolding on the y

Similix uses a new strategy for call unfolding on the y, creating a so-called specialization point for each dynamic conditional and for each dynamic lambda. The specialization point is a new named function (here called an sp-function) whose parameters are the free variables of the conditional or lambda, and whose body is the entire conditional or lambda.

A call to an sp-function (or to the goal function) is never unfolded: it must be a calld. A call to an existing function (except the goal function) is always unfolded: it must be a calls. If the subject program does not contain any loop which is controlled only by static data (or not controlled at all), then this approach avoids in nite unfolding; namely, in this case an in nite unfolding loop must involve a dynamic conditional or recursion via the Y combinator (or similar), which must involve a dynamic lambda.

The insertion of specialization points corresponds to the insertion of specialization points around dynamic conditionals in Scheme0 (cf. Section 5.5.4). In Scheme0, if we do not unfold dynamic conditionals, then in nite unfolding can happen only because of static in nite loops. In Scheme1 (but not in Scheme0), recursion can be expressed using the Y combinator (written as a lambda abstraction), and the truth values (true and false), and conditionals can be encoded as lambda expressions also:

true as (lambda (x) (lambda (y) x)) false as (lambda (x) (lambda (y) y))

(if e1 e2 e3) as (((e1 (lambda (z) e2)) (lambda (z) e3)) ())

The new variable z must not occur in e2 and e3. Thus controlled recursion need not involve any conditionals, but a dynamic truth value is now represented by a dynamic lambda. By specializing also at every dynamic lambda we therefore avoid in nite unfolding except when it corresponds to a static in nite loop.

In the residual program generated by the specializer, conditionals and lambda abstractions can appear only outermost in residual function bodies. However, after the residual program has been generated, a postprocessing phase unfolds the call to every residual function (except the goal function) which is called exactly one place, thus eliminating many trivial functions. The postunfolding must stop, as shown by the following argument. All in nite unfolding involves a cycle of functions (possibly just one function) calling each other cyclically. Consider such a cycle. If the goal function is on the cycle, then the unfolding stops there. If the goal function is not on the cycle, then there is a function on the cycle which can be called from outside the cycle. Thus there are at least two calls to that function, and none of them is unfolded, thus stopping the unfolding at that function.

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

10.5Continuation-based reduction

The goal of continuation-based reduction is to exploit static subexpressions of dynamic expressions.

Example 10.1 Consider the expression

(+ 3 (let (x e) 10))

and assume that e is dynamic. Then the result of the entire let-expression will be considered dynamic by the binding-time analysis, even though the body is static. With the ordinary reduce function above, the residual program will be

(+ 3 (let (x e0) 10))

where e0 is the reduced form of e. That is, the addition of 3 and 10 has not been done. However, if the context `(+ 3 . . . )' were propagated to the static expression 10, a better residual expression could be obtained:

(let (x e0) 13)

The context was propagated to a static subexpression, resulting in a binding-time

Expression reduction with context propagation is called continuation-based reduction. However, the example is very simple, and the same improvement could be obtained just by local (intraprocedural) transformation of the let-expression to (let (x e0) (+ 3 10)) before reduction.

General continuation-based reduction allows context propagation also across unfoldable (static) function calls. This may improve the binding times of a program considerably, and cannot be achieved by local transformations.

Consel and Danvy have shown that general continuation-based reduction can be obtained by a global transformation of the subject program: converting the subject program to continuation passing style (CPS) before reduction [56]. For a presentation of the CPS conversion itself, see Fischer [87], Plotkin [219], or Danvy and Filinski [68].

Consel and Danvy's technique allows propagation of contexts under dynamic conditionals as well as under dynamic let-bindings. In this case the residual programs will also be in CPS, which is sometimes not desirable. However, Danvy has shown that, subject to certain restrictions, programs in continuation passing style can systematically be converted back to direct style, thus eliminating the continuation parameters [67].

Bondorf has shown that some bene ts of continuation-based reduction can be obtained by modifying the specializer, thus avoiding the transformation to CPS [31]. When applying the reduce function to an expression e, the context K of the reduced value is also passed to reduce. Modifying the handling of dynamic letd then propagates the context K to the (possibly static) body of the let. This is

Continuation-based reduction 219

built into recent versions of Similix, but (currently) does not allow propagation of contexts under dynamic conditionals. The reason is that Similix encapsulates dynamic conditionals in sp-functions and hence in dynamic function calls, and contexts cannot be propagated across dynamic function calls.

The remainder of this section presents the idea in more detail. It is based on Bondorf's paper, which gives precise de nitions, theorems, and proofs [31]. In the remainder of this section, keep in mind that Scheme1 has call-by-value semantics.

10.5.1Continuation passing style

In continuation passing style (CPS) every function takes an extra argument: a continuation. The continuation is a function which consumes the result of the function and produces the nal result of the computation. Thus the continuation represents the remainder of the current computation, or the context of the current subexpression reduction.

For example, the ordinary factorial function

(define (fac n) (if (zero? n)

1

(* n (fac (- n 1)))))

has the following form in CPS:

(define (faccps n K) (if (zero? n)

(K 1)

(faccps (- n 1) (lambda (r) (K (* n r))))))

The K argument is the continuation. It is applied to the result of the function call, as seen in the rst branch (K 1). In the second branch, the continuation of the recursive call is (lambda (r) (K (* n r))). This continuation will take the result r of the recursive call, multiply it by n, and pass the result to the original continuation K. Note that the program in CPS has the same operational behaviour as the original one.

The relation between fac and faccps is the following for every function (continuation) K and non-negative integer n:

(K (fac n)) = (faccps n K)

In particular, (fac n) = (faccps n id), where id denotes the identity function

(lambda (r) r). It also follows that (faccps n K) = (K (faccps n id)). Continuations were invented in the late 1960s and used for transformation, proof,

and mathematical description of programming languages; see e.g. [223]. Continuations are used also in implementations of functional programming languages such as Scheme and Standard ML.

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

10.5.2Continuation-based reduction of Scheme1

The idea in continuation-based reduction of Scheme1 is to replace function reduce from Figure 10.3 in continuation-passing style. This in itself achieves nothing, but it allows us later to improve the handling of dynamic letd; this will be done in Section 10.5.4 below.

The continuation-based version redcps of reduce is shown in Figure 10.5. In the gure, id denotes the identity function (lambda (r) r). For brevity, the cases for dynamic function call, dynamic base function, static lambda abstraction, and lambda application have been left out, as they present no new problems.

The main loop of the specializer in Figure 10.4 must be changed to call function redcps as (redcps e (x1. . . xm xm+1. . . xa) (vs1. . . vsm xm+1 . . .xa) id) where id is the identity function (lambda (r) r). This achieves the same as the old call to reduce, since (redcps e vn vv id) = (reduce e vn vv).

10.5.3Well-behaved continuations

It holds that

(redcps e vn vv K) = (K (redcps e vn vv id))

for every function K. This equivalence has been used in the cases for ifd, lambdad, and letd to make the continuations of the recursive calls well-behaved. Roughly, a continuation K is well-behaved if whenever (K r) is an expression, then (1) K embeds its argument r in a strict position, that is, the evaluation of (K r) implies the evaluation of r; and (2) K does not introduce new variable bindings visible to r. The precise de nition can be found in [31, Section 4].

The importance of well-behaved continuations will be clear in the improved handling of let shown in Section 10.5.4.

In the `natural' CPS version of the ifd case, there would be a continuation K of form (lambda (r3) (K0 (list 'if r1 r2 r3))) which would embed the argument expression r3 in a branch of an if expression. Since that branch may not be evaluated when the if is, K would not be well-behaved.

Likewise, in the `natural' CPS version of the letd case, there would be a continuation K of form (lambda (r) (K0 (list 'let (x r1) r))) which would embed the argument expression r in a let-expression. Since that makes the binding of x visible to r, K would not be well-behaved.

In the `natural' CPS version of the lambdad case, there would be a continuation which would embed its argument r in a non-strict position, and introduce new variable bindings visible to r, thus violating requirement (1) as well as (2).

Using the equivalence shown above, all ill-behaved continuations have been avoided.