Multi-stage Programming

Course #:  COMP 511
Instructor:  Walid Taha (DH 3103)
Class time:  MWF 10:00AM – 10:50AM (Office Hours:  M 2:00 – 3:00)
Class room: Sewell Hall 562

 

 

 

Introduction

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.

Lectures

#

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

HWK1

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

Sheard, SAIG’01

(No review needed)

12

9/19

F

 

Partial evaluation

Jones, GPCE’02

 

13

9/22

M

 

and termination analysis

 

 

14

9/24

W

Large scale studies

Software Engineering (SDRR)

Kieburtz et al, ICSE 94

Review needed J

15

9/26

F

 

Scientific computing (FFTW)

Frigo 96

 

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

Taha, Makholm, and Hughes

 

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

 

Jones, Gomard, and Sestoft

HWK2

23

10/15

M

 

 

 

 

24

10/17

W

Runtime code generation

Cyclone

Smith (JFP SAIG) Up to s6.  No review.

HWK3

25

10/20

M

 

 

S7 and up.  Review due this class

HWK4

26

10/22

W

 

 

contd

 

27

10/24

F

 

 

Jumps between templates

HWK5

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

Sztipanovits and Karsai (GPCE’02)

 

32

11/5

W

 

 

Czarnecki et al. (GPCE’02)

 

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

 

 

 

11/28

Thanksgiving recess

 

 

New macros paper

 

 

12/ 1

 

 

 

Kamin’s Jumbo paper

 

 

12/3 

 

 

 

Tempo

 

 

12/5 

 

 

 

‘C

 

 

 

 

 

 

 

 

 

References

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 et al. 95.

16.   Ocaml textbook draft

Resources

            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

Previous Year’s Class Projects

            Tsuen-Wan Ngan

            Stephan Ellner

            Jianhong Zhang

            Nathan Froyd

            John Joseph Bachir

            Thomas Liu

            Scott Crosby

            James Sasitorn

            Luke Hoban

Accomodations for Students with Special Needs

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.