Book Excerpts:

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 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 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.

This book contains 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). This book explains 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.

Intended Audience:

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 constructing 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.