PEIOOL

This is the web page for the 2nd-part course Partial Evaluation for Imperative and Object-Oriented Languages [PEIOOL] taught here at DAIMI during the 4th quarter (spring 2004).

This course gives an introduction to the program specialization technique of partial evaluation and its application to imperative and object-oriented languages (C and Java). We will cover the enabling principles and provide an insight into the advanced program analysis techniques needed to specialize realistic programs. Interactive sessions and a practical project will provide hands-on experience.

Partial evaluation is a program transformation technique that specializes programs to their usage context. Partial evaluation can be seen as a highly aggressive form of optimization that transforms the program according to invariants provided by the programmer. During the course we will investigate its applications within domains such as automatic compiler generation, image processing, operating systems, and scientific computations.

• When: exams in PEIOOL are on June 10th, unless you have a special agreement with Ulrik.
• Requirements: the following materials are considered part of the examination requirements, although see below for my concrete expectations.
  • Tutorial Notes on Partial Evaluation. Charles Consel and Olivier Danvy. Proceedings of POPL93, the 1993 ACM Symposium on Principles of Programming Languages, pp. 493-501.
  • Chapter 11 of Partial Evaluation and Automatic Program Generation, excluding 11.6 and 11.7.
  • A Uniform Approach for Compile-Time and Run-Time Specialization
  • Static and Dynamic Program Compilation by Interpreter Specialization
  • Accurate Binding-Time Analysis for Imperative Languages: Flow, Context, and Return Sensitivity (with a focus on overall understanding rather than details)
  • Effective Specialization of Realistic Programs via Use Sensitivity (with a focus on overall understanding rather than details)
  • Automatic Program Specialization for Java
• What to say: At the exam I value an intuitive understanding of partial evaluation for imperative languages higher than the ability to remember e.g. various formal specifications of BTA dataflow equations. Knowing everything is of course best, but if you could do most of the exercises, you can most certaintly pass the exam as well! Partial evaluation for object-oriented languages may or may not be discussed at the exam, but it will not normally be a focus (exception: you brought a program with an object-oriented flavor to the exam).
• What to bring: You must bring an example of partial evaluation for imperative or object-oriented languages to the exam. The example can be based on an exercise, on something from Olivier's course, or whatever you can think of. If your example is based on previous work, you are of course expected to say so at the exam. REMEMBER: It can be hard to get programs through Tempo. Start with a minimal program, make it specialize, and then expand it. If you start well before the exam, it's easier for me to help you. You are not expected to spend e.g. more than a day's work preparing the example.
• Grading: The grade is based on your exercises, the PE example you bring, and your oral examination, as follows. The exercises and the PE example determine a starting point, so if they are good, you don't have to work as hard to get a good grade. It is nevertheless possible to get a good grade without having handed in the exercises and with a fairly small example. Similarly, having done the exercises and a cool example is no guarantee for a good grade. To get a high grade, you must convince us that you both have an intuitive understanding of PE and that you have mastered the hardest parts of working with imperative programs.
• Latest date for exercises: exercises not handed in when I meet at work Tuesday morning the 8th of June will not be taken into account. There may be several days in a row every once in a while where I am not able to answer questions (this is for example the case for the 7th of June and a few days before that).
• FAQ
  • Is it better to make a completely new example from scratch, or to e.g. reuse an existing example from Olivier's course? Reusing an example (either from Olivier's course or from one of the exercises) allows you to do something more advanced, which is better. If you would like to reuse an example, I would definitely recommend that you do so. (Only, you should tell us at the exam that you reused it.) Of course, a competely new revolutionary example reimplemented from scratch based on techniques that Olivier and I have never seen before is better then most other things, but is not needed for a good grade.

• Reading material is listed for the day for which I expect you to have read it, likewise for assignments which are listed for the day they are due.