Foundations of Partial Evaluation and Program Specialization

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

• are easy to understand (they have a very clean semantic foundation),
• are simple enough for students to code quickly, and that
• capture the most important properties that one encounters when specializing programs written in much richer languages.

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

• Table of contents:
  (toc.notes.ps.gz)
• Chapter 1: Introduction
  (chapter01.notes.ps.gz), (chapter01.slides.ps.gz).
• Chapter 2: The Flowchart Language FCL
  (chapter02.notes.ps.gz), (chapter02.slides.ps.gz).
• Chapter 3: Online Partial Evaluation
  (chapter03.ps.gz), (chapter03.slides.ps.gz).
• Chapter 4: Offline Partial Evaluation
  (chapter04.notes.ps.gz), (chapter04.slides.ps.gz).
• Chapter 5: Slicing
• Bibliography
  (bibliography.notes.ps.gz).
• Abstraction-based partial evaluation
  Associated Java implementation

Scheme Implementations

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.

• Here is the README file for the SCM implementation. It contains some example runs, and a listing of the exercises.

Java Implementations

• Here is the README file for the Java implementation. It contains some example runs, and a listing of the exercises.

Acknowledgements