|
Functional Programming
(V3 resp. 4 + Ü2, WS 2009/10)
|
|
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.
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.
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
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 ffi(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
The exercise sheets will be handed out during the lectures. They can
also be downloaded on this site.
You should hand in your solutions in groups of 2 or 3 students.
In the exercise course the solutions of the latest
exercise sheet will be presented and your reviewed solutions of last week's
exercises will be handed out.
If you want to hand in your solutions earlier than the deadline requires,
please go to Carsten Fuhs's office (room 4209, building E1).
In order to take part in the exercises, please sign
up here.
If you have questions regarding the review of your solution, please contact
one of the student teaching assistants.
- Sheet 1 (handed out on Oct 21, 2009, due on Oct 27, 2009)
ps,
pdf /
solution1.hs
- Sheet 2 (handed out on Oct 23, 2009, due on Oct 28, 2009)
ps,
pdf /
solution2.hs
- Sheet 3 (handed out on Nov 4, 2009, due on Nov 11, 2009)
ps,
pdf /
solution3.hs
- Sheet 4 (handed out on Nov 10, 2009, due on Nov 18, 2009)
ps,
pdf /
solution4.hs
- Sheet 5 (handed out on Nov 17, 2009, due on Nov 25, 2009)
ps,
pdf /
solution5.hs
- Sheet 6 (handed out on Nov 24, 2009, due on Dec 2, 2009)
ps,
pdf /
solution6.ps,
solution6.pdf
Remark regarding Sheet 6:
- Exercises 1 (a) + (b) and 3 (b) have been clarified over
the version of the sheet that was distributed in the lecture.
- Sheet 7 (handed out on Dec 1, 2009, due on Dec 9, 2009)
ps,
pdf /
solution7.ps,
solution7.pdf
- Sheet 8 (handed out on Dec 8, 2009, due on Dec 16, 2009)
ps,
pdf /
solution8.ps,
solution8.pdf
- Sheet 9 (handed out on Dec 15, 2009, due on Dec 23, 2009)
ps,
pdf /
solution9.ps,
solution9.pdf
Remark regarding Sheet 9, Ex. 2:
You can simplify your results during the transformation as in the
example in the lecture:
-
if (isan-tuple exp) then exp1 else exp2
can be replaced by exp1.
-
(\var -> exp) exp' can be replaced by exp, where all free
occurrences of var are replaced by exp'.
- Sheet 10 (handed out on Dec 22, 2009, due on Jan 13, 2010)
ps,
pdf /
solution10.ps,
solution10.pdf
- Sheet 11 (handed out on Jan 12, 2010, due on Jan 20, 2010)
ps,
pdf /
solution11.ps,
solution11.pdf
- Sheet 12 (handed out on Jan 19, 2010, due on Jan 27, 2010)
ps,
pdf /
solution12.ps,
solution12.pdf
- Sheet 13 (handed out on Jan 26, 2010, due on Feb 3, 2010)
ps,
pdf /
solution13.ps,
solution13.pdf
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
