Programming Languages: Application and Interpretation
Available online under Creative Commons License
Types and Programming Languages
MIT Press, 2002
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
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.
| Date | Topic | Obligatory Material | Advanced 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 pllecture@informatik.uni-marburg.de. The exercise descriptions are published below on Thursday evenings after the lecture, and have to be handed in until Thursday of the following week.
| Date | Group Exercise | Homework | Deadline | Notes |
|---|---|---|---|---|
| October 19 | g01.pdf | h01.pdf | October 22 | |
| October 26 | g02.pdf | h02.pdf | October 29 | |
| November 2 | g03.pdf | h03.pdf | November 5 | |
| November 9 | g04.pdf | h04.pdf | November 12 | |
| November 16 | g05.pdf | h05.pdf | November 19 | code: h05.ss |
| November 23 | g06.pdf | h06.pdf | November 26 | code: h06-skel.ss, further (non-obligatory) reading: On One-Pass CPS Transformations |
| November 30 | g07.pdf | h07.pdf | December 3 | |
| December 7 | g08.pdf | h08.pdf | December 10 | FAE interpreter |
| December 14 | g09.pdf | h09.pdf | December 17 | |
| January 11 | g10.pdf | none | ||
| January 18 | g11.pdf | h11.pdf | January 21 | |
| January 25 | g12.pdf | h12.pdf | January 28 | |
| February 1 | g13.pdf | h13.pdf | February 4 | |
| February 8 | g14.pdf | h14.pdf | February 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 |
to be done