Capita Selecta Software Engineering & Technology (2IMP05)
Advanced Functional Programming

2023-2024 (Quartile Q4, time slot To Be Determined)

A N N O U N C E M E N T S
03-Sep-2022	The course will run again in 2023-2024 (Q4). Contact me to register.
2022-2023	One student did the course
2021-2022	The course ran in Q4, Timeslot A
26-Jun-2021	Mail sent to participants of the bachelor course 2IPH0.
17-Jun-2021	Course announced; details to follow. In case of interest, contact the lecturer.

Lecturer

Dr. ir. T. (Tom) Verhoeff (SET Cluster, T.Verhoeff@TUE.NL)

When and Where

Timeslot:

• To Be Determined

If multiple students want to do this course together, then my preference is for Q4 (though Q3, or even Q2 are discussable). The time slot is still open. For individual students there is a bit more room to negotiate a time window.

Prior knowledge

It is strongly recommended that you have done a bachelor course on Functional Programming, such as 2IPH0.

• Calculational style for proofs and program construction
• Currying, uncurrying, sectioning, point-free/point-wise
• Product and sum types, lists, polymorphic typing
• Function combinators (composition, split, case, product, sum)
• Recursive function definitions, tail/head recursion, accumulation, tupling
• Inductive and co-inductive types, functor, fold/unfold (a.k.a. cata/ana), fusion
• Working with Haskell (try your hand at some of the programming problems in Haskell on Codewars.com)

Possible Topics (in part, also your choice)

• Recursion schemes for inductive and co-inductive types
• Generalized Algebraic Data Types (GADTs)
• Techniques for defining co-data and proving their properties, including bisimulation:
  • As a starter, see: "Proof Methods for Corecursive Programs" by Jeremy Gibbons and Graham Hutton
• Monads and co-monads (and monadic parsers, parsing combinators)
  LINKS TO BE PROVIDED
  • Code ``monadification'' made easy, by José Oliveira
  • Maximum Segment Sum, Mondically by Jeremy Gibbons
  • Calculating a Backtracking Algorithm by Shin-Cheng Mu
  • Monadic Parser Combinators by Graham Hutton, Erik Meijer
  • Monadic parsing in Haskell by Graham Hutton, Erik Meijer
• Combining monads through monad transformers, left/right adjoints
  • Hierarchical Free Monads
• Super-naturals (lazy numbers), by Ralf Hinze and Colin Runicman, JFP 32, 2022.
• Efficient immutable data types (through sharing and lazy updating)
  • "Weaving a Web", by Hinze and Jeuring
  • Tying the Knot (also: how to deal with graphs that have cycles, i.e. are not trees)
• Reasoning about efficiency of programs under lazy evaluation
  • "Call-by-Need is Clairvoyant Call-by-Value", by Hackett and Hutton (2019)
• Relational Calculus, e.g., see
  • Part II of Program Design by Calculation by J.N. Oliveira
• Category theory for functional programming, e.g., see
  • Category Theory is Type Theory
  • A taste of category theory for computer scientists by Benjamin C. Pierce, 1988
  • Law and Order in Algorithmics, dissertation by Maarten Fokkkinga, 1992
  • Category Theory for Programmers by Bartosz Milewski (online and as PDF)
• Lambda calculus and combinatory logic
  • John's Lambda Calculus and Combinatory Logic Playground
• Functional languages and Domain-Specific Languages
  • Functional Programming for Domain-Specific Languages, by Jeremy Gibbons
  • Writing functional DSLs for business domains
• Semantics of functional languages
  • Denotational Semantics of Haskell
  • The Semantics of Programming Languages, by Carl Gunter, MIT Press, 1992 (at your own risk, try to download from vdoc.pub; recommended: in DjVu format, because that is much more compact and no conversion is needed; also available on Internet Archive for online reading)
  • The Semantics of Types in Programming Languages by Carl Gunter
• Efficient execution of functional languages (e.g. through graph reduction)
  • The Implementation of Functional Programming Languages, by Simon Peyton Jones (1987)
  • Implementing Functional Languages: a tutorial, by Simon Peyton Jones (1992)
  • Write You A Haskell: Building a modern functional compiler from first principles, by Stephen Diehl
  • Compiling with Continuations, by Andrew Appel, Cambridge Univ. Press, 1991
  • Ben Lynn's website; check out: Haskell, Compiler, and Lambda Calculus
  • "Lambda to SKI Semantically", by Kiselyov (2018); website by Oleg Kyselyov; especially see lambda to SKI: a different view on the old translation
• Binary Lamba Calculus and Binary Combinatory Logic
  • John Tromp
  • Binary Lambda Calculus and Combinatory Logic
  • AIT (Algorithmic Information Theory)
  • Lambda Calculus in 397 Bytes
• Applications of functional programming
  • Algorithm Design with Haskell by Richard Bird and Jeremy Gibbons, Cambridge Univesity Press, 2020 (available as ebook via TU/e library)
  • Dynamic Programming
    • Explainable Dynamic Programming, by Martin Erwig and Prashant Kumar (JFP 31, 2021)
  • Software Design in Haskell
    • Functional Design and Architecture, by Alexander Granin, Manning, 2021-2022
  • Functional Programming in Java
  • Large-scale design in Haskell

Educational Format

• Some lectures
• Joint reading and discussing of articles and programming problems
• Student presentations
• Programming challenges

Study Material

Various articles and book chapters.