Graduate course: Introduction to Rewriting Systems

  Introduction to Rewriting Systems (TDDB40)

Teacher: Jan Maluszynski

The Objectives
The Organization
The Schedule.
The Literature
The Contents
The Examination
The Seminars
Actual Information, Mid-term course evaluation

The Objective

Any kind of computation can be seen as a rewriting process. The aim of the course is to give a uniform view of various rewriting systems and in this way provide a unified basis for studying and classifying various computing paradigms. The 2003 edition of the course will:

present basic concepts of rewriting, in particular of term rewriting. The concepts, discussed in these lecture notes, will be subject of the lectures and the familiarity with them will be checked by the obligatory homework assignments. The problems of the homework assignments are to be solved individually by each student and delivered by the deadlines, as the necessary examination requirement.
survey selected rewriting-based programming languages and systems in the form of seminar presentations prepared by the students and based on web-accessible materials linked from the course web page.

The Organization

In the 2003 edition the course will include lectures by Jan, discussion sessions, and 45 min seminars given by the students, as a part of the examination.

The Literature

Basic

Johan Boye, Jan Maluszynski Rewriting Systems Lecture Notes 2003

A very few selected sections from:
Claude and Helene Kirchner Rewriting Solving Proving (.ps)
The preliminary version of this monograph is available on the web.

Other

Franz Baader and Tobias Nipkow Term Rewriting and All That
This is a popular textbook published 1998. Its web page includes ML programs for finding critical pairs, constructing completion, etc..

There is a lot of interesting material on the Rewriting Home Page

Slides of the lectures

Seminar Slides

Curry Part 1.
Curry Part 2.
Haskell .
ASF-SDF .
ELAN .

The Seminars

A part of the course program will be covered in the form of seminars. The seminars will survey programming languages and systems based on/using rewriting techniques. The seminars will be prepared by groups of the students, with 45 minutes presentation by a group. The slides in .pdf or .ps form should be e-mailed to Jan at latest on the day preceding your seminar. Delivery of the slides and their oral presentation is a part of the examination requirement.

The objective of each presentation is:

To give a brief introduction to the language/system
To discuss how the language/system is related to rewriting

All students have to read the seminar material before each seminar and to participate in the discussion. The languages/systems in question include

Curry
- November 24, 15.15: Seminar 1 (Tord, Joakim H., Anders); 16.15: Seminar 2 (Mikael K., Joe, Mikael C.)
  Recommended Material:
  - Curry Tutorial and Tutorial Slides .
  - Definitional Trees and Needed Narrowing
  Topics:
  - General introduction with examples,
  - Defining and using data types (Relation to Algebraic Specifications), Examples,
  - Functional Programming in Curry (Relation to Term Rewriting, Conditional TRS), Examples,
  - Constraints and Functional Logic Programming (Relation to Narrowing), Examples,
  - Definitional trees, what they are for. Flex and Rigid operators.
- November 27, 15.15: Guest seminar , Bldg. E, Room Alan Turing
  Professor Michael Hanus (Kiel), Declarative Multi-paradigm Programming in Curry
Haskell ,
- December 1, 15.15: Seminar 3 (Anders, Elmir); 16.15: Seminar 4 (Antoine, Francisco, Egil);
  Recommended Material:
  - Haskell Tutorial ,
  Topics:
  - General introduction with examples,
  - Defining and using data types (Relation to Algebraic Specifications), Examples, Compare to Curry.
  - Defining and using Functions; Patterns, Infinite Data Structures, (Relation to Term Rewriting),Examples.
  - Type Classes, Examples
  - Monads
ASF+SDF
- December 4: Seminar 5 (Marcus, Albert), 13.15-14
  Recommended Material:
  - Arie van Deursen, An Overview of ASF+SDF not available on the web, in collection A. Deursen, J. Heering, P.Klint(eds) Language Prototyping World Scientific 1996, available in the library
  - Term Rewriting for Sale
  Topics:
  - Overview of ASF+SDF, the roles of ASF and SDF (Relation to Term Rewriting) Example(s)
  - Industrial Applications
ELAN
- December 4: Seminar 6 (Robin, Ingemar, Joakim M.), 14.15-15
  Recommended Material:
  - An Overview of ELAN
  - ELAN:A logical framework
  Topics:
  - Overview of ELAN, (Relation to Term Rewriting) Example(s)
  - Defining Strategies in ELAN
  - Applications
XSLT: a transformation language for XML documents
- December 9: Seminar 7 (Vlad), 10.15. Part 2 of the meeting will be devoted to the summary of the course and discussion.
  Recommended Material:
  - A semantics of XSLT patterns by P. Wadler
  - Semantics of XSLT in ELAN by C. Kirchner et al.
  Topics:
  - What kind of terms are XML documents?
  - Subterm selection with XPath
  - Rewriting XML with XSLT (Relation to TRS?)

The Contents

Abstract Rewriting Systems,
Computations as rewriting.
Term rewriting systems.
Termination proofs.
Equational logic and rewriting techniques.
E-Unification
Integration of functional and relational languages.
Selected rewriting-based languages/systems (seminars)

The Examination:

Two homework assignments:
- Batch 1: deadline Nov.17
- Batch 2: deadline December 4.
presentation at ONE seminar, with slides delivered in .pdf or .ps (group work).
participation in the final meeting, ready for presenting a solution to any of the homework problems.

Actual Information

Closing Meeting
The closing meeting : discussion of the solutions of the examination problems and course summary;
also a possibility for individual discussions.
Room Alan Turing, bldg. E Tuesday, Dec. 16 at 15.15

Homework 2: Deadline December 4.

Mid-term course evaluation (week 45)

Number of muddy cards received: 12

Positive Comments

Interesting/very interesting subject (5)
Good literature (2)
Lectures OK/interesting/good (3)
Exam as home assignments is good (2)

Negative coments/suggestions for change

Lectures unstructured/difficult to follow (3)
Lectures too slow sometimes(1)
The students should speak up more often (1)
Fonts on the slides too small (1)
Muddy card evaluation done too early (1)
More lambda calculus was promised in the course description (1)
(was it?) To cover more lambda calculus one has to remove something else.
Would be nice to have a part on automatic theorem proving (1)
Late start with almost all of first week lost (1)
Would be nice to be able to buy printed lecture notes (1)
IDA website says that the course is undergraduate, the course home page says that it is graduate (1)
It is an advanced course offered for senior C-line students and people with equivalent background. I believe that this information is clear at both sites.

Thanks for your comments. Both the positive and the negative ones are great support/help in my work. I will be trying to improve as much as I can. Some of the comments may influence the next edition of the course (if there will be one) in year 2005.

Updated: December 11, 2003