Graduate Course in Program Specialisation


Programmers face an eternal compromise between generality and efficiency. On the one hand, the programmer who writes very general programs, which can solve wide classes of problems, minimizes programming effort. On the other hand, the programmer who optimises carefully for the particular case in hand can produce much faster code. Program specialisation tools offer a solution to this dilemma, by transforming general programs automatically into efficient specialised code.

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.



Exercises are available here.


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