Programming Languages and Types

WS 2009/2010

The invention of programming is maybe the most significant intellectual achievement of the 20th century. Nowadays, the beauty and elegance of programming is often hidden behind complex programming languages and large tool chains. This course will open your eyes and you will be trained to see the gold in the mud.


The topics we will discuss include: names, definitional interpreters, lambda calculus, lazy evaluation, continuations, recursion, stateful vs. stateless, operational and denotational semantics, formal type systems and soundness, module systems, domain-specific languages, Scheme, Haskell, Scala, Java

Time and Place

see here


Prof. Dr. Klaus Ostermann
Sebastian Erdweg, M.Sc.
Tillmann Rendel, M.Sc.


The obligatory material is the basis for the exam. The advanced material exceeds what was discussed in class, but it is a good idea to take a look at it if you are striving for a very good grade in the exam.

DateTopicObligatory MaterialAdvanced Material
October 14 ASTs, parsing s-expressions
arithmetic expressions
PLAI Chap. 1-2
Lectures Notes 1
Reynold's paper on definitional interpreters
The next 700 programming languages
October 15 substitution, first-order functions, scope
environments vs substitution
PLAI Chap. 3-5
Lectures Notes 1 2
October 21 first-class functions, closures, dynamic vs static scoping PLAI Chap. 6
Lecture Notes 1 2 3
October 22 introduction to Haskell, lazy evaluation, designing modular programs using lazy evaluation PLAI Chap. 7
Why functional programming matters
Lecture Notes 1 2
October 28 implementing laziness, call-by-name vs. call-by-need, data vs. codata PLAI Chap. 8
Lecture Notes 1 2
October 29 structural recursion and guarded co-recursion, implementing recursion, fixpoint combinators PLAI Chap. 9-11
Lecture Notes 1 2
Total Functional Programming
November 4 State PLAI Chap. 12-13
Lecture Notes 1
November 5 State PLAI Chap. 14
November 11 Objects, Intro to Monads Lecture Notes 1 2
November 12 Maybe, Reader, State, IO, List Monad
Monad composition
Lecture Notes 1 2 3 4
November 18 Introduction to Continuations PLAI Chap. 15-17
November 19 Continuations, continued PLAI Chap. 18
November 25 Continuations, continued Lecture Notes 1
PLAI Chap. 19,20
November 26 Induction Principles
Structural Operational Semantics
Lecture Notes 1
Pierce Chap. 3
December 2 and 3 Introduction to Type Systems Lecture Notes 1
Pierce Chap. 8,9,11
December 9 and 10 Subtyping
Object-Oriented Programming
Lecture Notes 1 2
Pierce Chap. 15,16,18,19
December 16 fällt aus - Weihnachtsfeier
January 13 and 14 Type Inference, System F Lecture Notes 1 2
Pierce Chap. 22,23
January 20 and 21 Propositions-as-Types Lecture Notes 1
January 27 and 28 Existential Types Pierce Chap. 24, 29, 30
Lecture Notes 1
February 4 Higher-Order Types Lecture Notes 1
February 5 Domain-Specific Languages Lecture Notes 1 2
February 10 and 11 Domain-Specific Languages, ctd. Lecture Notes 1 Typed self-representation


In the beginning, we will use PLT Scheme, together with the PLAI plug-in, whose installation is described here (see "Get the Software"), and for which a reference can be found here.

In addition to group exercises, there are compulsory homework assignments which you are to work on in groups of three students. To be admitted to the exam, you have to hand in reasonable solutions for all but two assignments, and you have to present your homework in one of the exercises classes. Please hand in your homework by email to The exercise descriptions are published below on Thursday evenings after the lecture, and have to be handed in until Thursday of the following week.

DateGroup ExerciseHomeworkDeadlineNotes
October 19g01.pdf h01.pdfOctober 22
October 26g02.pdf h02.pdfOctober 29
November 2g03.pdf h03.pdfNovember 5
November 9g04.pdf h04.pdfNovember 12
November 16g05.pdf h05.pdfNovember 19 code:
November 23g06.pdf h06.pdfNovember 26 code:,
further (non-obligatory) reading: On One-Pass CPS Transformations
November 30g07.pdf h07.pdfDecember 3
December 7g08.pdf h08.pdfDecember 10 FAE interpreter
December 14g09.pdf h09.pdfDecember 17
January 11g10.pdf none
January 18g11.pdf h11.pdfJanuary 21
January 25g12.pdf h12.pdfJanuary 28
February 1g13.pdf h13.pdfFebruary 4
February 8g14.pdf h14.pdfFebruary 11


We will mainly use the books by Krishnamurthi and Pierce.

Shriram Krishnamurthi
Programming Languages: Application and Interpretation
Available online under Creative Commons License
Benjamin C. Pierce
Types and Programming Languages
MIT Press, 2002
Other references we will use:


to be done