|
Multi-stage Programming Course #: COMP 511 |
|
|
|
|
Multi-stage programming is a neat way of building programs at runtime, compiling them, and running them. Another way of understanding these languages is that they let you do partial evaluation. By using such languages, many interesting programs can be made 6-30 times faster. Yet programming in these languages is surprisingly easy! Over the last five years, there has also been a lot of work on type safety in such languages. These type systems ensure, for example, that whatever code you build at runtime, it's always type safe.
The goal of this course is to introduce you to this new technology for building program generators. The course will include an introduction to the applications of these languages, the theoretical foundations, and implementation issues. Course work will include reading research papers, discussions, doing various kinds of exercises, and experimenting with one such languages called MetaOCaml.
Students are encouraged to discuss the material covered in class in homeworks on the news group rice.owlnews.comp511.
|
# |
Date |
Day |
Topic |
Details |
Reading (Review
due in class) |
Excercises (Due next class) |
|
1 |
8/26 |
M |
Organizational Meeting |
Admin. Staging, power ex. |
|
|
|
2 |
8/28 |
W |
Multi-stage programming |
Why generation. Why MSP notionation and type systems. |
MSP Ch1, Taha and Hook 98 |
|
|
3 |
8/30 |
F |
|
Q & A (mostly on ML) |
MSP Ch2 |
|
|
4 |
9/4 |
W |
|
Renaming, staging, small examples |
|
|
|
5 |
9/6 |
F |
|
Bigger example: term rewriting |
MSP Ch3 |
|
|
6 |
9/9 |
M |
|
Meta-programming |
|
|
|
7 |
9/11 |
W |
|
Partial evaluation |
Project proposal (1 pg) |
|
|
8 |
9/13 |
F |
|
and termination analysis |
|
|
|
9 |
9/16 |
M |
Large scale studies |
Software Engineering (SDRR) |
|
|
|
10 |
9/18 |
W |
|
Scientific computing (FFTW) |
|
|
|
11 |
9/20 |
F |
Staged Interpreters |
Interpreters, Hindley-Milner-typed |
Pasalic, Sheard, and Taha (upto 1.3) |
(No review needed) |
|
12 |
9/23 |
M |
|
Jones Optimality and Tag Elimination |
|
|
|
13 |
9/25 |
W |
|
|
|
|
|
14 |
9/27 |
F |
|
Dependent types |
Pasalic, Sheard, and Taha (rest) |
Review needed J |
|
15 |
9/30 |
M |
|
|
|
|
|
16 |
10/2 |
W |
Binding-time improvements |
|
Progress report: Show you have implemented key parts of project, staged them, and collected some measurements. (Hand this in with review on 10/9). |
|
|
17 |
10/9 |
W |
|
|
|
|
|
18 |
10/11 |
F |
Implementing Multi-stage languages |
|
MSP Ch4, MetaOCaml paper (Draft) |
(No review on paper) |
|
19 |
10/16 |
W |
Semantics and Type Systems for Multi-stage languages |
Big-step semantics |
MSP Ch5 |
(Midterm out. Due Monday in class) |
|
20 |
10/18 |
F |
|
Type systems |
|
|
|
21 |
10/21 |
M |
|
Type safety |
|
|
|
22 |
10/23 |
W |
|
Type safety |
|
|
|
23 |
10/25 |
F |
Runtime code generation |
Cyclone |
Smith (JFP SAIG) Up to s6. No review. |
|
|
24 |
10/28 |
M |
|
|
S7 and up. Review due this class |
|
|
25 |
10/30 |
W |
|
|
contd |
|
|
26 |
11/1 |
F |
|
|
Jumps between templates |
|
|
27 |
11/4 |
M |
Staging and Macros |
Typed macros |
Ganz, Sabry, and Taha 01 (up to 4.1) |
|
|
28 |
11/6 |
W |
|
|
Rest of paper (Review due today) |
|
|
29 |
11/8 |
F |
|
|
Discussion of HWK5 |
|
|
30 |
11/11 |
M |
Program generation for embedded systems |
Survey |
|
|
|
31 |
11/13 |
W |
|
|
|
|
|
32 |
11/15 |
F |
Project presentations |
James Sasitorn |
|
|
|
33 |
11/18 |
M |
|
Tsuen-Wan Ngan |
|
|
|
34 |
11/20 |
W |
|
Luke Hoban |
|
|
|
35 |
11/22 |
F |
|
Stephan Ellner |
|
|
|
36 |
11/25 |
M |
|
Nathan Froyd |
|
|
|
37 |
11/27 |
W |
|
Thomas Liu |
|
|
|
38 |
12/2 |
M |
|
John Joseph Bachir |
|
|
|
39 |
12/4 |
W |
|
Jianhong Zhang |
|
|
|
40 |
12/6 |
F |
|
Scott Crosby |
|
|
1. Multi-stage Programming: Its theory and Applications, Taha 99. Now also available in pdf.
2. Partial Evaluation and Automatic Program Generation, Jones, Gomard and Sestoft.
3. Semantics, Applications and Implementation of Program Generation (2000), Taha (Ed).
4. Semantics, Applications and Implementation of Program Generation (2001), Taha (Ed).
5. Generative Programming and Component Based Software Engineering (2002), Batory, Consel and Taha (Eds).
6. Generative International Conference on Aspect Oriented Software Development (2002), Ossher and Kiczales (Eds).
7.
A
software engineering experiment in software component generation, Kieburtz
et al 96.
8.
The
anatomy of a component generation system, Taha and Hook 98.
9. What not to do when writing an intperpreter for staging, Jones 96.
10. A Fast Fourier Transform Compiler, Frigo 99
11. Tagless Staged Interpreters for Typed Languages, Pasalic, Taha, and Sheard 02
12. Tag
Elimination and Jones Optimality, Taha, Makholm, and Hughes 00.
13. A syntactic
approach to type soundness, Wright and Felleisen 92
14. Compiling Embedded Programs to Byte Code, Rhiger 02.
15.
Optimistic Incremental
Specialization: Streamlining a Commercial Operating System, Pu
16. Ocaml textbook draft
· Detailed class announcement
· Course schedule for this year will be similar to this schedule
· OGI course on Fundamentals of Staged Computations
· OSU course on Program Generation and Meta-Programming
· U Berlin course on Program generation
Students with disabilities are encouraged to contact me during the first two weeks of class regarding any special needs. Students with disabilities should also contact Disabled Student Services in the Ley Student Center and the Rice Disability Support Services.