The best-known kind of program specialisation, partial evaluation, consists of taking a general program and a part of its data, and performing all the computations that depend only on the given data. The remaining computations make up the generated or `residual' program. We may think of the given data as specifying a particular member of the class of problems that the general program can solve; the residual program takes the remaining input data and solves that particular problem. Partial evaluation may sound like glorified constant folding, but in fact a wide variety of powerful techniques are needed to do it successfully, and these may completely transform the structure of the original program. Program specialisation in fact gives us a general approach to program generation.

The breakthrough which made partial evaluation suddenly `hot' came in 1985, and since then the research area has been very dynamic. Many theoretical and practical advances have transformed partial evaluators from toys into industrial-strength tools which can be used, for example, in operating system design. Yet despite the maturity which the field has reached, there are still fundamental problems being solved by quite new approaches, suggesting that it will retain its dynamism for some time to come.

This course introduces program specialisation from the beginning, via a very practical approach. The first three days are spent learning about offline partial evaluation, inherited limits, binding-time analysis, and important binding-time improvements such as CPS specialisation and the Trick. The last two days focus on type specialisation, my own recent work. The practical exercises include specialising a number of interpreters, writing your own partial evaluator, constructing generating extensions, and specialising interpreters with the type specialiser. Most of the time will be spent on these exercises; the emphasis of the course is on gaining a deep understanding of the basics, rather than a superficial overview of the field.

- What Not to Do When Writing an Interpreter for Specialisation, Neil Jones.
- Evolution of Partial Evaluators: Removing Inherited Limits, Torben Mogensen.
- An Introduction to Program Specialisation by Type Inference, John Hughes.
- Type Specialisation for the Lambda-Calculus; or, a New Paradigm for Partial Evaluation based on Type Inference, John Hughes.

- A partial evaluator for a subset of Haskell.
- The type specialiser for extended lambda-calculus.

Last modified: Mon Sep 29 12:36:24 MET DST 1997