From the preface

This book is about partial evaluation, a program optimization technique also known as program specialization.

It presents general principles for constructing partial evaluators for a variety of programming languages, and it gives examples of applications and numerous references to the literature.

Partial evaluation

It is well known that a one-argument function can be obtained from a two argument function by specialization, i.e. by fixing one input to a particular value. In analysis this is called restriction or projection and in logic it is called currying. Partial evaluation, however, works with program texts rather than mathematical functions: a partial evaluator is an algorithm which, when given a program and some of its input data, produces a so-called residual or specialized program. Running the residual program on the remaining input data will yield the same result as running the original program on all of its input data.

The theoretical possibility of partial evaluation was established many years ago in recursive function theory as Kleene's `s-m-n theorem'. This book concerns its practical realization and application. Partial evaluation sheds new light on techniques for program optimization, compilation, interpretation, and the generation of program generators. Further, it gives insight into the properties of the programming languages themselves. Partial evaluation can be thought of as a special case of program transformation, but emphasizes full automation and generation of program generators as well as transformation of single programs.

Partial evaluation and compilation

Partial evaluation gives a remarkable approach to compilation and compiler generation. For example, partial evaluation of an interpreter with respect to a source program yields a target program. Thus compilation can be achieved without a compiler, and a target program can be thought of as a specialized interpreter.

Compiler generation

Moreover, provided the partial evaluator is self-applicable, compiler generation is possible: specializing the partial evaluator itself with respect to a fixed interpreter yields a compiler. Thus a compiler can be thought of as a specialized partial evaluator: one which can specialize only an interpreter for a particular language. Finally, specializing the partial evaluator with respect to itself yields a compiler generator. Thus a compiler generator can be thought of as a specialized partial evaluator: one which can specialize only itself.

Other applications

The application of partial evaluation is not restricted to compiling and compiler generation. If a program takes more than one input, and one of the inputs varies more slowly than the others, then specialization of the program with respect to that input gives a faster specialized program. Moreover, very many real life programs exhibit interpretive behaviour. For instance, they may be parametrized with configuration files, etc., which seldom vary, and therefore they may be profitably specialized. The range of potential applications is extremely large as shown by the list of examples below. All have been implemented on the computer by researchers from Copenhagen, Princeton, and Stanford universities; and INRIA (France) and ECRC (Germany). All have been seen to give significant speedups.

This book

We give several examples of such applications, but the main emphasis of the book is on principles and methods for partial evaluation of a variety of programming languages: functional (the lambda calculus and Scheme); imperative (a flowchart language and a subset of C); and logical (Prolog). We explain the techniques necessary for construction of partial evaluators (for instance, program flow analysis) in sufficient detail to allow their implementation. Many of these techniques are applicable also in other advanced programming tasks.

The book is structured as follows. The first chapter gives an overview of partial evaluation and some applications. Then Part I introduces fundamental programming language concepts, defines three mini-languages, and presents interpreters for them. Part II describes the principles of self-applicable partial evaluation, illustrated using two of the mini-languages: flow charts and first-order recursion equations. Part III shows how these principles apply to stronger languages: the lambda calculus and large subsets of the Prolog, Scheme, and C programming languages. Part IV discusses practical aspects of partial evaluation, and presents wide range of applications. Part V presents a more theoretical view and a number of advanced techniques, and provides extensive references to other research.

The book should be accessible even to beginning graduate students and thus useful for beginners and researchers in partial evaluation alike. The perspective on partial evaluation and the selection of material reflect the experience of our group with construction of several partial evaluators. These include the first non-trivial self-applicable partial evaluators for a functional language, an imperative language, the lambda calculus, a Prolog subset and a subset of C. This work has been carried out at the University of Copenhagen.

Back to book homepage.