Foundations of Partial Evaluation and Program Specialization

Course Notes

John Hatcliff

These notes give a gentle introduction to program specialization concepts using a simple flowchart language called FCL (the idea of using FCL to explain partial evaluation is due to Gomard and Jones, who used it to present offline partial evaluation).

The goal of these notes is to present program specialization systems that

The notes currently contain material on online partial evaluation, offline partial evaluation, two-level languages and binding-time analysis, program slicing, and abstraction-based partial evaluation (combining abstract interpretation and partial evaluation). Other material on constraint-based binding-time analysis, extended forms of binding-time analysis, and handling structures, pointers, and arrays will be added during the Spring of 1999.

Each specialization system is presented using rule-based operational semantics specifications. These specifications provide enough formalization so that one can prove the correctness of the given specializers with relative ease.

For each specialization system presented, there are accompanying Scheme and Java implementations. The Java implementations include web-based documentation and are generally more sophisticated than the Scheme implementations. On the other hand, the Scheme implementations are much shorter and can be understood more quickly. For programming exercises, students are given code templates for the specializers and are asked to fill in the holes. The more mundane portions of the implementation (code for parsing, stores, and other data structures) are provided. Other exercises involve using the operational semantics to study particular aspects of the specializers, and applying the specializers to various examples.

Available material:

Lecture notes and slides
Scheme implementation
Java implementation
Exercises and programming project

Lecture Notes and Slides

Scheme Implementations

Here is the student version (templates) for the Scheme implementations of the FCL interpreter and partial evaluators. You must use Aubry Jaffer's SCM implementation of Scheme, or do a little porting (don't know how much).

You are strongly advised to use the EMACS editor when programming in Scheme. It does a lot of nice indenting for you. You can also run SCM inside of EMACS -- much easier to work with than running it stand-alone.

Java Implementations

Here is the student version (templates) for the Java implementations of the FCL interpreter and partial evaluators.


A subset of this material was originally presented by John Hatcliff at the 1998 DIKU International Summer School on Partial Evaluation. The authors gratefully acknowledge the substantial financial support of the TOPPS group at the University of Copenhagen, and the United States National Science Foundation (NSF CAREER Grant CCR-9806354 (previously CCR-9701418)).

John Hatcliff ( March 1, 1999.