Partial Evaluation and Automatic Program Generation

Appeared in Volume 8/3, August 1995

Keywords: partial evaluation.

N.D. Jones, C.K. Gomard, and P. Sestoft
With chapters by L.O. Andersen and T. Mogensen.

The preface and table of contents can be obtained via anonymous FTP from:
ftp://ftp.diku.dk/pub/diku/dists/jones-book/about-book

or by sending an email request to me (sestoft@id.dth.dk).

Partial Evaluation in a Nutshell

Let p be a program which takes two inputs d1 and d2. Ordinarily, p (d1,d2) would be evaluated in one step: evaluate p with input (d1, d2), to produce the result res.

However, it may also be evaluated in two steps:

Partially evaluate p with input d1, to produce a new program r.
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 describes principles, techniques, and applications of partial evaluation, as well as several partial evaluation systems (for Scheme, Prolog, and C) constructed by other researchers.

Prentice Hall Int. 1993.
xii + 415 pages.  ISBN 0-13-020249-5.
List price: US$ 44.95

Peter Sestoft
Dept. of Computer Science
Technical Univ. of Denmark, Building 344
DK-2800 Lyngby, Denmark
Tel: +45 45 93 1222/3749
Fax: +45 42 88 4530
Email: sestoft@id.dth.dk