Functional Programming WS 2009/10

Functional Programming

(V3 resp. 4 + Ü2, WS 2009/10)

Type	Times/Room	Instructor
Lecture (3 / 4)	Tue 11:45 - 13:15 AH 3	Prof. Dr. Jürgen Giesl
	Fri 11:45 - 13:15 AH 1
Exercise (2)	Wed 16:00 - 17:30 AH 3	Prof. Dr. Jürgen Giesl & Carsten Fuhs

The lecture has 3 hours per week for students in Bachelor Informatik and Master Informatik. It has 4 hours per week for students in Diplom Informatik, Diplom Mathematik, and Master of Software Systems Engineering (see below for details).

News

The (solved) exams of February 24, 2010 and March 19, 2010 are now available for download.
Students in a Diplom program who obtained an exercise certificate (Übungsschein) can retrieve their certificate at our secretary's office (room 4213).
Exam inspection: The inspection for the exam of March 19, 2010 will take place in room 4201b (seminar room of i2) in the computer science building at Ahornstr. 55 on March 25 between 9:30 and 10:30. For the inspection of the exam, you must provide a corresponding student ID and a passport/national ID card/... with a photo. Obvious correction mistakes (like incorrectly summed up points) will be corrected immediately. For other correction mistakes, the student must hand in a written request why he/she disagrees with the correction. Then the corresponding parts of the exercise that are mentioned in the request will be graded anew. As soon as all requests have been processed, the updated results will be announced on this web page.
The results of the exam written on March 19 are available now. The mapping from points to grades is as follows:

points grade

55.5 - 58 1.0
52.5 - 55 1.3
49.5 - 52 1.7
46.5 - 49 2.0
43.5 - 46 2.3
40.5 - 43 2.7
37.5 - 40 3.0
34.5 - 37 3.3
31.5 - 34 3.7
29 - 31 4.0
0 - 28.5 5.0
The written exam on March 19, 2010 will begin at 14:30 in the afternoon and take two hours. The exam will take place in the computer science building at Ahornstr. 55 in lecture hall AH 5. Please also have a look at the information given earlier on the exam.
The exam of February 24, 2010 and a solution are now available for download.
The results of the exam of February 24, 2010 after the inspection are now available.
Exam inspection: You can inspect your exam on Thursday, March 4, 14:00 - 16:00 in room 5054 in the computer science building at Ahornstr. 55. To avoid unnecessary waiting times, we are scheduling the inspection for the different versions of the exam as follows:
- V4 and V3M: 14:00 - 15:00
- V3B: 15:00 - 16:00
For the inspection of the exam, you must provide a corresponding student ID and a passport/national ID card/... with a photo. Obvious correction mistakes (like incorrectly summed up points) will be corrected immediately. For other correction mistakes, the student must hand in a written request why he/she disagrees with the correction. Then the corresponding parts of the exercise that are mentioned in the request will be graded anew. As soon as all requests have been processed, the updated results will be announced on this web page.
The results of the exam written on February 24 are available now. The mapping from points to grades is as follows:

points grade

53.5 - 56 1.0
50.5 - 53 1.3
47.5 - 50 1.7
44.5 - 47 2.0
41.5 - 44 2.3
38.5 - 41 2.7
35.5 - 38 3.0
33 - 35 3.3
30.5 - 32.5 3.7
28 - 30 4.0
0 - 27.5 5.0
The written exam on February 24, 2010 will begin at 9:30 in the morning and take two hours. The exam will take place in the computer science building at Ahornstr. 55. The room where you write the exam depends on the version of the lecture that you have attended. The distribution of students to rooms is as follows:
- V4 (Master of Software Systems Engineering): AH 5
- V3B (Bachelor of Computer Science - Wahlpflicht and Master of Mathematics): AH 4
- V3M (Master of Computer Science and Bachelor of Computer Science - for Master's studies): AH 6
Please also have a look at the information given earlier on the exam.
The list of students who have obtained the qualification for the final exam in February/March or for the "Übungsschein" is now online. Please check if you are on this list!
Below we have compiled some information and old exams that may be helpful to prepare for the final written exam.
The absolute number of exercise points needed to qualify for the final exam/to obtain the "Übungsschein" (i.e., 50% of the total points obtainable in the exercises for the corresponding version of the lecture) is now known:
- V3B: 74 points
- V3M: 72.5 points
- V4: 87 points
Note that the percentages given in the exercise management system refers to the points that could be obtained in the exercises for the V4 version of the lecture. Thus, if you are not attending the V4 version, these percentages do not apply to you. Instead you should check whether your score (after Sheet 13) is at least at high as given above.
After correction of Sheet 13, we are going to put a list on this page which contains the matriculation numbers of the students who have qualified for the exam/who have obtained the "Übungsschein". Note that if you have registered for the exam and then also qualify for the exam, this means that you are expected to participate in the exam (i.e., not coming to the exam then counts as a "fail")! Therefore, if you have registered for the exam, you should check in any case whether your matriculation number appears on this list. If however you do not qualify for the exam, you will be deregistered from the exam automatically.
All students except "Diplom" students should register for the written exam on February 24, 2010. To do this, please proceed as follows:
- Master Informatik, Master Mathematik: Please register via Campus and use the "modulares Anmeldeverfahren". Registration is possible from November 1 - November 27, 2009.
- Bachelor Informatik, Master SSE: Please register via the ZPA or the VZPA. If you do it via VZPA, it is possible from December 1 - December 18, 2009.
- Bachelor Informatik attending the "Master Course": Please register by sending an e-mail to Carsten Fuhs until December 18, 2009.
The final exam for the lecture will be a written exam for all students except those studying in a "Diplom" program. For "Diplom" students, the graded exam is oral.
The date for the written exam will be February 24, 2010. If you fail this exam, there is a second written exam to repeat it on March 19, 2010.
Students of "Diplom Informatik" and "Diplom Mathematik" can obtain a certificate of successful participation in the exercises ("Übungsschein"). For this, you have to score at least an overall 50% of the total points in the exercises. If you fulfill this criterion, you can get your certificate at our secretary's office after the last exercise sheet has been corrected. Note that this semester we do not require an explicit final exam for this certificate.

points	grade
55.5 - 58	1.0
52.5 - 55	1.3
49.5 - 52	1.7
46.5 - 49	2.0
43.5 - 46	2.3
40.5 - 43	2.7
37.5 - 40	3.0
34.5 - 37	3.3
31.5 - 34	3.7
29 - 31	4.0
0 - 28.5	5.0

points	grade
53.5 - 56	1.0
50.5 - 53	1.3
47.5 - 50	1.7
44.5 - 47	2.0
41.5 - 44	2.3
38.5 - 41	2.7
35.5 - 38	3.0
33 - 35	3.3
30.5 - 32.5	3.7
28 - 30	4.0
0 - 27.5	5.0

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.

References

P. Thiemann: Grundlagen der funktionalen Programmierung, Teubner, 1994.
A. Field, P. Harrison: Functional Programming, Addison-Wesley, 1988.
C. Reade: Elements of Functional Programming, Addison-Wesley, 1989.
R. Bird: Introduction to Functional Programming using Haskell, Prentice Hall Press, 1998.
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, Addison-Wesley, 1999.
S. Peyton Jones: The Implementation of Functional Programming Languages, Prentice Hall, 1987.
J. Loeckx, K. Sieber: The Foundations of Program Verification, Wiley-Teubner, 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 foreign-language calls in Haskell, Marktoberdorf Summer School 2000. (Available from http://research.microsoft.com/users/simonpj/papers/marktoberdorf)

Here is a short overview on the correspondence of the material in the lecture to material in the books mentioned above. However, the material is not identical to the one in the books.

Chapter 1.1- 1.3 of the lecture corresponds to Chapters 2-7 of Thiemann's book. A good source for an introduction to Haskell is also the book by Bird.
Chapter 1.4 of the lecture corresponds to Chapter 10 in Bird's book and Chapter 18 in Thompson's book.
Chapter 2.1 of the lecture corresponds to Chapter 3.3 and 4 in the book by Loeckx and Sieber.
Chapter 2.2 of the lecture corresponds to Chapter 10 and 12.2 in Reade's book.
Chapter 3 corresponds to Chapter 12 of Reade's book. Additional material can be found in Chapter 15 of Thiemann's book and Chapter 6 and Appendix B and C of the book by Field & Harrison.
Chapter 4 corresponds to Chapter 7 of Field & Harrison's book. Additional material can be found in Chapter 15.4 and 15.5 of Thiemann's book and Chapter 11 of the book by Reade.

Versions of the Lecture

Not all material of the lecture is needed for all students. More precisely, there are three versions of the lecture:

V4 This version contains the full lecture (with 4 hours per week). It is relevant for students in Diplom Informatik, Diplom Mathematik, and Master of Software Systems Engineering.
V3B This version only contains a subset of the full lecture (with 3 hours per week). It is relevant for students in Bachelor Informatik and Master Mathematik. Compared to V4, the following material is missing in V3B:
- Section 1.4 (Monads)
- Section 2.2.3 (Semantics of complex Haskell programs)
- Section 4.3 (Type inference for Haskell programs)
V3M This version only contains a subset of the full lecture (with 3 hours per week). It is relevant for students in Master Informatik. This is also the version that is relevant for those students in Bachelor Informatik who already want to attend the master-version of this course (they can transfer the credits obtained here as soon as they enter the master program). Compared to V4, the following material is missing in V3M:
- "Operators and infix declarations" (in Section 1.1)
- "List comprehensions" (in Section 1.2)
- "Cyclic data objects" (in Section 1.3)
- Section 1.4.2 (Programming with monads)
- "Transformation rules (10)-(12)" (in Section 2.2.3)
- Section 3.4 (Pure lambda calculus)
- "Compilation of Haskell" (in Section 4.3)

Area

Theoretical Computer Science, Area of Specialization

Old Exams and Important Topics

As already announced above, the date for the written exam will be February 24, 2010. If you fail this exam, there is a second written exam to repeat it on March 19, 2010. As for the lecture, there will be three corresponding versions of the final written exam (V4, V3B, V3M). The exam will be closed book (i.e., no additional material is allowed). You will only need to bring a pen/biro, your student ID and a passport/ID card to the exam. For all versions, the exam is scheduled to take 120 minutes. We consider especially the following topics to be important for the exam:

Programming in Haskell
- Higher-order functions
- Infinite data objects
- Monads (especially the IO monad) -- not for V3B; note that V3M did not cover Sect. 1.4.2
- Infix operators -- not for V3M
- List comprehensions -- not for V3M
- Cyclic data objects -- not for V3M
Determining the domain for a given data type
Determining the denotational semantics of a Haskell function
- Determining the corresponding higher-order function ff for a given Haskell function f, such that lfp(ff) is the semantics of f
- Determining the least fixpoint of this higher-order function ff (by giving ffⁱ(bot) for all natural numbers i and the least upper bound of the corresponding chain)
Proofs in the area of denotational semantics
Determining an equivalent simple Haskell program for a given Haskell program (but it does not matter how you construct the simple Haskell program, i.e., you do not need to use the transformation rules from the lecture) -- not for V3B
Determining an equivalent lambda-term for a given simple Haskell program
Type checking for the lambda-calculus using the W-algorithm

Due to recent changes in the computer science curriculum, before this semester 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. 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 90 minutes).

Exercise Certificate Exam Functional Programming 2005 ps, pdf / Solutions ps, pdf
Exercise Certificate Exam Functional Programming 2007 ps, pdf / Solutions ps, pdf

The exams of this semester are now both available for download. They took 120 minutes each.

Exam February 24, 2010 V3B, V3M, V4 / Solutions V3B, V3M, V4
Exam March 19, 2010 V3B, V3M, V4 / Solutions V3B, V3M, V4

Haskell

In the course, we use the functional programming language Haskell. Information on Haskell as well as (free) interpreters and compilers can be found on the Haskell home page haskell.org. To learn Haskell, we recommend the Haskell interpreter Hugs.

Transparencies

Here are the transparencies used in the lecture.

Transparency 1 (October 16, 2009) ps, pdf
Transparency 2 (October 16, 2009) ps, pdf
Transparency 3 (October 20, 2009) ps, pdf
Transparency 4 (October 23, 2009) ps, pdf
Transparency 5 (October 30, 2009) ps, pdf
Transparency 6 (November 4, 2009) ps, pdf
Transparency 7 (November 6, 2009) ps, pdf
Transparency 8 (November 10, 2009) ps, pdf
Transparency 9 (November 17, 2009) ps, pdf
Transparency 10 (November 27, 2009) ps, pdf
Transparency 11 (November 27, 2009) ps, pdf
Transparency 12 (December 1, 2009) ps, pdf
Transparency 13 (December 4, 2009) ps, pdf
Transparency 14 (December 8, 2009) ps, pdf
Transparency 15 (December 15, 2009) ps, pdf
Transparency 16 (December 15, 2009) ps, pdf
Transparency 17 (December 18, 2009) ps, pdf
Transparency 18 (December 18, 2009) ps, pdf
Transparency 19 (January 8, 2010) ps, pdf
Transparency 20 (January 15, 2010) ps, pdf

Disclaimer

Research Group Computer Science 2

Dept. of Computer Science