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