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

Partial evaluation and compilation 11

Parser and compiler generation

Assuming cogen exists, compiler generation can be done by letting p be the interpreter int, and letting in1 be source. The result of specializing int to source is a program written in the specializer's output language, but with the same input/output function as the source program. In other words, the source program has been compiled from S into cogen's output language. The e ect is that int-gen is a compiler.

If we let p be program parser, with a given grammar as its known input in1, by the description above parser-gen is a parser generator, meaning that parser-gen transforms its input grammar into a specialized parser. This application has been realized in practice at Copenhagen (unpublished as yet), and yields essentially the well-known LR(k) parsers, in program form.

E ciency is desirable at three di erent times:

1.The specialized program pin1 should be fast. Analogy: a fast target program.

2.The program specializer p-gen should quickly construct pin1 . Analogy: a fast compiler.

3.cogen should quickly construct p-gen from p. Analogy: fast compiler generation.

It would be wonderful to have a program generator generator, but it is far from clear how to construct one. Polya's advice on solving hard problems: solve a simpler problem similar to the ultimate goal, and then generalize. Following this approach, we can clump boxes cogen and p-gen in Figure 1.4 together into a single program with two inputs, the program p to be specialized, and its rst argument in1. This is just the mix of Figure 1.1, so we already have a weaker version of the multiphase cogen.

We will see how cogen can be constructed from mix. This has been done in practice for several di erent programming languages, and e ciency criteria 1, 2 and 3 have all been met. Surprisingly, criteria 2 and 3 are achieved by self-application | applying the partial evaluator to itself as input.

1.4Partial evaluation and compilation

One may compile by specializing an interpreter to execute only one xed-source program, yielding a target program in the partial evaluator's output language so target = [[mix]] [int, source]. Program target can be expected to be faster than interpreting source since many interpreter actions depend only on source and so can be precomputed.

In general, program target will be a mixture of int and source, containing parts derived from both. A common pattern is that the target program's control

12 Introduction

structure and computations resemble those of the source program, while its appearance resembles that of the interpreter, both in its language and the names of its specialized functions.

The cost of interpretation

A typical interpreter's basic cycle is rst, syntax analysis; then evaluation of subexpressions by recursive calls; and nally, actions to perform the main operator, e.g. to subtract 1 or to look up a variable value. In general, running time of interpreter int on inputs p and d satis es ap tp(d) tint(p, d) for all d, where ap is a constant. (In this context, `constant' means that ap is independent of d, but may depend on source program p.) In experiments ap is often around 10 for simple interpreters run on small source programs, and larger for more sophisticated languages. Clever use of data structures such as hash tables or binary trees can make ap grow slowly as a function of p's size.

Optimality

The `best possible' mix should remove all computational overhead caused by interpretation. This criterion has been satis ed for several partial evaluators for various languages, using natural self-interpreters.

1.4.1Partial evaluation versus traditional compiling

Does partial evaluation eliminate the need to write compilers? Yes and no. . . Pro: when given a language de nition in the form of an operational semantics, a partial evaluator eliminates the rst and largest order of magnitude: the interpretation overhead. A virtue is that the method yields target programs that are always correct with respect to the interpreter. Thus the problem of compiler correctness seems to have vanished. This approach is clearly suitable for prototype implementation of new languages from interpretive de nitions (known as metaprogramming in the Prolog community).

Contra: the generated target code is in the partial evaluator's output language, typically the language the interpreter is written in. Thus partial evaluation will not devise a target language suitable for the source language, e.g. P-code for Pascal. It won't invent new runtime data structures either, so human creativity seems necessary to gain the full handwritten compiler e ciency. Recent work by Wand, and Hannan and Miller, however, suggests the possibility of deriving target machine architectures from the text of an interpreter [277,110].

Finally, partial evaluation is automatic and general, so its generated code may not be as good as handwritten target code. In particular we have not mentioned classical optimization techniques such as common subexpression elimination, exploiting available expressions, and register allocation. Some of these depend on speci c machine models or intermediate languages and so are hard to generalize;

Automatic program generation 13

but there is no reason why many well-known techniques could not be incorporated into the next generation of partial evaluators.

1.5Automatic program generation

This section shows the sometimes surprising capabilities of partial evaluation for generating program generators.

1.5.1The rst Futamura projection

Compiling by partial evaluation always yields correct target programs, veri ed as follows:

out = [[ source]]S input

=[[int]] [source, input]

=[[[[mix]] [int, source] ]] input

=[[target]] input

The last three equalities follow respectively by the de nitions of an interpreter, mix, and target. The net e ect has thus been to translate from S to L. Equation target = [[mix]] int source is often called the rst Futamura projection, rst reported in [92].

1.5.2Compiler generation by self-application

We now show that mix can also generate a stand-alone compiler:

compiler = [[mix]] [mix, int]

This is an L-program which, when applied to source, yields target, and is thus a compiler from S to L, written in L. Veri cation is straightforward from the mix equation:

target = [[ mix]] [int ,source]

=[[[[mix]] [mix, int] ]] source

=[[compiler]] source

Equation compiler = [[mix]] [mix, int] is called the second Futamura projection. The compiler generates specialized versions of interpreter int, and so is in e ect int-gen as discussed in Section 1.3.5. Operationally, constructing a compiler this way is hard to understand because it involves self-application | using mix to specialize itself. But it gives good results in practice, as we shall see.

Critical assessment 15

1.5.5Hierarchies of metalanguages

A modern approach to solving a wide-spectrum problem is to devise a user-oriented language to express computational requests, viz. the widespread interest in expert systems. A processor for such a language usually works interpretively, alternating between reading and deciphering the user's requests, consulting databases, and doing problem-related computing | an obvious opportunity to optimize by partial evaluation.

Such systems are often constructed using a hierarchy of metalanguages, each controlling the sequence and choice of operations at the next lower level [234]. Here, e ciency problems are yet more serious since each interpretation layer multiplies computation time by a signi cant factor. We shall see that partial evaluation allows one to use metaprogramming without order-of-magnitude loss of e ciency.

1.6Critical assessment

Partial evaluation and self-application have many promising applications, and work well in practice for generating program generators, e.g. compilers and compiler generators, and other program transformers, for example style changers and instrumenters. They are, however, still far from perfectly understood in either theory or practice. Signi cant problems remain, and we conclude by listing some of them.

Greater automation and user convenience

The user should not need to give advice on unfolding or on generalization, that is to say, where statically computable values should be regarded as dynamic. (Such advice is required in some current systems to avoid constructing large or in nite output programs.)

The user should not be forced to understand the logic of a program resulting from specialization. An analogy is that one almost never looks at a compiler-generated target program, or a Yacc-generated parser.

Further, users shouldn't need to understand how the partial evaluator works. If partial evaluation is to be used by non-specialists in the eld, it is essential that the user thinks as much as possible about the problem he or she is trying to solve, and as little as possible about the tool being used to aid its solution. A consequence is that debugging facilities and interfaces that give feedback about the subject program's binding-time separation are essential for use by non-specialists.

Analogy with parser generation

In several respects, using a partial evaluator is rather like using a parser generator such as Yacc. First, if Yacc accepts a grammar, then one can be certain that the parser it generates assigns the right parse tree to any syntactically correct input string, and detects any incorrect string. Analogously, a correct partial evaluator

16 Introduction

always yields specialized programs faithful to the input program. For instance, a target program will be faithful to its source, and a generated compiler will always be correct with respect to the interpreter from which it was derived.

Second, when a user constructs a context-free grammar, he or she is mainly interested in what strings it generates. But use of Yacc forces the user to think from a new perspective: possible left-to-right ambiguity. If Yacc rejects a grammar, the user may have to modify it several times, until it is free of left-to-right ambiguity.

Analogously, a partial evaluator user may have to think about his or her program from a new perspective: how clear is its binding-time separation? If specialized programs are too slow, it will be necessary to modify the program and retry until it has better binding-time properties.

Partial evaluation is no panacea

Not all programs bene t from specialization. Knowing the value of x will not signi cantly aid computing xn as in Figure 1.2, since no actual operation on x can be done by the partial evaluator. Further, the e ciency of mix-generated target programs depend crucially on how the interpreter is written. For example, if the interpreter uses dynamic name binding, then generated target programs will have runtime variable name searches; and if it uses dynamic code creation then generated target programs will contain runtime source language text.

Some recurring problems in partial evaluation

Rapid progress has occurred, but there are often problems with termination of the partial evaluator, and sometimes with semantic faithfulness of the specialized program to the input program (termination, backtracking, correct answers, etc.). Further, it can be hard to predict how much (if any) speedup will be achieved by specialization, and hard to see how to modify the program to improve the speedup.

An increasing understanding is evolving of how to construct partial evaluators for various languages, of how to tame termination problems, and of the mathematical foundations of partial evaluation. On the other hand, we need to be able to

make it easier to use a partial evaluator;

understand how much speedup is possible;

predict the speedup and space usage from the program before specialization

deal with typed languages;

generate machine architectures tailor-made to a source language de ned by an interpreter.

Overview of the book 17

1.7Overview of the book

Prerequisites

Our presentation style is semiformal. On the one hand, the various terms and algorithms used are precisely de ned. For example, the programs we present may be unambiguously executed by hand. On the other hand, we do not use advanced mathematical concepts and terminology (domains, algebras, categories, etc.); ordinary discrete mathematics is su cient.

We assume the reader to be familiar with a Pascal-like programming language. Prior knowledge of a functional language such as Lisp, Scheme, ML, Miranda, or Haskell would make some parts easier to follow, but is not a prerequisite. Finally, some experience with compilers (e.g. an undergraduate compiler construction course) would be desirable.

Outline

Part I introduces concepts and notation of programming languages.

Chapter 2 introduces functions, recursion, and data types, and the distinction between a program (text) and the function it de nes.

Chapter 3 de nes the concepts of interpreter and compiler and discusses program running times and interpretation overhead. Then three mini-languages are presented: the lambda calculus, rst-order recursion equations, and a ow chart language. Interpreters for executing them are given also, to introduce the concepts of abstract syntax, environment, and closure, which will be used in the partial evaluators presented later.

Part II presents partial evaluators for two of the mini-languages introduced in Chapter 3. This introduces a variety of techniques for partial evaluation, useful also in the partial evaluation of stronger languages.

Chapter 4 concerns the ow chart language. A partial evaluator is developed in considerable detail, emphasizing concrete examples and carefully motivating the various design decisions that are taken. Enough details are given to allow the reader to implement the partial evaluator and generate compilers on his or her own computer. It is shown by examples that partial evaluation can compile, generate compilers, and even generate a compiler generator. The key to the latter two is self-application as in the Futamura projections of Section 1.5. It may come as a surprise that self-application leads to considerable improvements in compiler running times. Program texts illustrating all of these are included.

The important topic of binding-time analysis is introduced, and a variety of technical problems are identi ed, analysed, and solved.

Chapter 5 describes a self-applicable partial evaluator for a rst-order language of recursive equations. Many of the principles of Chapter 4 can be adapted to this stronger programming language.

Chapter 6 presents one way to recognize a good partial evaluator, and shows

18 Introduction

that there is a theoretical limit to the amount of speed-up that can in general be expected from partial evaluation.

Chapter 7 compares o ine partial evaluation (using a separate binding-time analysis phase) to online partial evaluation. The o ine approach appears bene cial to self-application, and all partial evaluators presented in this book are o ine. Finally, some advice on constructing a self-applicable partial evaluator for a new programming language is given.

Part III presents partial evaluators for four languages which are stronger in various respects than the ow chart and recursion equation language.

Chapter 8 describes a self-applicable partial evaluator for the untyped lambda calculus, stronger than the previous partial evaluator in that it can deal with higher-order functions. It is seen that type inference provides a simple and elegant way to do binding-time analysis for higher-order partial evaluation.

Chapter 9 describes a self-applicable partial evaluator for a Prolog subset, emphasizing problems not seen in the earlier chapters.

Chapter 10 presents a partial evaluator `Similix', which handles a substantial subset of Scheme including both higher-order functions and restricted side e ects. Scheme is interesting because it is a realistic language.

Chapter 11 presents some techniques required to deal with languages (C, Pascal, etc.) where the programming style relies on both (recursive) function calls and a global, mutable state, including arrays and pointers.

Part IV discusses practical problems frequently encountered when using partial evaluation, and gives several examples of its practical application.

Chapter 12 shows that some subject programs are less amenable to speed-up by partial evaluation than others, and presents some transformation that improve the results of partial evaluation while preserving the meaning of the subject program.

Chapter 13 describes several applications of partial evaluation and demonstrates that the utility of partial evaluation is not limited to compiler generation.

Part V presents advanced topics, more brie y than the previous subjects and with references to current literature.

Chapter 14 contains a discussion of termination in partial evaluation. An algorithm su cient to guarantee that program specialization terminates (in the absence of in nite static loops) is presented and justi ed, for the simple ow chart language of Chapter 4.

Chapter 15 explains the program analysis method called abstract interpretation, presents a so-called closure analysis which is useful for doing analysis of higherorder programs, and applies this to produce a higher-order binding-time analysis for the partial evaluator in Chapter 10. Finally, it presents a projection-based approach to binding-time analysis of partially static data structures.

Chapter 16 relates partial evaluation to recursive function theory, gives a more abstract view of program specialization, and discusses the types of program-pro-

Overview of the book 19

cessing programs: interpreters, compilers, and partial evaluators.

Chapter 17 explains the relation between partial evaluation and classical program transformation methods such as Burstall and Darlington's fold/unfold technique.

Finally, Chapter 18 gives an overview of the literature on partial evaluation and closely related topics, and serves as a guide to further studies in the eld.