Grundlagen der funktionalen Programmierung

Das vorliegende Buch entstand aus einer Reihe von Vorlesungen, die der Autor an der Eberhard-Karls-UniversWit Tiibingen unter dem Titel "Einfiihrung in die funktionale Programmierung" gehalten hat. Die Zielgruppe der Vorlesung sind Studenten im Hauptstudium, die Informatik als Haupt-oder Nebenfach belegen. Voraussetzungen zum Verstandnis des Buches sind die Kenntnis von Grundbe griffen der Informatik und Programmierung. Die Vorlesung, wie auch das Bueh, besteht aus zwei Tellen. Der erste Tell um faBt die Kapitell bis 8 und ist praktisch orientiert. Er gibt eine kurze Einfiihrung in die rein-funktionale Programmiersprache Gofer mit grundlegenden Program mierteehniken und Methoden der Verifikation und Transformation von Program men gefolgt von einem kurzen Ausbliek auf fortgesehrittene Techniken und wei terfiihrende Konzepte. Insbesondere wird auf Typklassen, Konstruktorklassen und Monaden, sowie rein-funktionale Ein-und Ausgabe eingegangen. Typklassen und Konstruktorklassen erlauben die kontrollierte Uberladung von benutzerde finierten Funktionen. Monaden ermoglichen unter anderem die Integration von in rein-funktionale Programmierspraehen. Variablen im herkommlichen Sinn 1m zweiten Teil (Kap. 9 bis 15) werden verschiedene Modelle fur Semantik und Ausfiihrung funktionaler Programmiersprachen vorgestellt. Der Tell umfaBt eine Einfiihrung in die Bereichstheorie, universelle Algebra, operationelle und de notationelle Semantik, und den Lambda-Kalkiil. Ferner werden Typen und ihre Semantik, die automatisehe Rekonstruktion von Typen, sowie Grundbegriffeder abstrakten Interpretation und Striktheitsanalyse behandelt. Damit verzahnt wer den Implementierungstechniken fur funktionale Programmiersprachen auf einer abstrakten Ebene diskutiert.

1 Einführung.- 2 Grundlegende Sprachstrukturen.- 2.1 Programmierung mit Funktionen.- 2.2 Lexikalische Syntax.- 2.3 Deklarationen.- 2.4 Typausdrücke.- 2.5 Ausdrücke.- 2.6 Muster.- 2.7 Deklarationen auf der Skriptebene.- 2.8 Polymorphie.- 2.9 Aufgaben.- 3 Funktionen höheren Typs.- 3.1 Die Funktion map.- 3.2 Die Funktion foldr.- 3.3 Funktionale auf Bäumen.- 3.4 Verallgemeinerte map- und fold-Funktionale.- 3.5 Literaturhinweise.- 3.6 Aufgaben.- 4 Fallstudien.- 4.1 Auswertung von Polynomen.- 4.2 Operationen auf Matrizen und Vektoren.- 4.3 Graphische Darstellung von Bäumen.- 5 Verzögerte Auswertung.- 5.1 Auswertung.- 5.2 Newtonscher Algorithmus.- 5.3 Das Sieb des Eratosthenes.- 5.4 Zirkuläre Datenstrukturen.- 5.5 Aufgaben.- 6 Programmeigenschaften.- 6.1 Induktionsbeweise.- 6.2 Aussagen über Funktionen.- 6.3 Programmsynthese.- 6.4 Programmtransformation.- 6.5 Partielle Listen.- 6.6 Literaturhinweise.- 6.7 Aufgaben.- 7 Fortgeschrittene Konzepte.- 7.1 Komprehensionen für Listen.- 7.2 Parser.- 7.3 Monaden.- 7.4 Funktionale Ein-/ Ausgabe.- 7.5 Spezifische Eigenschaften von Haskell und Gofer.- 7.6 Literaturhinweise.- 7.7 Aufgaben.- 8 Überblick und Anwendungen.- 8.1 Lisp.- 8.2 ISWIM und FP.- 8.3 ML.- 8.4 Hope.- 8.5 MirandaTM.- 8.6 Haskell.- 8.7 Anwendungen.- 9 Einführung in die denotationelle Semantik.- 9.1 Semantik von Funktionsgleichungen.- 9.2 Strikt vs. nicht-strikt.- 10 Bereichstheorie.- 10.1 Vollständige Halbordnungen.- 10.2 Konstruktion von Halbordnungen.- 10.3 Beziehungen zwischen Bereichen.- 10.4 Bereichsgleichungen.- 10.5 Literaturhinweise.- 10.6 Aufgaben.- 11 Universelle Algebra.- 11.1 Homogene Algebra.- 11.2 Polymorphe Algebra.- 11.3 Literaturhinweise.- 11.4 Aufgaben.- 12 Sprachen mit Funktionen erster Ordnung.- 12.1 Syntax.- 12.2 Semantik.- 12.3Maschinenmodelle und Übersetzung.- 12.4 Aufgaben.- 13 Sprachen mit Funktionen höherer Ordnung.- 13.1 Syntax.- 13.2 Semantik.- 13.3 Maschinenmodelle und Übersetzung.- 13.4 Parallele Auswertung.- 13.5 Literaturhinweise.- 13.6 Aufgaben.- 14 Abstrakte Interpretation.- 14.1 Grundlagen.- 14.2 Striktheitsanalyse.- 14.3 Vorwärtsanalyse.- 14.4 Rückwärtsanalyse.- 14.5 Literaturhinweise.- 14.6 Aufgaben.- 15 Der ?-Kalkül.- 15.1 Syntax und Reduktionssemantik.- 15.2 Darstellung rekursiver Funktionen.- 15.3 Ein angereicherter ?-Kalkül.- 15.4 Typen für den ?-Kalkül.- 15.5 Semantik von Typen.- 15.6 Die SECD-Maschine.- 15.7 SKI-Kombinatorreduktion.- 15.8 Literaturhinweise.- 15.9 Aufgaben.- A Grundlegende Notation.- B Syntaxdiagramme von Gofer.- B.1 Deklarationen.- B.2 Typen.- B.3 Klassen- und Exemplardeklarationen.- B.4 Wert- und Funktionsdeklarationen.- B.5 Ausdrücke.- B.6 Muster.- B.7 Variablen und Operatoren.- B.8 Lexikalische Syntax.- C Kurzübersicht Gofer.- D Implementierungen von Gofer und Haskell.- E Bedienung des Gofer-Interpretierers.- Literatur.- Sachwortverzeichnis.