Programming Languages

Functional Programming with Effects

This is a MSc-level seminar but we also welcome interested BSc students.

Purely functional programs don’t allow side-effects like reading or writing from the console (or network), mutable state, or exceptions. How then can those languages be used to solve real world problems?

In this seminar, we will cover various techniques to structure and program with effectful functional programs. Participants will learn the foundations of computational effects like monads, arrows, and applicatives. Explicitly structuring programs with computational effects opens up the possibility for equational reasoning. Participants will learn how to instantiate those general concepts for particular use cases like parsing or functional reactive programming.

Entry in the Campus system: Link

Registration Closed

The registration for the seminar is now closed. We will meet weekly on Thursdays, 16:00-17:45, C215 Sand.

First Meeting

We will have our first meeting on Monday April 15 at 17:00 in room A302 (Sand).

The slides of the first meeting.

Course Requirements

There are no formal requirements. However, having attended some of the following lectures greatly helps to understand the papers more easily:

Most of the papers use the programming language Haskell or similar functional programming languages. It is thus also very helpful to have some prior exposition to functional programming (and to Haskell) as provided by the lecture Functional Programming (by the group of Torsten Grust).

Instructor

Jonathan Brachthäuser
Alumni
Jonathan Brachthäuser
(Office: Room B213, Sand 13)

Seminar Structure

This seminar will be conducted as a paper reading group with weekly meetings.

Each week one of the students is the discussion leader, who familiarizes herself/himself with the paper’s content in greater depth. The other participants should also read the paper, prepare questions, and send them to the discussion leader.

During the session, the discussion leader will summarize the main points of each section, be ready to answer the other participants’ questions, keep the discussion on track, and point out additional insights gained by her/his in-depth preparation.

At the end of the semester, each participant will write a term paper on the topic she/he prepared as discussion leader. It is also possible to accompany this with some artefact, e.g. a mini software project, that showcases practical applications discussed in the term paper.

Other Informations

Discussion Language: English or German (depending on participants)
Paper Language: English
Credits: 3 LP (new PO), 4 LP (old PO)
Weekly meetings: To be determined
Kick-off meeting: To be determined

Information on Reading Papers

In preparation for the seminar, we highly recommend to read the following short papers:

Literature

The following is a preliminary list of papers you can choose from. Note that you need to be in the university network (or VPN) to access some of the papers as PDF. If you can’t find the PDFs you can also try searching on Google-Scholar.

Tentative Schedule

02.05.

Monads for Functional Programming

Philip Wadler. Advanced Functional Programming (1995).

Introduces monads as program structuring technique

Paper (Springer)

09.05.

What we talk about when we talk about monads

Tomas Petricek. Programming Journal, 2018.

A survey paper about monads

Paper (Programming)

16.05.

Monad Transformers and Modular Interpreters

Sheng Liang, Paul Hudak and Mark Jones. POPL (1995).

Introduces monad transformers

Paper (ACM)

23.05.

Generalizing Monads to Arrows

John Hughes. Science of Computer Programming (2000).

Introduces Arrows

Paper (Elsevier)

06.06.

Freer monads, more extensible effects

Oleg Kiselyov and Hiromi Ishii. Proc. of Haskell Symposium (2015).

Introduces free monads in multiple variations

Paper (ACM)

27.06.

Type directed compilation of row-typed algebraic effects

Daan Leijen. Symposium on Principles of Programming Languages (2017).

We read Sections 1, 2 and 4. Section 4 should be understood as a reference, not as an introduction.

Paper (ACM)

04.07.

Programming with Implicit Values, Functions, and Control (or, Implicit Functions: Dynamic Binding with Lexical Scoping)

Jonathan Brachthäuser, Daan Leijen. MSR-TR-2019-7

We read Sections 1 and 2

Paper (Microsoft Research)

11.07.

Applicative programming with Effects

Connor McBride, Ross Paterson. Journal of Functional Programming (2008).

Introduces applicatives / idioms

Paper (JFP)

18.07.

Algebraic Effects and Effect Handlers for Idioms and Arrows

Sam Lindley. Workshop on Generic Programming (2014).

We focus on Sections 1, 2, and 6. Note, that for 6 it is necessary to have (at least) a basic understanding of 3-5.

Paper (ACM)

TBD

Monadic Parsing in Haskell

Graham Hutton, Erik Meijer. Journal of Functional Programming (1998).

Uses monads to write parsers

Paper (JFP)

TBD

Profunctor Optics

Matthew Pickering, Jeremy Gibbons and Nicholas Wu. Programming Journal (2017).

Use arrow like structures to express optics

Paper (Programming)

TBD

Arrows, Robots, and Functional Reactive Programming

Paul Hudak, Antony Courtney, Henrik Nilsson and John Peterson. In: Advanced Functional Programming (AFP): 4th International School, 2002.

Paper (Springer)

TBD

The Essence of the Iterator Pattern

Jeremy Gibbons and Bruno Oliveira. Journal of Functional Programming (2009).

Shows that applicatives capture the essence of iterators

Paper (JFP)

TBD

Monoids: Theme and Variations (Functional Pearl)

Brent Yorgey. Haskell Symposium (2012).

Shows how to construct a library for diagrams using monoids

Paper (ACM)

TBD

An idiom's guide to formlets

Ezra Cooper, Sam Lindley, Philip Wadler and Jeremy Yallop. Technical Report (2008)

Uses idioms to model forms on webpages

Paper (PDF)

TBD

The F# Computation Expression Zoo

Tomas Petricek and Don Syme. PADL (2014).

Introduces notation for monadics, applicatives and more in F#

Paper (PDF)

TBD

Idioms are Oblivious, Arrows are Meticulous, Monads are Promiscuous

Sam Lindley, Philip Wadler and Jeremy Yallop. Mathematically Structured Functional Programming (2008).

Show that idioms embed into arrows and arrows embed into monads.

Paper (Elsevier)