|
Multi-stage Programming Course #: COMP 511 |
|
|
|
|
Multi-stage programming is a new approach to building generic programs that do not pay a runtime overhead for their generality. Languages that support multi-stage programming allow us to perform symbolic computation and partial evaluation, making it easier to achieve the goals of multi-stage programming. Such languages are particularly useful for building efficient implementations of other programming languages, including domain-specific ones (DSLs). Over the last six years, there has significant research into such languages, including issues such as their implementation, type systems, semantics, and use to define macros.
The goal of this course is to introduce you to this new technology and to research in this area. The course includes an introduction to the applications of these languages, the theoretical foundations, and implementation issues. Course work will include reading research papers, discussions, doing a few exercises in MetaOCaml, and a term paper.
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/25 |
M |
Organizational Meeting |
Admin. Staging, power ex. |
|
|
|
2 |
8/27 |
W |
Multi-stage programming |
Why generation. Why MSP notionation and type systems. |
MSP Ch1, Taha and Hook 98 |
|
|
3 |
8/39 |
F |
|
Q & A (mostly on ML) |
MSP Ch2 |
|
|
4 |
9/1 Labor day |
M |
|
Renaming, staging, small examples |
|
|
|
5 |
9/3 |
W |
|
Bigger example: term rewriting |
MSP Ch3 |
|
|
6 |
9/5 |
F |
Implementing Multi-stage languages |
|
MSP Ch4, MetaOCaml
paper (Draft) |
|
|
7 |
9/8 |
M |
Semantics and Type Systems for Multi-stage
languages |
Big-step semantics |
MSP Ch5 |
Project proposal (1 pg) |
|
8 |
9/10 |
W |
|
Type systems |
|
|
|
9 |
9/12 |
F |
|
Type safety |
|
|
|
10 |
9/15 |
M |
|
Type safety |
|
|
|
11 |
9/17 |
W |
|
Meta-programming |
(No review needed) |
|
|
12 |
9/19 |
F |
|
Partial evaluation |
|
|
|
13 |
9/22 |
M |
|
and termination analysis |
|
|
|
14 |
9/24 |
W |
Large scale studies |
Software Engineering (SDRR) |
Review needed J |
|
|
15 |
9/26 |
F |
|
Scientific computing (FFTW) |
|
|
|
16 |
9/29 |
M |
Staged Interpreters |
Interpreters, Hindley-Milner-typed |
Pasalic, Sheard, and Taha (upto 1.3) |
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/1 |
W |
|
Jones Optimality and Tag Elimination |
|
|
|
18 |
10/3 |
F |
|
|
|
(No review on paper) |
|
19 |
10/6 |
M |
|
Dependent types |
Pasalic, Sheard, and Taha (rest) |
(Midterm out. Due Monday in class) |
|
20 |
10/8 |
W |
|
|
|
|
| 21 | 10/10 | F | ||||
|
22 |
10/13 Midterm Recess |
F |
Binding-time improvements |
|
||
|
23 |
10/15 |
M |
|
|
|
|
|
24 |
10/17 |
W |
Runtime code generation |
Cyclone |
Smith (JFP SAIG) Up to s6. No review. |
|
|
25 |
10/20 |
M |
|
|
S7 and up. Review due this class |
|
|
26 |
10/22 |
W |
|
|
contd |
|
|
27 |
10/24 |
F |
|
|
Jumps between templates |
|
|
28 |
10/27 |
M |
Staging and Macros |
Typed macros |
Ganz, Sabry, and Taha 01 (up to 4.1) |
|
|
29 |
10/29 |
W |
|
|
Rest of paper (Review due today) |
|
|
30 |
10/31 |
F |
|
|
Discussion of HWK5 |
|
|
31 |
11/3 |
M |
Program generation for embedded systems |
Survey |
|
|
|
32 |
11/5 |
W |
|
|
|
|
|
33 |
11/7 |
F |
Project presentations |
James Sasitorn |
|
|
|
34 |
11/10 |
M |
|
Tsuen-Wan Ngan |
|
|
|
35 |
11/12 |
W |
|
Luke Hoban |
|
|
|
36 |
11/14 |
F |
|
Stephan Ellner |
|
|
|
37 |
11/17 |
M |
|
Nathan Froyd |
|
|
|
38 |
11/19 |
W |
|
Thomas Liu |
|
|
|
39 |
11/21 |
M |
|
John Joseph Bachir |
|
|
|
40 |
11/24 |
W |
|
Jianhong Zhang |
|
|
|
40 |
11/26 |
F |
|
Scott Crosby |
|
|
|
|
|
|
|
|
New macros paper |
|
|
|
12/ 1 |
|
|
|
Kamin’s Jumbo paper |
|
|
|
12/3 |
|
|
|
Tempo |
|
|
|
12/5 |
|
|
|
‘C |
|
|
|
|
|
|
|
|
|
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.