WS 2005/06: Theorie der Programmierung I + II

Termine

Vorlesung Di 12:15 - 13:45 H-F 104

Do 14:15 - 15:45 gelber HS
Übungen für Teil II Do 10 - 12 H-F 115 (neu!)
Sprechstunde Di 14:00 - 15:00 H-A 8113

Aufteilung

Teil I der Vorlesung endet kurz vor Weihnachten, Teil II schließt sich unmittelbar an.

Übungsblätter

Übung 1 PDF
Übung 2 PDF
Übung 3 PDF
Übung 4 PDF
Übung 5 PDF
Übung 6 PDF
Übung 7 PDF
Übung 8 PDF
Übung 9 PDF
Übung 10 PDF
Übung 11 PDF
Übung 12 PDF

Lösungen

Übung 1, Aufgabe 1 PDF
Übung 2, Aufgabe 3 PDF
Übung 3, Aufgabe 3 PDF
Übung 4, Aufgabe 3 PDF
Übung 5, Aufgabe 2 PDF
Übung 5, Aufgabe 3 PDF
Übung 5, Aufgabe 5 PDF
Übung 8, Aufgabe 4 PDF

Materialien zur Vorlesung

Abstrakte Syntax der Sprachen L0 und L1 PDF
Small step Semantik der Sprachen L0 und L1 PDF (korrigierte Version vom 27.10.2005)
Definition der Sprache L2 und big step Semantik von L0, L1, L2 PDF
Beispiel zur big step Semantik: Fakultätsfunktion PDF
Die einfach getypten Sprachen L0t, L1t, L2t PDF
Beispiel einer Typherleitung in L2t: Potenzieren PDF
Die Typinferenz-Sprachen L0ti, L1ti, L2ti PDF
1. Beispiel zur let-Polymorphie PDF
2. Beispiel zur let-Polymorphie PDF
Typinferenz für die Sprachen LiML PDF (korrigierte Version vom 28.12.2005)

Literatur

1. Benjamin Pierce: Types and Programming Languages, MIT Press, 2002

In diesem Buch werden (nur) small-step Semantik und Typsysteme behandelt. Dabei wird in Teil II (Kapitel 8-14) etwa die gleiche Programmiersprache abgedeckt, die wir auch in der Vorlesung betrachten, und es werden ähnliche Resultate (z.B. Typsicherheit) für diese Sprache bewiesen. Insgesamt ist das Buch sehr als Vorlesungsbegleitung zu empfehlen.

2. Glynn Winskel: The Formal Semantics of Programming Languages, MIT Press,1993

In Kapitel 2,5 und 6 des Buches werden operationelle, denotationelle und axiomatische Semantik für eine einfache imperative Sprache behandelt, in Kapitel 9, 10 und 11 werden Typsysteme, operationelle und denotationelle Semantik für funktionale Sprachen betrachtet. Der Schwerpunkt bei der operationellen Semantik liegt auf big-step, small-step kommt nur am Rande vor (Absatz 2.6).

3. Robin Milner, Mads Tofte and Robert Harper: The Definition of Standard ML, MIT Press 1990

In diesem Buch wird die funktionale Programmiersprache "Standard ML" (an die sich die in der Vorlesung definierte Sprache anlehnt) formal definiert, d.h.
- die Syntax (= kontextfreie Syntax) in Kapitel 1 und 2
- die statische Semantik (= Typregeln) in Kapitel 3 und 4
- die dynamische Semantik (= big step Semantik) in Kapitel 5 und 6
Man kann hier einmal sehen, wie die Techniken, die wir in der Vorlesung erlernen, auf eine echte Programmiersprache angewendet werden. Das ist natürlich sehr aufwendig.

4. Robin Milner and Mads Tofte: Commentary on Standard ML, MIT Press, 1991

Hier werden Erläuterungen zu 3. gegeben und es werden einige Sätze über die Semantik bewiesen.

5. Larry C. Paulson: ML for the working programmer

Sehr zu empfehlen für jeden, der in ML programmieren oder auch nur etwas mehr Gefühl für's funktionale Programmieren bekommen möchte (was ja für die Vorlesung nicht schaden kann!). Natürlich gibt's noch viele andere Bücher zum gleichen Thema.
Kurt Sieber