Book on Partial Evaluation

Peter Sestoft <>
Thu, 1 Jul 1993 09:27:42 GMT

          From comp.compilers

Related articles
Book on Partial Evaluation (Peter Sestoft) (1993-07-01)
| List of all articles for this month |

Newsgroups: comp.compilers
From: Peter Sestoft <>
Keywords: books, optimize
Organization: Compilers Central
Date: Thu, 1 Jul 1993 09:27:42 GMT


The following book is now available:

N.D. Jones, C.K. Gomard, and P. Sestoft,
With chapters by L.O. Andersen and T. Mogensen.
Prentice Hall International 1993. xii + 415 pages. ISBN 0-13-020249-5.
List price: 44.95 US dollars.

The preface and table of contents can be obtained via anonymous ftp from

Node: (Internet
File: pub/diku/dists/jones-book/about-book

or by sending an email request to me (

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:

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

Partial evaluation has strong links to (the non-syntactical aspects
of) interpretation, compilation, and compiler generation:

* Partial evaluation of an interpreter with respect to a
source program produces a target program.
* Partial evaluation of a partial evaluator with respect to an
interpreter produces a compiler.
* Partial evaluation of a partial evaluator with respect to a
partial evaluator produces a compiler generator (or a currying
transformation on programs, which is the same).

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.
Peter Sestoft * * Department of Computer Science
Technical University of Denmark, Building 344 DK-2800 Lyngby, Denmark
Tel: +45 45 93 33 32 * Direct: +45 45 93 12 22/3749 * Fax: +45 42 88 45 30

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.