Dept & No:      CS630
Title:          Multi-stage Programming
First Offered:  Spring 2002
Enrollment:     limited
Credit:         1.0
CR/D/F:         No
Classes RP:     No
Meeting Time:   F 2:30 - 5:00 AKW 500 (Next class is Friday 25nd)
Starred:        Yes
Format:         Lecture
Instructor:     Walid Taha
Title:          Associate Research Scientist


Brief Description
=================

Multi-stage programming languages support building programs at
runtime, compiling them, and running them.  These languages express
partial evaluation, and can be used to make many interesting programs
run 6-30 times faster.  Using these languages remarkable easy.  The
course is a chance to explore this promising technology.


Expanded Description
====================

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 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.


Prerequisites
=============

Experience in computer programming (to the level satisfied
by a functional programming or a compilers course) is essential.
Basic knowledge of discrete mathematics.


Rough Topic Outline
===================

Lecture 1  Organizational meeting
Lecture 2  A Killer App for MSP:  Staged Interpreters
Lecture 3  Another App:  Term rewriting
Lecture 4  Implementing MSP languages
Lecture 5   ...(cont'd)
Lecture 6  The Semantics of MSP languages
Lecture 7   ...(cont'd)
Lecture 8  Runtime Machine Code Generation
Lecture 9   [Discussion of class projects]
Lecture 10 MSP in Maple
Lecture 11 Limitations of MSP
Lecture 12  [Review]


Course Requirements
===================

Course requirements include weekly homework assignments and a term
project of the student's choice.  Programming assignments will involve
implementation staged programs and analyzing their performance.
Final grade will be based 40% on homework, 40% on class project, and
20% on final examination.




Required Books
==============

Main text:
  Walid Taha
  Multi-stage Programming:  Its theory and Applications
  PhD Dissertation, 1999.  Available online from
   ftp://cse.ogi.edu/pub/tech-reports/1999/99-TH-002.ps.gz

Reference:
  Semantics, Applications and Implementation of Program Generation (2000).
  LNCS 1924, Springer Verlag.  Available online
   http://link.springer.de/link/service/series/0558/tocs/t1924.htm

  Semantics, Applications and Implementation of Program Generation (2001).
  LNCS 2196, Springer Verlag.  Available online.
   http://link.springer.de/link/service/series/0558/tocs/t2196.htm