Partial Evaluation and Automatic Program Generation

Cover The book Partial Evaluation and Automatic Program Generation gives a comprehensive presentation of partial evaluation: theory, techniques, and applications. It is suitable for self-study, and for graduate courses and advanced undergraduate courses on program transformation techniques. See the preface and the table of contents.

Download the full text of the book

What is partial evaluation?

Partial evaluation creates a specialized version of a general program. The specialized program may be much faster than the general one.

Let p be a program which takes two inputs d1 and d2. Ordinarily, the application of p to (d1,d2) would be evaluated in one step:

        Evaluate p with input (d1, d2), to produce the result res.
However, alternatively it may be evaluated in two steps:
        (1) Partially evaluate p with input d1, to produce a new program r.
        (2) Evaluate r with input d2, to produce the result res.
The program r is a specialized version of p (for the particular value d1 of the first input), and is called a residual program. The process of producing r (in step 1) is called partial evaluation, or program specialization. The benefit of partial evaluation is speed of execution: the specialized program r is often much faster than the general program p.

The book's bibliographic data

N.D. Jones, C.K. Gomard, and P. Sestoft, Partial Evaluation and Automatic Program Generation.
With chapters by L.O. Andersen and T. Mogensen.
Prentice Hall International, June 1993. xii + 415 pages. ISBN 0-13-020249-5.
List price: 44.95 US dollars.
Reviewed in Computing Reviews 35(7): 346-347, 1994, entry 9407-0420.

How to obtain a copy of the book

Download the full text in Postscript (2.3 MB) or in PDF (US letter) (1.7 MB) or PDF (A4) (1.7 MB).

Getting a paper copy may be harder; the book is out of print. You may find it second-hand somewhere, or else you may contact Neil D. Jones or Peter Sestoft to see if we have any copies left.

Contacting the authors

Online materials related to the book

Other online materials on partial evaluation

Peter Sestoft 1996-10-15, 1998-08-24, 2001-09-06, 2004-05-23