# AoP

During study period 4 (end of March to beginning of June 2008) Patrik Jansson led a 7.5hp (research level) seminar course on "Algebra of Programming" centered around the book by Bird & de Moor. (Undersidor är skyddade av lösenord (driB baklänges) för att undvika spam.)

## Course outline

- Topic
- Algebra of Programming
- Examiner
- Patrik Jansson
- Credits
- 7.5hp
- First meeting
- Wed. 080319, 10.00-12.00 in room EDIT 6128
- Meetings
- See the Sem 1 notes.
- Google group
- Join http://groups.google.com/group/aop2008
- Literature
- The book "Algebra of Programming" and a selection of related research papers
- Participants
- AoP.Participants - add your name to the list if you intend to follow the course

## Content

From the preface of the AoP book:

This is the TOC from the AoP book: 1. Programs 2. Functions and Categories 3. Applications 4. Relations and Allegories 5. Datatypes in Allegories 6. Recursive Programs 7. Optimization Problems 8. Thinning Algorithms 9. Dynamic Programming 10. Greedy Algorithms

## Audience

This is copied verbatim from the preface:

"The book is addressed primarily to the mathematically inclined functional programmer, though the non-functional – but still mathematically inclined – programmer is not excluded. Although we have taken pains to make the book as self-contained as possible, and have provided lots of exercises for self-study, the reader will need some mathematical background to appreciate and master the more abstract material. A first course in functional programming will help quite a lot, since many of the ideas we describe can be found there in more concrete clothing. Prior exposure to the basic ideas of set theory would be a significant bonus, as would some familiarity with relations and equational reasoning in a logical calculus. The bibliographical remarks at the end of each chapter describe where appropriate background material can be found."

## Examination

Each student should

- A: (10h) do a literature search to identify ten suitable research papers connecting AoP to his or her own research interests. Deliverable: (by week 17) a BibTeX-file with the citations + a memo citing them including a one-paragraph per paper explanation of the connection.
- B: (10h) identify one or two (of the above) papers as suitable reads for the whole group. Deliverable: (by week 17) A one-page summary connecting the paper to the AoP theme.
- C: (80h) read the book sections and identified "suitable reads" papers. Deliverable: active participation in the seminar discussions.
- D: (20h) host one or two of the weekly seminars. Deliverable: a tutorial-style .pdf-slideshow of (some of) the material in the part of the book scheduled for that seminar. Presentation time, 45 min.
- E: (70h) perform a case-study or implementation project. Deliverable: (by week 22) a "workshop paper" or well documented source code.
- F: (10h) review the case-study / project of one other participant. Deliverable: (by week 23) a one-page review of the strengths and weaknesses of the deliverable E from the other participant.

## Schedule and assigment of seminars to participants:

See Sem 1 for details.

Ten seminars:

- Week 12: Ch. 1: Programs: Intro + planning meeting
- Week 14: Ch. 2: Functions and Categories
- Week 15: Ch. 3: Applications
- Week 16: Ch. 4: Relations and Allegories
- Week 17: Ch. 5: Datatypes in Allegories, (hand in deliverable A and B before this meeting)
- Week 19: Ch. 6: Recursive Programs
- Week 20: Ch. 7: Optimization Problems
- Week 21: Ch. 8: Thinning Algorithms
- Week 22: Ch. 9: Dynamic Programming, hand in deliverable E before this meeting
- Week 23: Ch. 10: Greedy Algorithms, hand in deliverable F before this meeting

## Selected Papers

Selected papers and their relationship to the AoP theme will be listed here.

## Links:

- Agda Standard Library
- AoPA: Parts of AoP implemented in the proof system Agda
- AoP 2004 Chalmers instance: http://www.cs.chalmers.se/~ulfn/aop/
- http://lambda-the-ultimate.org/node/1117
- http://courses.cs.ut.ee/2006/algebraofprog/Main/HomePage
- http://www.cs.ru.nl/E.Poll/papers/reviewAoP.ps.gz
- http://vl.fmnet.info/phiscs/
- AoP book: Print on demand: http://www.pearsoned.co.uk/Bookshop/detail.asp?item=100000000010900