Modul Deklarative Programmiersprachen

Sommersemester 2024

Arbeitsgruppe Programmiersprachen und Übersetzerkonstruktion

Nr. Art Termine Raum Veranstalter
080039 V4 Mo 10:15 - 11:45 LMS8 - R.EG.009 Hanus
    Di 16:15 - 17:45 LMS4 - R.526  
080027 Ü2 Do 10:15 - 11:45 CAP3 - Hörsaal 1 Hanus, Prott

Organisatorisches

Die Vorlesung beginnt am Montag, 15.04.2024, 10:15 Uhr. In den ersten beiden Vorlesungswochen finden an den Übungsterminen auch Vorlesungen statt.

Alle Teilnehmer müssen dieses Modul in der StudiDB belegen, damit sie nachher eine Prüfung ablegen können. Eine frühere Anmeldung ist nicht erforderlich. Für Rückfragen, Anmerkungen, Verbesserungsvorschläge u.ä. können die Veranstalter gerne per Email kontaktiert werden.

Zielgruppe

Studierende in den Bachelor- oder Masterstudiengängen Informatik und Wirtschaftsinformatik sowie Studierende mit Nebenfach Informatik

Voraussetzungen

Grundstudium (1.-4. Semester) in Informatik, insbesondere das Modul Deklarative Programmierung (oder das Vorgängermodul Fortgeschrittene Programmierung). Das Skript zu dieser Vorlesung ist als PDF innerhalb der CAU zugreifbar)

Inhalt

Aufgrund der Komplexität heutiger Software-Systeme ist die Verwendung von Programmiersprachen mit einem hohen Abstraktionsniveau notwendig. Deklarative Sprachen bieten hierzu wichtige Lösungsansätze. Aufgrund ihrer deklarativen Struktur sind Programme leichter wartbar und verifizierbar, was gerade für die Zuverlässigkeit und Sicherheit von Softwaresystemen relevant ist. Z.B. hat kürzlich die Videospielentwicklungsfirma Epic Games die neue deklarative Programmiersprache Verse vorgestellt, die zur Spieleentwicklung eingesetzt wird.

In dieser Vorlesung werden Konzepte moderner deklarativer Programmiersprachen vorgestellt. Ausgehend von dem aus dem Grundstudium bekannten Konzept der funktionalen Programmierung, das kurz wiederholt und eingehender erläutert wird, werden funktionale Sprachen um logische Anteile erweitert, um die Konzepte der funktionalen, logischen und integrierten logisch-funktionalen Sprachen in einem einheitlichen Rahmen darzustellen. Außerdem werden die Grundlagen der funktionalen und logischen Programmierung vorgestellt.

Deklarative Programmierung in der Praxis

Deklarative Programmiertechniken und Sprachkonstrukte führen zu besser strukturierten Programmen führen und sind daher auch in zum Teil eingeschränkter Form in vielen modernen Programmiersprachen zu finden. Deklarative Programmiersprachen sind nicht nur vom akademischen Interesse, sondern sie werden auch in der Praxis immer stärker eingesetzt. Zum Beispiel verwendet Jane Street Capital, eine Finanzhandelsfirma mit Vertretungen in New York, London und Hong Kong, die funktionale Sprache OCaml für ihre Anwendungen (dazu gibt es auch einen Blog). Die Firma Galois mit Hauptsitz in Portland (Oregon, USA) verwendet funktionale Programmiersprachen und -konzepte zur Entwicklung sicherheitskritischer Systeme.

Die logische Programmiersprache Prolog wurde im KI-System Watson eingesetzt, das im Februar 2011 in der Quizsendung Jeopardy gegen zwei menschliche Spieler gewonnen hat. Hierbei wurde in Watson die Sprachverarbeitung mit Prolog implementiert.

Die Firma Epic Games ist bekannt für die Entwicklung von Videospielen (insbesondere Fortnite) und verwendet die neue deklarative Programmiersprache Verse als Entwicklungsplattform. Verse kombiniert Elemente der funktionalen und logischen Programmierung und greift damit Elemente auf, die in dieser Vorlesung diskutiert werden. Details kann man in einem Papier zu den Grundlagen von Verse und z.B. einem Vortrag von Simon Peyton Jones und Tim Sweeney zu Verse finden.

Warum gerade im Finanzbereich funktionale Programmierung eingesetzt wird, liegt auch daran, dass Fehler in einer Software existenzielle Probleme verursachen kann, wie man am Fall von Fall Knight Capital sehen kann.

Hier sind noch ein paar weitere Berichte über den industriellen Einsatz funktionaler Programmierung:

Forscher bei Microsoft fordern in einem Artikel der Zeitschrift CACM, dass Informatikstudierende so früh wie möglich funktionale Programmiersprachen erlernen sollten.

Modulprüfung

Am Ende der Vorlesung findet eine mündliche Abschlussprüfung statt. Die Zeiten werden später individuell vereinbart.

Ergänzende Materialien zur Vorlesung

Es gibt kein ausführliches Lehrbuch oder Skript zur Vorlesung, aber einige Notizen zur Vorlesung im PDF-Format (nur innerhalb des Netzwerkes der CAU Kiel zugreifbar!), die im Verlauf des Semesters aktualisiert werden. Dieses Skript ist kein Ersatz für die Vorlesungsteilnahme, es beinhaltet aber den ungefähren Vorlesungsverlauf und ist hoffentlich eine gute Unterstützung. Wer darin keine Fehler entdeckt, hat bestimmt nicht ordentlich gelesen. Es wäre es schön, wenn Fehler an Michael Hanus mitgeteilt werden.

Folien und Programme:

15.4.2024: Einführung (PDF) Diskriminierungsfreies IfI (PDF) Quicksort (PDF) HeartBleedBug (PDF) Anwendungen deklarativer Sprachen (PDF)
16.4.2024: Einfache Haskell-Funktionen Wurzelberechnung (Haskell)
18.4.2024: Datentypen Pattern Matching
22.4.2024: Pattern-Matching-Transformation (PDF) Pattern Matching: Transformationsbeispiele
23.4.2024: Beispiel: Auswertungsstrategie + Pattern Matching Polymorphe Funktionen
6.5.2024: Typinference für mehrere Funktionen Typisierung mit Rank-2-Polymorphismus
13./14.5.2024 Berechnungsstrategien (Video) Induktiv-sequenzielle TES (Video)
21.5.2024: Induktiv-sequenzielle Programme Verwandtschaftsbeispiel (Haskell) Verwandtschaftsbeispiel (Curry) Extravariablen, Listen (Curry) Spiel 24 (Curry)
27.5.2024: Reguläre Ausdrücke (Curry)
28.5.2024: Funktionen als Relationen (Prolog) Vorfahr-Relation (Curry) Probleme mit Backtracking (Curry) Landkarte färben (Curry) Haus vom Nikolaus (Curry)
4.6.2024: Nichtdeterministische Operationen (Curry)
10.6.2024: Call-time Choice vs. Run-time Choice (Curry) Residuation-Problem (Curry) Curry-Auswertungsstrategie: Beispiele (Curry)
11.6.2024: Gleichheit in Curry Bankkonto (Curry)
17.6.2024: Eingekapselte Suche (Curry)
18.6.2024: Kürzeste Wegesuche (Curry) n-Damen-Problem (Curry) Variationen über last (Curry)
24.6.2024: Anwendungen funktionaler Musterr (Curry) Arithmetische Ausdrucksverarbeitung (Curry) Counter GUI (Curry)
25.6.2024: Counter GUI (Curry) GUI mit Temperaturkonverter (Curry) Tischrechner-GUI (Curry) Dynamische Webseite (Curry)
1.7.2024: Analyse von IT-Sicherheitsregeln (Curry) XML-Strukturen (Curry)
2.7.2024: XML-Verarbeitung mit funktionalen Mustern (Curry)
8.7.2024: Default-Regeln in Curry Färben einer Landkarte mit Default-Regeln (Curry) Bubble Sort (Curry) Dutch National Flag (Curry) Vereinfachung arithmetischer Ausdrücke (Curry) Programm mit Vor/Nachbedingungen (Curry) Programmkorrektheit: keine Fehlschläge (Curry)

Übungen

In den begleitenden Übungen werden für praktische Programmieraufgaben die Sprachen Haskell und Curry eingesetzt, für die es frei verfügbare Implementierungen für Unix- und Linux-Systeme gibt.

Literatur

  • G. Hutton: Programming in Haskell, 2nd Ed., Cambridge University Press, 2016
  • R.. Bird: Introduction to Functional Programming using Haskell, Prentice Hall, 1998
  • S. Thompson: Haskell - The Craft of Functional Programming, Addison-Wesley, 3rd Ed., 2011
  • L. Sterling, E. Shapiro: The Art of Prolog, 2nd Ed., MIT Press, 1994
  • M. Hanus: Functional Logic Programming: From Theory to Curry, Programming Logics - Essays in Memory of Harald Ganzinger, Springer LNCS 7797, pp. 123-168, 2013
  • S. Antoy, M. Hanus: Functional Logic Programming, Communications of the ACM, Vol. 53, No. 4, pp. 74-85, 2010
Weitere Literatur wird in der Vorlesung bekanntgegeben.