Datatype-generic programming (Seminar)

Sommer semester 2015

Organization

Instructor	Yufei Cai AlumniYufei Cai
Weekly meeting	Wednesday 14:15-16:00 in Sand 6/7, Room F 122 (kleiner Hörsaal).
Language	English
Credits	4 LP (Im Vorlesungsverzeichnis)

Description

From a bird’s eye, generic programming is about how programs can be similar to each other. By exploiting the similarities, programs become shorter and easier to write. This seminar focuses on program similarities due to algebraic datatypes in functional programming languages. Participants will learn new ways to write programs, practice high-level reasoning on programs, and gain understanding about design patterns in general. We will learn the following concepts and apply them to functional programming:

• Functors,
• Sum and product types,
• Algebras and coalgebras,
• Applicative functors and traversals.

Knowledge in Haskell is necessary to get the full benefit.

Process

The seminar consists of a series of weekly discussions followed by a programming project.

Phase 1: reading group

During this phase, we will read some paper sections or book chapters each week, and discuss together what we learnt from them. Participants will take turns being the discussion leader.

The discussion leader has these responsibilities during meetings:

1. Control the duration of discussions, interrupt people as necessary.
2. Summarize main points of each section.
3. Announce discussion topics related to the section.
4. Answer questions as much as possible.
5. Ask questions about things they do not understand.

Discussion participants have these responsibilities during meetings:

1. Ask questions about things they do not understand.
2. Answer questions as much as possible.
3. Offer any additional insight they may have.

Each week, discussion participants should submit discussion topics and questions to the discussion leader and me before Monday, 23:59:59.

Phase 2: final project

The final project is about learning one or more programming techniques in depth, and using them in practice. Each participants should give a presentation of their project and submit a short paper at the end of the semester.

Meetings

Final project

Apply a generic programming technique to a small program of your choosing. The goal of the project is to gain insights from using a technique in practice, not to produce perfect software. It should be something you can program in a weekend or less.

Deliverables

• 08.07.2015: Proposal. Email me a brief (1–2 paragraph) proposal for your project.

• 22.07.2015: Presentation. Give a 10-minute talk about your project in the seminar meeting.

• 31.07.2015: Document. Submit a short paper (around 1000 words) summarizing your project and what you learnt from it, especially insights that are not obvious from reading alone. Incorporate feedback about your presentation.

Proposal

The project proposal should answer the following questions.

• What technique will you implement?
• On which program will you apply the technique? It should be different from the example used in the paper.
• Why do you choose the technique? What do you hope to learn? (It is okay if you end up learning something else.)

If you plan to present on a notebook computer (recommended), please include in the email your display port (DVI, HDMI, VGA etc.) so that I can make sure it’s usable with the projector.

Presentation

The presentation is 10-minute long. There are 5 minutes afterwards for questions. The presentation should clarify the following:

• What is the problem you are trying to solve?
• What programming technique is your chosen solution?
• How does the technique solve the problem?
• What did you learn about the technique from using it?

Discussion candidates

• Gibbons. Datatype-generic programming. LNCS 4719.
• Gibbons. Design patterns as higher-order datatype-generic programs. WGP 2006.
• Gibbons and Oliveira. The essence of the iterator pattern. JFP 19.3-4, 2009.
• Hinze. Polytypic values possess polykinded types. LNCS 1837.
• Hinze and Jeuring. Generic Haskell: practice and theory. LNCS 2793.
• Hinze. Generics for the masses. JFP 16.4-5, 2006.
• Hinze. Generic programming with adjunctions. LNCS 7470.
• Lämmel and Peyton Jones. Scrap your boilerplate: a practical design pattern for generic programming. TLDI 2003
• Lipovača. Learn You a Haskell for Great Good!
• Meijer and Hutton. Bananas in space: Extending fold and unfold to exponential types. ICFP 1995.
• McBride and Paterson. Applicative programming with effects. JFP 18.1, 2008.
• Rodriguez Yakushev et al. Generic programming with fixed points for mutually recursive datatypes. ICFP 2009.
• Swierstra. Data types à la carte. JFP 18.4, 2008.