Funktionale Programmierung (FuPro)
  • Pflichtveranstaltung INF-BSc-114 im WiSe 2016/17 für Studierende des Bachelor-Studiengangs Informatik
    sowie
    3-std. Wahlveranstaltung im Hauptstudium der Informatik-Diplomstudiengänge für die Schwerpunktgebiete 1 und 4
  • 2 SWS Vorlesung + 1 SWS Übung = 5 Credits
  • Zur Teilnahme an der Übung bitte unter LSF oder Moodle für diese LV anmelden. Dort stehen alle laufenden Infos, Übungstermine und -aufgaben.
  • Übungsleiter: Jos Kusiek
  • Vorlesungstermin: Fr 14:15-15:45 im HG 2, Hörsaal 3
  • Beginn: 21. 10. 2016
  • Inhalt
    Die LV behandelt Konzepte und Anwendungen funktionaler, musterbasierter und monadischer Programmierung anhand der zur Zeit mächtigsten und am weitesten verbreiteten funktionalen Programmiersprache Haskell. Der Kern eines funktionales Programms ist ein System rekursiver Gleichungen zwischen funktionalen Ausdrücken. Seine Ausführung besteht in der Auswertung der Ausdrücke durch Anwendung der Gleichungen. Auch Ein- und Ausgabedaten sind funktionale Ausdrücke, deren Funktionen Konstruktoren genannt werden, weil sie nicht ausgeführt werden, sondern nur den Aufbau der Daten(muster) beschreiben. Dieses Sprachmodell und der damit einhergehende Programmierstil unterscheiden sich zunächst stark von dem einer objektorientierten, imperativen und zustandsorientierten Sprache wie Java. Sie erlauben oft problemnahere und flexiblere Lösungen, die leicht an neue Anforderungen, modifizierte Datenstrukturen, etc. anpassbar sind. Mit den Konzepten der funktionalen Programmierung, insbesondere mit geeigneten Typklassen, lässt sich aber auch zustandsorientiert und sogar aspektorientiert implementieren, so dass z.B. der gleiche Algorithmus leicht von einer deterministischen in eine nichtdeterministische oder um differenzierte Ausnahmebehandlungen erweiterte Variante übertragbar ist. Ebenso kann die traditionell der logischen oder relationalen Programmierung vorbehaltene Beantwortung prädikatenlogischer Anfragen funktional realisiert werden. Dies ist eine Konsequenz der lazy evaluation-Strategie, der die Ausführung jedes Haskell-Programms folgt. Sie erlaubt u.a. das Rechnen mit unendlichen Datenströmen, Prozessbäumen, etc.
    Folglich wird in dieser Lehrveranstaltung nicht nur ein bestimmter Programmierstil behandelt, sondern ganz allgemein die Klassifikation von Daten- und Programmtypen auf der Basis mathematischer Strukturen sowie deren direkte Implementierung. Damit wird Haskell auch als Entwurfssprache einsetzbar, in der sich formale Modelle direkt ausführen lassen (rapid prototyping).
  • Kompetenzen
    Die Studierenden lernen den Umgang mit Konzepten funktionaler, musterbasierter und monadischer Programmierung und deren Einsatz in verschiedenen Anwendungsbereichen. Sie werden damit u.a. vorbereitet auf Wahlpflicht-LVs wie Übersetzerbau und das Fachprojekt Rapid Prototyping. Außerdem lernen sie, wie diese Konzepte nicht nur zur Lösung reiner Implementierungsaufgaben, sondern auch zur präzisen Modellierung verwendet werden können, was wiederum dazu befähigt, die Konzepte sowie entsprechende Werkzeuge auch in Entwicklungsumgebungen zu nutzen, in denen am Ende in Java, C++ oder einer anderen nichtfunktionalen Sprache programmiert wird. Allerdings werden auch dort zunehmend funktionale Konstrukte eingebaut, was bereits eine Reihe hybrider Sprachen wie z.B. F-Sharp, Objective CAML, Python, Ruby und Scala hervorgebracht hat.
  • Zeitplan der Vorlesung
    • 21. 10. 2016 Einführung, Funktionen
    • 28. 10. 2016 Funktionen
    • 04. 11. 2016 Listen
    • 11. 11. 2016 dto.
    • 18. 11. 2016 Datentypen, Typklassen
    • 25. 11. 2016 dto.
    • 02. 12. 2016 Bäume
    • 09. 12. 2016 dto.
    • 16. 12. 2016 Fixpunkte, Graphen
    • 13. 01. 2017 dto.
    • 20. 01. 2017 Funktoren und Monaden
    • 27. 01. 2017 dto.
    • 03. 02. 2017 Felder, Matrizen
    • 10. 02. 2017 Monadentransformer und Comonaden
  • Klausurtermine
    • 20. 02. 2017, 10:30 - 12:30, HG 2, Hörsäle 1, 5 und 6
    • 27. 03. 2017, 08:00 - 10:00, HG 2, Hörsäle 1, 3 und 6
  • Folienskript zur LV
  • Haskell-Startseite
  • Hackage: Haskell-Bibliotheken und -Werkzeuge
  • Hoogle, die Haskell-Suchmaschine
  • Haskell 98 Report - Online-Version
  • Haskell 2010 Report
  • Tutorials et al.
  • Haskell-Lehrbücher
  • Haskell-Module (die zum Teil in der LV benutzt werden)
    • Painter: Funktionen zur graphischen Wiedergabe von Texten, Bäumen, Graphen und Berechnungsfolgen in SVG- bzw. HTML-Dateien. Zur Benutzung von Painter-Funktionen werden aus dem Painter-Paket nur die Haskell-Module Movie.hs und Painter.hs sowie ein Verzeichnis Pix benötigt, das das JavaScript-Programm Painter.js enthält. Letzeres steuert die GUI-Komponenten der von einigen Painter-Funktionen erzeugten und in Pix gespeicherten HTML-Dateien. Alle Painter-Funktionen sind im Manual (Painter.pdf) beschrieben.
    • Coalg.hs: (Co)Algebraische (Daten)Typen inkl. ihrer (co)monadischen Operationen (gehört zum Painter-Paket)
    • Expr.hs: Programme zu Datentypen für arithmetische Ausdrücke (gehört zum Painter-Paket)
    • Align.hs: Programm zur Erzeugung von Alignments; siehe Modellieren und Implementieren in Haskell, Abschnitt Felder
    • Lazy.hs: Programme, die mit unendlichen Objekten oder anderen als Gleichungslösugen definierten Daten arbeiten
    • Examples.hs (gehört zum Painter-Paket)
    • PreludeHugs.hs: Häufig verwendete Standardtypen und -funktionen (stimmt größtenteils mit dem ghci-Prelude überein)
    • Term.hs: Substitution, Unifikation
    • Interpreter
    • Datentypen
    • O'Haskell-Typen
    • Nebenläufigkeit in O'Haskell
    • Records
    • Springer-Wege und -Kreise
    • Graphics.HGL: Manual - Folien - Installation unter Mac OS X
  • Skript zu einer Vorläufer-Veranstaltung, die auf der seinerzeit fortgeschrittensten funktionalen Sprache Standard ML basiert.
  • Sammlungen alter Übungsblätter