Course Schedule
Pt03
The course will be thaught in November and December 2003 and January 2004.
This is the planned schedule for the course. Adjustments might be made along the way so check this
page regularly.
Participants are expected to attend all lectures.
Chapters from the lecture notes Strategies for Program Transformation will be handed out in advance of the lectures and should be read before the lecture. The number of copies will be based on the number of students registered for the course.
Part of the lecture will be dedicated to making exercises, which should be handed in at the end of the lecture. A good job on these exercises will result in a bonus point for the grade of your exams.
In the first part of the course, each lecture is followed by a lab session with exercises about that lecture. These exercises should be handed in before the next lecture.
Week 47
Lecture 1 : Introduction
- Monday, November 17, 13:00
- What is program transformation?
- A taxonomy of program transformation
- Issues in the implementation of program transformation systems
- Book:PartI
- Distinguish different kinds of program transformation by their output
- Assignment Classifying Transformations
Lecture 2 : Program Representation
- Wednesday, November 19, 13:00
- Syntax definition
- Concrete and abstract syntax trees
- Terms
- Parsing
- Unparsing
- Pretty-printing
- Design a syntax definition for a tiny language and derive a parser and pretty-printer from it
- Assignment Program Representation
Extra: STC talk by Martin Bravenboer
- Thursday 11:00
- XML and term representation
Week 48
Lecture 3 : Term Rewriting
- Terms with variables
- Substitution
- Pattern matching
- Rewrite rules
- Rewriting
- Strategies for rewriting
- Applications: simplifying expressions, desugaring
- Develop a set of rewrite rules for simplification of expressions
- Assignment Term Rewriting
Lecture 4 : Concrete Syntax
- Concrete vs abstract syntax
- String-based vs structured generation and transformation
- Embedding concrete syntax in a meta-language
- Rewrite rules with concrete syntax
- Application: instrumentation, template-based generation
- Simplification rules with concrete syntax
- Assignment Concrete Syntax
Week 49
Lecture 5 : In Control of Rewriting
- Limitations of rewriting: non-termination, non-confluence
- Control over application of rules
- Traversal overhead
- Separation of rules and strategies
- Idioms for program transformation with strategies
- Application: staged simplification
- Learn to use the Tiger-Front environment
- Compare writing a function to using a strategy
- Assignment In Control of Rewriting
Lecture 6 : Composing Strategies
- Combinators for composing strategies
- Sequential composition, choice, recursion, ...
- Data-type specific traversal with congruence operators
- Strategic programming
- Application: evaluation using control-flow strategy
- Write strategies for traversing data-types
- Assignment Composing Strategies
Week 50
Lecture 7 : First-Class Pattern Matching
- Rules are not primitive
- Pattern matching
- Pattern construction
- Variable scope
- Derived operations
- Application: target-driven transformations
- Exercises with match and build
- Assignment First Class Pattern Matching
Lecture 8 : Generic Traversal Strategies
- Generic traversal combinators
- Generic traversals
- Generic term deconstruction
- Type unifying strategies
- Applications: rewriting strategies, analyses
- Exercises with generic traversal
- Assignment Generic Traversal Strategies
Week 51
Lecture 9 : Scoped Dynamic Rewrite Rules
- Context-sensitive rewriting
- Introduction and use of dynamic rules
- Dynamic rule scope
- Applications: renaming, inlining, dead-code elimination, evaluation
Lecture 10 : Introduction to Partial Evaluation
- Program specialization or partial evaluation
- Binding time
- Binding time annotations
- Specialization
- Binding time analysis
First Exam
- Topic: week 47 to 50
Vacation
Week 2
Lab : Develop a partial evaluator for Tiger
The lab in the remainder of the course is dedicated to building a partial evaluator for Tiger.Lecture 11 : Constant Propagation
- Constant folding
- Constant propagation
- Other data-flow optimizations
Lecture 12 : Online Partial Evaluation
- Combining inlining and constant propagation
Week 3
Lecture 13 : Binding-time Annotations
- Binding-time annotations
- Function specialization
Lecture 14 : Binding-time Analysis
- Binding-time analysis
Week 4
The transformation techniques introduced in this course are also applicable to transformation of structured data.Lecture 15 : XML Generation
- XML and ATerms
- Interpretation and validation
- Template-based data generation
Lecture 16 : XML Transformation
- Transformation of structured documents
- Use of strategies
Week 5
Second Exam
- Topic: week 51 to 4