<br />
<b>Deprecated</b>:  The each() function is deprecated. This message will be suppressed on further calls in <b>/home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php</b> on line <b>456</b><br />

Multi-Stage Programming (Class Schedule)
Instructor:  Walid Taha

Tuesday January 15th/2002. 
Lecture 1   Organizational Meeting and Introduction
            NB:  I am out of Town.  Paul Hudak will kindly fill in
            - Goals of the class:  To teach you about a very new technology
              for writing more efficient programs in high-level languages.
            - The power function example
            - Class schedule
            - Agreeing on meeting time.  We'll start with Friday afternoon
              from 2:30-5:00 and move backwards in the week, first covering
              afternoon spots, then going to the morning.
 Reading:   First two chapters of Taha99.  
            Hand in a half page summary
            of what you thought are the key points.
 Homework:  Go to google.com find the MetaOCaml home page.  
            Download MetaOCaml system, read examples, and run them.
            Write some small examples of our own, and hand them in.

Friday January 25th/2002.
Lecture 2   Staged Interpreters:  A Killer App for MSP
            - Interpreter for a simple expression language
            - Interpreter for the lambda calculus
            - Tag elimination
 Reading:   Neil Jones paper on how not to write a staged interpreter.
            The last tag elimination paper.
 Homework:  Write an interpreter for a language that can express
            boolean functions from three boolean inputs.  You need only
            deal with sum-of-product expressions.  Stage it, and gather
            performance data.  Are there other ways to write such a function
            in OCalm or MetaOCaml?  How does their speed compare?
            Carry out the timings with different expressions.  Does the
            relative speed of one implementation relative to another differ
            based on the input?

Friday February 1st/2002
Lecture 3   Term rewriting, and the CPS transformation
            - Don't forget staging doesn't work for everything
            - Sometimes, "massaging" can provide better opportunities for staging
 Reading:   Chapter three of Taha99.
 Homework:  Propose a project where you can demonstrate your understanding
            of multi-stage programming.

Friday February 8th/2002
Lecture 4   Implementing Multi-stage Programming Language
            - Interpreters aren't that easy
            - Compilers don't seem to pose a difficulty
 Reading:   Chapter four of Taha99
            Paper on MetaOCaml
            Extra:  Jones on Gomard on Partial Evaluation for the untyped lambda
            calculus.
 Homework:  Finish first running prototype of project.  This should include
            both unstaged version and test examples.  Hand it in next lecture.

Lecture 5   The Mathematical Semantics of Multi-stage Programming Languages
            - Operational semantics
               - Big-step
               - Small-step
               - Reduction
            - Denotational semantics
 Reading:   Chapters four and five of dissertation
            PEPM paper
 Homework:  Relate the big-step and small-step semantics.  Carefully show
            that chains of small-steps are chains of reduction steps.

Lecture 6   Alternative Approaches to Implementing Multi-stage Languages
             - Runtime code generation
             - Charles Consel's trick
             - The key tradeoffs
 Reading:   Charles paper on templates
            Kamin's papers on generating binaries
            Peter Thiemann's paper on higher-order code slicing
            Our PLDI submission (again)
 Homework:  Hand in staged version of your program, together with a status report
            that contains performance measurements.  Make sure you hand in the
            most recent version of your unstaged program.

Lecture 7   Class Projects
             - Summary of project description that were handed in last lecture
             - Open discussion of progress and results
 Reading:
 Homework:  Based on today's discussion, identify realistic, real-world applications
            of multi-stage programming.  Hand in a one-page report on this assignment.

Lecture 8   Multi-stage Programming in Maple (May change)
 Reading:   To be determined
 Homework:  Finish report and hand it in.  The report should include
              1) An explanation of what the program that you chose for this
                 project is supposed to do (1 page or less)
              2) An explanation of what was involved in staging the program.
              3) A clear presentation and analysis of the performance measurements
                 that were collected.
              4) An analysis of which aspects of staging this program where easy,
                 and which were not.  Are MetaOCaml's staging annotations satisfactory?
                 Is there need for additional annotations?
              5) How does the staged implementation compare to other ways of improving
                 the performance of you the program that you wrote.  For example, could
                 you have written your original program in a radically different way to
                 improve performance.
              6) A discussion of related works in the literature
              7) How useful do you think this technology will be in practice?

Lecture 9   Limitations of Multi-Stage Programming
             - Intentional analysis
             - Symbolic computation
             - Domain-specific Optimizations
            Elliot's paper

Lecture 10  Wrap up
             - Review
             - Future Directions in Multi-stage Programming
 Reading:   Tim's paper at SAIG.
            Based on your own experience with MetaOCaml and with your class project,
            write a one page report of what you think are the most important research
            directions in multi-stage programming.

Grading:  35% Homeworks
          35% Class project
          30% Final examination