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

Summary 61

1.Changing language style, for example from non-linear, value-oriented expressions to linear, command-oriented machine code.

2.Sequentializing naturally non-sequential processes, e.g. devising a stack to remember temporary results obtained while evaluating the parts of an arithmetic expression in a particular sequence.

3.Lowering the level of abstraction from source level (e.g. `higher-level language') to a target code level tailored to that particular source code, e.g. P-code for implementing Pascal.

4.Devising data structures at the machine code level suitable for implementing higher-level data (products, sums, recursively de ned data, functions as values, etc.), all implemented in a linear storage space.

5.Implementing value management, e.g. going from implicit last-in rst-out scope rules to stacked activation blocks containing environment bindings.

3.6Summary

This chapter concerned interpreters: operational semantics for programming languages in a directly executable form. Important topics included the following:

interpreted programs usually run slower than directly executed ones;

the speed di erence is often a practically signi cant factor;

the interpretation overhead is nearly constant for a given source program being interpreted | the constant depends on the program but not the input;

the lambda calculus is a useful notation for de ning functions;

computation in the lambda calculus can be de ned by reduction relations;

evaluation strategies used in functional languages are restrictions of these relations;

call-by-name evaluation terminates more often than call-by-value.

We also presented interpreters written in ML for three mini-languages: the call- by-value lambda calculus, rst-order recursion equations, and a simple imperativeow chart language.

Finally, we summarized the achievements and non-achievements of compilation by automatic program specialization.

62 Programming Languages and Interpreters

3.7Exercises

Exercise 3.1 Identify the free and bound variable occurrences in the following lambda expressions. For each bound occurrence, point out the binding lambda.

1.(x ( x. x.x x) x)

2.(x ( x.( x.x) x) x)

3.h.( x.h (x x)) ( x.h (x x))

2

Exercise 3.2 Use the and reduction rules to reduce the following lambda expressions:

1.x (( y.x) z)

2.( x.x y) ( z.z)

3.( y. z.z y) ( k.z)

4.( x.( y.x y) x) ( x.z)

5.( f. g. x.f x (g x)) ( x. y.x) ( x. y.x) a

2

Exercise 3.3 Find two -expression M and N such that

1.M is evaluated faster with call-by-value than with call-by-name

2.N is evaluated faster with call-by-name than with call-by-value

2

Exercise 3.4 Let M be any lambda expression. Show that there is a lambda expression D such that Yv M ) D and D ) M( a.M D a), using the call-by-value reduction order:

Yv = h.( x.h( a.(x x)a))( x.h( a.(x x)a))

2

Exercise 3.5 A lambda expression is said to be in normal form when no -, -, or conditional reduction can be applied to any subexpression.

Find a -expression P without free variables, such that reduction of P to normal

Exercise 3.6 Show every step in the call-by-name reduction of the expression: Yn(M)(1), where Yn and M are de ned as follows:

Exercise 3.7 Reduce the expression fib(4) with call-by-name, where fib is de ned as:

fib = Yn ( f. n.if (n=1 or n=2) then 1 else f(n-1)+f(n-2))

Exercise 3.10 * Consider a tiny imperative language. A program has only one variable X, whose value is a list. Programs have the following syntax:

The informal semantics is straightforward. An expression e evaluates to a list. For example, X evaluates to its current value. If e evaluates to ["A","B","C"], then expression hd e evaluates to ["A"], and tl e evaluates to ["B","C"].

An assignment X := e evaluates e to obtain a value v, then makes v the new current value of X. A sequencing c1;c2 executes c1, then c2. A while loop while e do c rst evaluates e to a value v. If v is ["nil"] then the loop has no further e ect; otherwise it has the same e ect as c; while e do c.

Consider the example program pgm:

read X;

while hd X do X := tl X; write X

This program outputs the longest su x of its input starting with "nil", if any. For instance, if the input is ["A","nil","B"], then the output is ["nil","B"].

1.The running time tp(inp) of a program p on input inp is the number of operations that p performs when executed with input inp. The operations counted are: assignment, test (in the while loop), hd, tl, and fetching the value of X. For instance,

64 Programming Languages and Interpreters

tpgm(["A","nil","B"]) = 9

Assume the input to pgm is a list inp = [A1,..., An, "nil"], where Ai 6= "nil". Describe the running time tpgm(inp) as a function of n.

2.Write an interpreter int for the tiny imperative language. The interpreter should be in the same language, extended as desired with constants and other list manipulation operations and/or command forms as desired. It may not, however, use recursive or other function calls.

Hint: use a `control stack', whose top contains the expression or command currently being executed, and whose lower elements can contain expressions or commands to be executed later, together with ` ags', each describing what is to be done when the expressions or commands above it are nished.

3.The running time tint(p; inp) of the interpreter is the number of operations that int performs when executing p on inp.

How large is tint(pgm, ["A","nil","B"])?

4.Assume again that the input is a list inp = [A1,..., An, "nil"], where Ai 6= "nil". Describe the running time tint(pgm; inp) as a function of n.

5.What is the relation between tint(pgm; inp) and tpgm(inp) for large n?

2

68Partial Evaluation for a Flow Chart Language

Many of the usual complications in partial evaluation arise, but due to the simplicity of the language they appear in a very clean form. Solving the problems for the miminal imperative language rst and then moving the solutions to more complex frameworks has been shown to be fruitful.

4.1Introduction

We show that certain basic techniques are su cient to construct a nontrivial and self-applicable program specializer for a very simple imperative language. The result, called mix, is only 65 lines long.

We present one approach to program specialization, namely polyvariant specialization, also called polyvariant mixed computation [40] (others exist, e.g. supercompilation [265,267]). Successive concepts and techniques will be brought in only on the basis of need, so as to distinguish necessary from arbitrary design decisions and reduce the inevitable complexity problems that occur when documenting an existing system. To make our mix as simple and readable as possible we have assumed `library' functions as needed; we let these functions do some cumbersome work not central to the concepts of program specialization.

Three fundamental assumptions dominate this chapter, and di erentiate it from much other work in program transformation. The rst is that we are only interested in methods that are completely automatic, with no need at all for user advice while program transformation is taking place. The second is that our methods must be strong enough to compile by specializing an interpreter with respect to a xed source program. Third, we must be able automatically to generate stand-alone compilers. To do this we must be able to self-apply the specializer, i.e., to specialize the specializer itself with respect to a xed interpreter.

Thesis

Our main thesis is that program specialization can be done by three steps, all essentially independent of the particular programming language being transformed. The underlying ideas are not new, having been seen implicitly in several earlier works including [19,76,175,265,267] and more explicitly in [40].

We consider only deterministic languages, and suppose that any program has a set of program points which include the `current control point' at any instant during program execution. Examples include labels in a ow chart language, function names in a functional language, and procedure (predicate) names in a logic programming language. The three steps of the program specialization algorithm are as follows:

1.Given the value of part of the program's input, obtain a description of all computational states reachable when running the program on all possible

What is partial evaluation? 69

input values.

2.Rede ne the program's control by incorporating parts of the data state into the control state, yielding perhaps several specialized versions of each of the program's control points (0, 1 or more; hence the term polyvariant specialization).

3.The resulting program usually contains many trivial transitions. Optimize it by traditional techniques, yielding the specialized (or residual) program.

A note on termination

In some places this chapter is not completely precise with respect to termination properties. These problems are in general ignored, so certain equations describing computer executions may be formally incorrect because of the possibility that one side is unde ned when the other is not. The purpose of this chapter is to communicate certain programming concepts; a more formalistic treatment might make it harder to understand the basic algorithms. We defer the discussion of problems and solutions concerning termination to Chapter 14. Hence we simply ignore the problem, just ensuring that the programs we deal with terminate `often enough'.

4.2What is partial evaluation?

Given a program and its input data, an interpreter can execute the program producing a nal answer. Given a program and only part of this program's input data, a program specializer will attempt to execute the given program as far as possible yielding as result a residual program that will perform the rest of the computation when the rest of the input data is supplied.

To de ne program specialization more precisely we need a concise notation describing the e ect of running a program. Suppose p is a program written in the language L. Recall from Section 3.1.2 that we denote the result of running the program p on some input data d (if it terminates) by

[[p]]L d = result

Since program specializers accept both programs and data as input, we assume that both p and d are drawn from a common set D of data values. A well-known notation allowing programs to be treated as data is Lisp's list notation, hence we take D to be the set of Lisp S-expressions. We shall represent programs as Lisp lists as described in Section 2.3.4.