Functional Programming
(V3 + Ü2, SS 2016)


News
Course of Studies
This lecture is suitable for the following students:
 Bachelor Informatik
 This course can be attended as
a "BachelorWahlpflichtveranstaltung" (Theory) for students of Bachelor Informatik.
 Already as a student of
Bachelor Informatik, it is also possible to attend this course as a "Master lecture"
and to transfer the credits afterwards when enrolling in
the Master Informatik program.
 Master Informatik
 Master Software Systems Engineering (as a Core Subject in Theoretical
Foundations of SSE)
 Master Mathematik
Contents
The course gives an introduction to functional programming
using the language Haskell. Moreover, we will discuss
models for the semantics and the implementation of
functional languages. This also includes techniques for
type checking and type inference.
Language
The course is given in English.
Course Notes
The course notes are available here (in German): Course Notes (version
of May 30, 2016)
You can also find
inofficial video
recordings of the lecture in 2012 provided by Fachschaft I/1 MPI.
Area
Theoretical Computer Science
Haskell
In the course, we use the functional programming language Haskell. Information
on Haskell can be found on the Haskell home page www.haskell.org.
To interpret or compile Haskell programs, one can use the Glasgow Haskell Compiler (GHC). For the lecture, we recommend the interactive mode of the GHC (called GHCi). To this end, we recommend to download the Haskell Platform.
References
 P. Thiemann: Grundlagen der funktionalen Programmierung, Teubner, 1994.
 A. Field, P. Harrison: Functional Programming, AddisonWesley, 1988.
 C. Reade: Elements of Functional Programming, AddisonWesley, 1989.
 R. Bird: Thinking Functionally With Haskell,
Cambridge University Press, 2014.
 P. Pepper: Funktionale Programmierung, Springer, 2002.
 M. M. T. Chakravarty, G. C. Keller: An Introduction to Computing With
Haskell, Pearson, 2002.
Also appeared as "Einführung
in die Programmierung mit Haskell", Pearson, 2004.
 S. J. Thompson: Haskell: The Craft of Functional Programming, AddisonWesley, 2011.
 G. Hutton: Programming in Haskell, Cambridge University Press, 2007.
 B. O'Sullivan, J. Goerzen: Real World Haskell, O'Reilly, 2010.
 S. Peyton Jones: The Implementation of Functional Programming Languages, Prentice
Hall, 1987.
 M. Lipvaca: Learn You a Haskell for Great Good, No Starch Press, 2011.
 J. Loeckx, K. Sieber: The Foundations of Program Verification, WileyTeubner, 1987.
 S. Peyton Jones (ed.): Haskell 98 Languages and Libraries: The Revised Report.
Cambridge University Press, 2003. (Available from http://haskell.org/onlinereport/)
 S. Peyton Jones: Tackling the Awkward Squad: monadic input/output,
concurrency, exceptions, and foreignlanguage calls in Haskell, Marktoberdorf
Summer School 2000. (Available from http://research.microsoft.com/users/simonpj/papers/marktoberdorf)
The exercises have to be solved in groups of four.
50% of the points on the exercise sheets are needed in order to take part in the final exam.
In order to take part in the exercises, please sign
up here.
The exercise sheets can be downloaded here.
Transparencies
Here are the transparencies used in the lecture.
 Transparency 1 (April 13, 2016)
 Transparency 2 (April 13, 2016)
 Transparency 3 (April 13 + 19, 2016)
 Transparency 4 (April 19, 2016)
 Transparency 5 (April 20, 2016)
 Transparency 6 (April 26, 2016)
 Transparency 7 (April 27, 2016)
 Transparency 8 (May 3, 2016)
 Transparency 9 (May 4, 2016)
 Transparency 10 (May 10, 2016)
 Transparency 11 (May 11 + 24, 2016)
 Transparency 12 (May 24 + 25, 2016)
 Transparency 13 (May 31, 2016)
 Transparency 14 (May 31 + June 1, 2016)
 Transparency 15 (June 7, 2016)
 Transparency 16 (June 8, 2016)
 Transparency 17 (June 8, 2016)
 Transparency 18 (June 14, 2016)
 Transparency 19 (June 21, 2016)
Here are the notes from the lecture.
 0. Motivation (April 13, 2016)
 1.1.1 Declarations (April 13 + 19, 2016)
 1.1.2 Expressions (April 19, 2016)
 1.1.3 Patterns (April 19 + 20, 2016)
 1.1.4 Types (April
20 + 26, 2016)
 1.2 HigherOrder Functions (April
27 + May 3, 2016)
 1.3 Programming with Lazy Evaluation (May 3,
2016)
 1.4 Monads (May 4,
2016)
 2.1.1 Partially Defined Values (May 10,
2016)
 2.1.2 Monotonic and
Continuous Functions (Part 1) (May 10 + 11, 2016)
 2.1.2 Monotonic and
Continuous Functions (Part 2) (May 24, 2016)
 2.1.3 Fixpoints (May 24 + 25, 2016)
 2.2.1 Construction of Domains (May 25 + 31, 2016)
 2.2.2 Semantics of
Simple Haskell Programs (May 31 + June 1, 2016)
 2.2.3 Semantics of
Complex Haskell Programs (June 1 + 7 + 8, 2016)
 3.1 Syntax of the Lambda Calculus (June 8, 2016)
 3.2 Semantics of the Lambda
Calculus (June 8 + 14, 2016)
 3.3 Reducing Haskell to the Lambda Calculus (June 14 + 15, 2016)
 3.4 The Pure Lambda Calculus
(June 15 + 21, 2016)
 4.1 Type Schemas and Type Assumptions (June 21, 2016)
 4.2 The Type Inference Algorithm (June 21 + 22, 2016)
There will be a written exam on
the lecture. It takes place on
August 17, 2016. The second written exam will take place on September 19, 2016.
Exam August 17, 2016 / Solutions
Exam September 19, 2016 / Solutions
To help you prepare, here are the exams used in previous semesters. Please note that there will not be different exams for bachelor and master students this year.
Each of these exams took 120 minutes. We put them online so that they can help you when you are preparing for the final exam. We strongly recommend you to solve these exams without looking at the solutions first! It is a good idea to solve these exams also under the conditions of the original exam (i.e., closed book and with a time limit of 120 minutes):
 Exam February 24, 2010 (V3B) / Solutions (V3B)
 Exam February 24, 2010 (V3M) / Solutions (V3M)
 Exam February 24, 2010 (V4) / Solutions (V4)
 Exam March 19, 2010 (V3B) / Solutions (V3B)
 Exam March 19, 2010 (V3M) / Solutions (V3M)
 Exam March 19, 2010 (V4) / Solutions (V4)
 Exam August 15, 2012 (V3B) / Solutions (V3B)
 Exam August 15, 2012 (V3M) / Solutions (V3M)
 Exam September 10, 2012 (V3B) / Solutions (V3B)
 Exam September 10, 2012 (V3M) / Solutions (V3M)
 Exam August 20, 2014 (V3B) / Solutions (V3B)
 Exam August 20, 2014 (V3M) / Solutions (V3M)
 Exam September 15, 2014 (V3B) / Solutions (V3B)
 Exam September 15, 2014 (V3M) / Solutions (V3M)
Due to changes in the computer science curriculum, before 2009 there have not been any written exams to determine the final grade for the course "Functional Programming". However, the following old exams were used in earlier semesters for the acquisition of the exercise certificate for students of "Diplom" curricula. Each of these exams took 90 minutes: