SS 2005: Theorie der Programmierung II

Termine

Vorlesung Mo 10:15 - 11:45  H-C 3310 
Erste Vorlesung  Mo 18. 04. 2005 
Übung  Mo 08:30 - 10:00  H-A 4102
Erste Übung  Mo 02. 05. 2005


Übungsblätter

Übung 1 PDF
Übung 2 PDF
Übung 3 PDF
Übung 4 PDF
Übung 5 PDF
Übung 6 PDF


Lösungen

Übung 1 Aufgabe 1


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.
  1. die Syntax (= kontextfreie Syntax) in Kapitel 1 und 2
  2. die statische Semantik (= Typregeln) in Kapitel 3 und 4
  3. 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