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

Continuation-based reduction 221

(define (redcps e vn vv K)
case e of
number n	=> (K n)
(quote c)	=> (K c)
yj	=> (K vj) where (y1 . . . yj . . . yk) = vn
		(v1 . . . vj . . . vk) = vv
(ifs e1 e2 e3)	=>
(redcps e1 vn vv
(lambda (r1) (if r1		(redcps e2 vn vv K)
		(redcps e3 vn vv K))))
(ifd e1 e2 e3)	=>
(redcps e1 vn vv
(lambda (r1)
	(K (list 'if r1 (redcps e2 vn vv id)
		(redcps e3 vn vv id)))))
(calls f (e1 . . .	em) (em+1 . . .	ea)) =>
(redcps e1 vn vv
(lambda (r1) . . .
	(redcps ea vn vv
	(lambda (ra)
		(redcps ef (x1. . . xa)(r1. . . ra) K)))
	. . . ))
where (define (f (x1. . . xm)(xm+1. . . xa)) ef)=(lookup f program)
(calld f (e1 . . .	em) (em+1 . . .	ea)) => . . .
(ops e1 . . . ea)	=>
(redcps e1 vn vv
(lambda (r1) . . .
	(redcps ea vn vv
	(lambda (ra)
		(K (op r1 . . . ra)))) . . . ))
(opd e1 . . . ea)	=> . . .
(lift e)	=> (redcps e vn vv
	(lambda (r) (K (list 'quote r))))

(lambdas` (x) e)	=> . . .
(lambdad` (x) e) =>
(K (list 'lambda (z) (redcps e (x :: vn) (z :: vv) id)))
where z is a fresh identi er
(e0 e1)	=> . . .
(e0 @d e1)	=> . . .
(lets (x e1) e)	=>
(redcps e1 vn vv
(lambda (r1) (redcps e (x :: vn) (r1 :: vv) K)))
(letd (x e1) e)	=>

(redcps e1 vn vv

(lambda (r1) (K (list 'let (z r1)

(redcps e (x::vn) (z::vv) id)))))

where z is a fresh identi er

Figure 10.5: Continuation-based reduction of Scheme1 expressions.

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

10.5.4Extracting static information from a dynamic let

So far, nothing has been achieved by constructing the CPS version redcps of reduce; the two functions are equivalent. However, now we can improve the treatment of letd by using the equivalence

(K (let (x r1) r)) = (let (x r1) (K r))

which holds only when K is well-behaved. It does not hold for ill-behaved K, because

(1) if r1 is unde ned, then the right hand side is unde ned, yet if K does not embed its argument in a strict position, then the left hand side might be de ned; and (2) if K could introduce new bindings, then these would be visible to r1 on the left hand side but not on the right hand side.

Using the equivalence, we replace the right hand side of the letd case by

(redcps e1 vn vv (lambda (r1)

(list 'let (z r1)

(K (redcps e (x :: vn) (z :: vv) id)))))

Then we use the equivalence (K (redcps e vn vv id)) = (redcps e vn vv K) to transform it again, and obtain the following right hand side for the letd case of redcps:

(redcps e1 vn vv (lambda (r1)

(list 'let (z r1) (redcps e (x::vn) (z::vv) K))))

Note that the continuation K of the entire dynamic expression (letd (x e1) e) is propagated to the body e. This is advantageous when e is static and e1 is dynamic. Propagating K to e in this case allows the exploitation of the static information from e when reducing the context of the let-expression, as illustrated in Example 10.1.

It is signi cant that the context K of a static function call (calls) is propagated to the body of the called function when it is being reduced with redcps in Figure 10.5. This means that the context may propagate to a let-expression in another function, and in practice this turns out to greatly improve the binding times of programs. This cannot be achieved with local (intraprocedural) transformations of the source program.

10.5.5Improved binding-time analysis for Scheme1

The binding-time analysis must re ect the improved handling of (let (x e1) e). So far, the result of the let-expression has been deemed dynamic when either e1 or e were dynamic (cf. Section 10.1.4). However, now the result of the let-expression is deemed dynamic precisely when e is, regardless of e1, so now Be[[(let (x e1)

Handling partially static structures 223

e)]] = Be[[e]] in the Scheme1 binding-time analysis.

10.6Handling partially static structures

Assume that e1 is static and e2 is dynamic in the expression

(let (z (cons e1 e2)) (car z))

In the Scheme1 specializer as presented above, the expression (cons e1 e2) would be considered dynamic because e2 is dynamic. Hence z would be dynamic, the expression (car z) would be dynamic, and so would the result of the entire let- expression. This is because base values must either be completely static, or else dynamic.

10.6.1Partially static structures

If we allow partially static base values, then the value of z would be a pair whoserst component is static, and whose second component is dynamic. Hence (car z) would be static, and if the value of e1 were 10, say, then the entire let-expression could be reduced to 10.

Clearly, handling partially static base values will require considerable changes to the binding-time analysis as well as the specializer. Recursive partially static structures are particularly interesting. For example, consider the function mkenv that builds an environment association list from a (static) list of variable names and a dynamic list of corresponding values (the superscripts on cons are labels, called cons points):

(define (mkenv names values) (if (null? names)

()

(cons1 (cons2 (car names) (car values))

(mkenv (cdr names) (cdr values)))))

Function mkenv returns a list of pairs, whose rst components are all static and whose second components are all dynamic. The function is likely to be used this way in an interpreter being specialized with respect to a source program but without its input. The example is due to Mogensen, who used grammars to describe partially static binding times in an untyped language [187]. The result of mkenv could be described by the grammar

mkenv	! S | cons1
cons1	! P(cons2, mkenv)
cons2	! P(S, D)

Here S denotes a static value, D denotes a dynamic value, and P denotes a pair of

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

values. Nonterminal mkenv describes all possible results of the function, nonterminal cons1 describes all structures built by the cons operator labelled 1, etc. Thus the grammar says that a result of mkenv is either completely static (namely, ()) or a result of cons1. A result of cons1 is a pair of a value built by cons2 and a result of mkenv. A result of cons2 is a pair of a static and a dynamic value.

Using grammars of this form, Mogensen designed the rst binding-time analysis with partially static binding times. Consel used a cons point analysis to collect essentially the same information for an untyped higher-order language [53]. Launchbury used projections to analyse a typed language [165,167]. In Section 15.4 we shall explain Launchbury's approach.

Mogensen also showed how to preprocess a subject program, using (partially static) binding-time information to separate static and dynamic computations. Every function parameter whose value is a partially static structure is split into (essentially) one static and one dynamic parameter. Every function returning a partially static result is split into two functions, one returning the static part, and one returning the dynamic part. The static part depends only on static arguments and thus can be fully computed at specialization time. After this preprocessing a simple specializer (not handling partially static structures) can be used [190].

10.6.2Arity raising

Specialization of a program with partially static structures implies arity raising. With arity raising, one dynamic (or partially static) function parameter in the subject program may give rise to several function parameters in the residual program. For example, if a dynamic function parameter in the subject program is always a list of three elements, then it may be replaced by three simple parameters in the residual program, possibly raising the arity of the function.

Arity raising was originally done with hand annotations which guided the splitting of a dynamic variable according to the value of a static variable [245]. Then Sergei Romanenko gave an automatic forwards analysis of the structure of dynamic variables, and a backwards analysis of their use, for an untyped functional language [228]. Using a closure analysis (Section 15.2), Steensgaard and Marquard extended Romanenko's work to a higher-order language [253].

10.6.3Safe specialization of partially static structures

Recall the expression (let (z (cons e1 e2)) (car z)) from above. If the value of e1 is 10, say, then it could be reduced to 10. However, this would discard the dynamic expression e2 entirely, which is undesirable: it might change the termination properties of the program.

Similarly, the expression

(y e2)

The Similix implementation 225

(let (z (cons e1 e2)) (+ (cdr z) (cdr z)))

is a dynamic expression which could reduce to the residual expression (+ e02 e02), where e02 is the reduced form of e2. However, this would duplicate the dynamic expression e2, which is also undesirable.

The problem can be solved by binding every dynamic cons argument in a dynamic (non-unfoldable) letd, as in:

(let (z (letd (y e2) (cons e1 y))) (car z))

Using an ordinary specializer, this would achieve little, as the letd expression will give rise to a residual let, so z and hence (car z) would be dynamic.

Using the new continuation-based redcps function from Section 10.5, the modi-cation makes sense. Now the context (let (z . . . ) (car z)) will be propagated to the expression (cons e1 y), as if the expression had been written

(letd (y e2) (let (z (cons e1 y)) (car z)))

Then reduction gives (let (y e02) 10), assuming that e1 reduces to 10. The dynamic expression e2 has not been discarded. Note that with continuation-based reduction it is not necessary to actually transform the source expression this way. Also, with continuation-based reduction this works even if the expression (letd

. . . ) were hidden in the body of a function called by a static call (calls). Similarly, the second expression above would reduce to (let (y e02) (+ y y)),

in which e2 has not been duplicated.

Recent versions of Bondorf's Similix include safe handling of partially static structures.

10.7The Similix implementation

Bondorf's partial evaluator Similix (version 5.0 at the time of writing), including user manual, can be obtained by anonymous ftp from ftp.diku.dk as le pub/diku/dists/jones-book/Similix-5.0.tar.Z | see page 123 of this book.

Similix version 5.0 is written in Scheme and complies to the (uno cial) `R4RS' standard [49], and so is highly portable. It has been tested under Unix with Aubrey Ja er's free `scm' system (which is available for Unix, VMS, MS-DOS, and MacOS), and with R. Kent Dybvig's commercial `Chez Scheme' system.

10.8Exercises

Exercise 10.1 For each higher-order application in the following program (the two applications of g in h) identify which closures can be applied. Insert identity let-

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

expressions and do binding-time analysis under the assumption that x is dynamic. Annotate the program accordingly. Analyse the number of occurrences of dynamic let-bound variables, and annotate the let expressions accordingly.

(define (f x) (if (zero? x)

(+ (h (lambda (y) (+ y 1))) 42)

(+ (h (lambda (y) (+ y 1))) (h (lambda (y) (+ y x)))))) (define (h g)

(+ (g 17) (g 42)))

2

Exercise 10.2 Execute the preprocess phase for the following program, and specialize f1 under the assumption that x is dynamic. Repeat the process with x static and specialize with respect to x = 25.

(define (f1 x)

(f2 (lambda (y) (if (< x y) x y)))) (define (f2 g)

(+ (g 17) (g 42)))

2

Exercise 10.3 Specialize f in the following program with x dynamic without inserting identity let-expression. Then specialize again now with the identity letexpressions inserted. What is gained by inserting identity let-expression?

(define (f x)

(g (fak x) (fak (+ x 5)) (power 2 8))) (define (g x y z)

(+ x x y y z z)) (define (fak x)

(if (equal? x 1) 1 (* x (fak (- x 1))))) (define (power x n)

(if (equal? n 0) x (* x (power x (- n 1)))))

2

Exercise 10.4 Consider the append function below and assume that truth values and conditionals are encoded as described in Section 10.4, that is, (null? xs) returns either (lambda (x) (lambda (y) x)) or (lambda (x) (lambda (y) y)). Try specializing (while doing call unfolding on the y) with respect to xs dynamic and ys static without inserting specialization points for dynamic lambdas. Why does the strategy for call unfolding on the y fail?

(define (append xs ys)

((((null? xs) (lambda (z) ys))

(lambda (z) (cons (car xs) (append (cdr xs) ys)))) '()))

2

Exercises 227

Exercise 10.5 Consider the following program, where n (which is dynamic) is indexed in a static environment (ns holds the names and vs holds the values). For simplicity we have assumed that the indexing always succeeds. Since the static ns decreases for every recursive call to lookup it is safe to unfold completely; termination is guaranteed. Thus it is not necessary to insert a specialization point at the dynamic if. Execute the preprocess phase, without inserting a specialization point for the dynamic if, and specialize f using the direct style specializer. Specialize again using the CPS style specializer. What is gained by using the CPS style specializer?

(define (f n)

(+ 1 (lookup n '(a b c) '(1 2 3)))) (define (lookup n ns vs)

(if (null? (cdr ns)) (car vs)

(if (equal? n (car ns)) (car vs)

(lookup n (cdr ns) (cdr vs)))))

2

Exercise 10.6 Write a program to perform bubble sort. The input parameters must be an array a and its length n. Use Similix to specialize the program with respect to a known n. Comment on the length and e ciency (complexity) of the residual

program.

2

Exercise 10.7 Consider the following program to nd a path of length n from node x to node y in the directed graph G.

(define (sons G a) (cdr (assoc a G))) (define (path G n x y)

(if (< n 0) '#f

(if (= n 0)

(if (equal? x y) (list y) '#f)

(let ((p (path* G (- n 1) y (sons G x)))) (if (null? p)

'#f

(cons x p)))))) (define (path* G n y xs)

(if (null? xs) '#f

(let ((p (path G n (car xs) y))) (if (null? p)

(path* G n y (cdr xs)) '()))))

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

Using Similix, try specializing path to y dynamic, x = 1, n = 1, and

G = ((a . (b c)) (b . (d)) (c . (d)) (d . (e)) (e . ()))

;;edges from a to b and c

;;edge from b to d

;;edge from c to d

;;edge from d to e

;;no edges from e

Specialize again now with n = 3. Notation: a !n b means that there exists a path from a to b of length n. A better algorithm can be based on the following observation: a !m b if and only if either m = 0 and a = b, or m > 0 and there exists a node c with a !m div 2 c and c !m,(m div 2) b. Implement the better algorithm

in Scheme, and specialize it to various combinations of known arguments.

2

Exercise 10.8 Implement the interpreter for the call-by-value lambda calculus in Figure 3.1 in Scheme. Use Similix to specialize the interpreter to various lambda expressions, thereby compiling them to Scheme. Specialize Similix to the interpreter, thereby generating a lambda-to-Scheme compiler. Use the generated compiler on the same lambda-expressions as before. Which is the most e cient way to compile?

Why?

2

Exercise 10.9 Elimination of type checking by partial evaluation. Assume that a hypothetical, very advanced partial evaluator supermix is available. It is the intention to use supermix to compile a statically typed (like Pascal, C, ML, Miranda) language S to L given an interpreter sint for that language S.

1.Apply supermix to the interpreter sint, an S-program p, and the type of the input to p. How much type checking will be left in the residual program?

2.Same question, but for a dynamically typed (like Lisp, Scheme) language D.

2

Chapter 11

Partial Evaluation for the C Language

Lars Ole Andersen

This chapter describes o ine partial evaluation for a subset of the pragmatically oriented C programming language. C is a widely used imperative language with several features not available in the languages studied in the previous chapters. There are data structures such as structs, multidimensional arrays, and pointers; a rich variety of statements and expressions; and functions.

Partial evaluation for large-scale imperative languages is currently an active research area. Here we present principles suitable for automatic specialization of a substantial subset of C, but the techniques carry over to related languages such as Pascal and Fortran. The chapter ends with a description of the kernel of a C specializer.

11.1Introduction

The goal of partial evaluation is e ciency : by specializing a program to parts of its input, a faster specialized version can often be constructed. The aim of this chapter is to describe partial evaluation applied to a realistic large-scale imperative programming language. We shall see that several of the basic techniques from the previous chapters can be employed, but new aspects must be considered because of the more complicated semantics of C. These include, in particular, specialization of functions with side-e ects, and pointers and dynamic memory allocation.

We shall consider only o ine partial evaluation where the specialization is performed in two stages: rst the program is binding-time analysed, and subsequently it is specialized. We argue that the explicit separation of the binding times is an important stepping stone for successfully processing programs that exploit pointers and addresses. Without a prior binding-time analysis, the partial evaluator must be overly conservative, reducing the potential gain of a specialization.

Some knowledge and experience with the C programming language is expected, e.g. corresponding to Kernighan and Ritchie [147].

229

230Partial Evaluation for the C Language

11.1.1What is partial evaluation for C?

The language we consider is a substantial subset of the C programming language [124,147], including global variables, functions with both parameters and local variables, the usual statements and expressions, and data structures such as structs, multidimensional arrays, and pointers.

Given only partial input, not all statements can be executed during the specialization. Those that can be executed are called static and those that cannot are called dynamic, and similar for expressions. The goal of the binding-time analysis is to mark all statements as either static or dynamic. Given an annotated program, specialization proceeds by a symbolic execution where static statements are executed and code is generated for the dynamic ones.

Example 11.1 Consider a mini-version of the formatted print function printf()1 where for simplicity we assume that only integers can be printed out.

void mini_printf(char *fmt, int *value) f

int i;

for (i = 0; *fmt != 'n0'; fmt++) if (*fmt != '%') putchar(*fmt); else switch (*++fmt) f

case 'd': printf("%d", value[i++]); break; case '%': putchar('%'); break;

default: abort(); /* Error */

g

g

The function could for instance be found in a program implementing scienti c computation, where there would be several calls such as mini printf("Result is %dnn", v). Since the format string is given (static) it makes sense to specialize mini printf() with respect to a static fmt.

Consider each statement of mini printf(). Clearly, the for loop is entirely controlled by the fmt string and so are the if and switch. These can thus be classi ed as static. On the other hand, the output functions must be deemed dynamic since output is supposed to be delivered at run time.

Suppose a non-standard symbolic execution given as input the value "n = %d" of the format string fmt but no value for value. Static statements are executed as usual, and code is generated for dynamic statements. Static expressions, that is, expressions depending solely on static values, are evaluated, and dynamic expressions are reduced. This results in the following residual program.

1This example can be found in Kernighan and Ritchie [147], and has also been demonstrated in the Scheme language [58]