Modul Fortgeschrittene Programmierung

Wintersemester 2019/20
Arbeitsgruppe Programmiersprachen und Übersetzerkonstruktion

Nr. Art Termine Raum Veranstalter
080038 V4 Mo 10:15 - 11:45 CAP3 - HS.2 Hanus
    Di 14:15 - 15:45 CAP3 - HS.2  
080037 Ü2 Mi 10-12/16-18, Do 8-10, 10-12   Bunkenburg, Dylus, Hanus
080013 PÜ1 17.2. - 28.2. HRS3 - R.501-503 Teegen, Dylus

Vorlesungsbeginn

Montag, 21.10.2019, 10:15 Uhr, CAP3 - HS.2

Zielgruppe

Studierende im 1-Fach-Bachelorstudiengang Informatik, im 2-Fach-Masterstudiengang Informatik, im Masterstudiengang Wirtschaftsinformatik sowie Studierende mit Nebenfach Informatik

Studierende Masterstudiengangs Informatik Lehramt können dieses Modul auch in Form des Kombi-Moduls Inf-FD-Kombi didaktisch begleiten. Zur zeitlichen Planung sollten interessierte Studierende ihre zeitlichen Einschränkungen mitteilen! Weitere Informationen dazu werden in der ersten Vorlesungsstunde mitgeteilt.

Dieses Modul beinhaltet auch das Modul Inf-FPKonz (Fortgeschrittene Programmierkonzepte). In diesem Fall muss der erste Teil zur nebenläufigen und verteilten Programmierung nicht gehört werden, sondern das Modul beginnt mit der funktionalen Programmierung am Montag, 4.11.2019!

Dieses Modul beinhaltet auch das Modul Inf-EinfFP (Einführung in die Funktionale Programmierung). In diesem Fall muss der erste Teil zur nebenläufigen und verteilten Programmierung ebenfalls nicht gehört werden, sondern das Modul beginnt mit der funktionalen Programmierung am Montag, 4.11.2019! Ebenso muss dann der Teil zur logischen Programmierung nicht gehört werden, sodass der Vorlesungsteil Anfang Januar endet. Die Klausur findet aber erst nach dem Praktikum (s.u.) statt.

Voraussetzungen

Solide Programmierkenntnisse einschließlich in der objektorientierten Programmierung mit Java, wie sie beispielsweise im Grundmodul Programmierung erworben werden können.

Inhalt

In dieser Vorlesung werden forgeschrittene Programmierkonzepte, die über die in den ersten Studiensemestern erlernte Programmierung hinausgehen, vorgestellt. Dabei wird anhand verschiedener Programmiersprachen der Umgang mit den Konzepten der wichtigsten Programmierparadigmen vermittelt. Konzepte zur nebenläufigen und verteilten Programmierung werden mit der Sprache Java vorgestellt und geübt. Moderne funktionale Programmierungtechniken werden am Beispiel der Sprache Haskell gezeigt. Logische und Constraint-orientierte Programmierung wird in der Sprache Prolog vermittelt.

Funktionale Programmierung in der Praxis

Ein Schwerpunkt der Vorlesung bildet die funktionale Programmierung. Dies liegt daran, dass funktionale Programmiertechniken und Sprachkonstrukte zu besser strukturierten Programmen führen und daher auch in zum Teil eingeschränkter Form in vielen modernen Programmiersprachen zu finden sind. Dies ist in einem kürzlich erschienen Artikel in der Zeitschrift CACM genauer erläutert. Allgemein gilt, dass die Verwendung funktionaler Programmierkonzepte zu kürzeren, besser strukturierten Programmen und insbesondere durch fortgeschrittene Typkonzepte zu zuverlässigeren Softwaresystemen führt.

Funktionale 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.

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. Und es gibt natürlich auch Jobs für Haskell-Programmierer.

Praktikum

Bestandteil des Moduls Inf-FortProgP ist ein Praktikum. Dieses findet nach der Vorlesung und dem ersten Prüfungszeitraum in der Zeit vom 17.2.-28.2.2020 statt. Da die erfolgreiche Teilnahme am Praktikum eine Zulassungsvoraussetzung zur Klausur ist, besteht für dieses Praktikum prinzipiell Anwesenheitspflicht. Für das Praktikum ist eine separate Anmeldung erforderlich. Informationen dazu werden in der Vorbesprechung zum Praktikum am 17.2.2020 mitgeteilt. Eine Vorbesprechung und Einführung zum Praktikum findet am 17.2.2020, 9:30 Uhr im CAP3-HS2 statt.

Modulprüfung

Am Ende der Vorlesung findet nach dem Praktikum eine schriftliche Abschlussprüfung statt. Voraussetzung zur Zulassung zur Klausur ist die regelmäßige Bearbeitung der Übungsaufgaben (s.u.) und die erfolgreiche Teilnahme am Praktikum.

Die erste Modulprüfung findet am Mittwoch, 4. März 2020, von 11:00 bis 14:00 Uhr in den Räumen OHP5 - [Chemie I], OHP5 - [Chemie II] und OHP2 - Otto-Hahn-Hörsaal statt. Die zweite Modulprüfung findet am Freitag, 27. März 2020, von 10:00 bis 13:00 Uhr im CAP2 - Frederik-Paulsen-Hörsaal statt. Eine vorherige Anmeldung in der StudiDB ist zur Teilnahme erforderlich.

Ergänzende Materialien zur Vorlesung

Es gibt ein Skript zur Vorlesung (im PDF-Format, nur innerhalb der CAU Kiel zugreifbar!), welches parallel zur Vorlesung überarbeitet wird. Dieses Skript ist kein Lehrbuch, aber es beinhaltet den ungefähren Vorlesungsverlauf. Daher sollte neben dem Lesen des Skripts auch immer die Vorlesung besucht werden, um über den aktuellen Stand informiert zu sein!

Folien und Programme:

21.10.2019: Einführung (PDF) ProducerConsumer.txt Philosophers.txt
22.10.2019: ConcurrentPrintThread.java ConcurrentPrint.java Account.java State.java Storage.java PrintStateSimple.java
28.10.2019: PrintState.java Buffer1.java Buffer1Sync.java
29.10.2019: ObjectStreamDemo.java FlipServer Interface FlipServer Implementierung FlipServer Client FlipServer Client mit Synchronisation
4.11.2019: Warum deklarative Programmierung? Einfache Haskell-Funktionen
5.11.2019: Lokale Deklarationen Datentypdeklarationen
11.11.2019: Polymorphe Daten und Funktionen
12.11.2019: Pattern Matching Funktionen höherer Ordnung
18.11.2019: Funktionen höherer Ordnung auf Listen
19.11.2019: Feld als Funktion Kombinatoren für Funktionen Funktionen höherer Ordnung in Ruby Map in Java Feld von Funktionen in Java Map in JavaScript
25.11.2019: Typklassen
26.11.2019: Unendliche Listen und Primzahllisten
2.12.2019: Unendliche Datenstrukturen List comprehensions
3.12.2019: CSV Show/Read I/O-Aktionen
9.12.2019: Dateioperationen Nats-Modul Main Hauptmodul Functor-Struktur
10.12.2019: Functor-Struktur Applicative-Struktur Monadische Strukturen
16.12.2019: Listenmonade Testen mit QuickCheck
17.12.2019: Fallstudie: Peano-Arithmetik Rationale Zahlen Test für ADT Rationale Zahlen
7.1.2020: Mengen als Funktionen Testen der Mengengesetze Mengen als Listen Mengen als geordnete Listen Verwandtschaftsbeispiel in Haskell Verwandtschaftsbeispiel in Prolog
13.1.2020: Landkartenfärbung Listenoperationen
14.1.2020: Listenkonkatenationen Peano-Zahlen
20.1.2020: Unendliche Ableitungen
21.1.2020: Verwandtschaftsbeispiel mit Negation Cut-Operator Fakultät Hypotheken SEND+MORE=MONEY
27.1.2020: n-Damen-Problem Prädikate höherer Ordnung Verwandschaftsbeispiel mit Kapselung
28.1.2020: Meta-Interpretierer für Prolog Verwandschaftsbeispiel mit Ein/Ausgabe Curry-Beispiele Peano-Arithmetik in Curry

Literatur

  • G. Hutton: Programming in Haskell, 2nd Ed., Cambridge University Press, 2016
  • R.. Bird: Thinking Functionally with Haskell, Cambridge University Press, 2015
  • S. Thompson: Haskell - The Craft of Functional Programming, 3rd Ed., Addison Wesley, 2012
  • L. Sterling, E. Shapiro: The Art of Prolog, 2nd Ed., MIT Press, 1994
  • T. Frühwirth, S. Abdennadher: Constraint-Programmierung, Springer, 1997
  • D. Lea: Concurrent Programming in Java, 2nd Ed., Addison Wesley, 2000
  • P. Hyde: Java Thread Programming, Sams Publishing, 1999

Übungen

Zur Teilnahme an der Modulprüfung müssen die Übungsaufgaben regelmäßig und sinnvoll bearbeitet werden. Hierzu wird für jede Aufgabe festgehalten, ob diese sinnvoll bearbeitet wurde ("Sinnpunkte"). Für eine Zulassung zur Klausur müssen in jedem der drei Bereiche nebenläufige/verteile Programmierung, funktionale Programmierung und logische Programmierung mindestens 50% der Sinnpunkte erreicht werden.

Die Abgabe der Übungen soll vornehmlich über das iLearn Übungssystem erfolgen. Um die Wünsche für Übungsgruppen möglichst gut zu berücksichtigen, erfolgt die Anmeldungen zu den Übungen nicht über das iLearn, sondern über diese Formular, bei dem man Präferenzen für eine Übungsgruppe angeben kann. Die Anmeldung sollte bis Dienstrag, 22.10.2019, 12 Uhr erfolgen, damit Ihr Übunsgruppenwunsch berücksichtigt werden kann!

Die in der Vorlesung behandelten Programmiersprachen sind auf den Institutsrechnern installiert und auch im Internet sind freie Implementierungen von Java, Haskell und Prolog verfügbar.

Anmerkung zur Verwendung von Prolog: Zur Lösung der Übungsaufgaben kann man das frei verfügbare SWI-Prolog-System verwenden. Um einen leichteren Einstieg in Prolog zu haben, sollte man in dieser Vorlesung zunächst eine Erweiterung für SWI-Prolog verwenden, die eine bessere Suchstrategie implementiert. Hierzu gibt es zwei Möglichkeiten (unter der Voraussetzung, das SWI-Prolog installiert ist und durch den Aufruf "swipl" gestartet werden kann):

  • Für Unix/Linux: Man kopiere dieses Bash-Skript in ein bin-Verzeichnis, das im eigenen Pfad liegt. Dann kann man durch das Kommando fortprog-swipl das erweiterte SWI-Prolog-System aufrufen. Alternativ kann man das Bash-Skript auch in das Verzeichnis legen, wo die Prolog-Programme sind, und dann das SWI-Prolog-System mit dem Kommando ./fortprog-swipl aufrufen.
  • Für andere Systeme: Man kopiere dieses Prolog-Programm in das Verzeichnis, wo sich die Prolog-Programme befinden, und starte das SWI-Prolog-System mit dem Kommando swipl -q -s fortprog.

Nach diesem Start von SWI-Prolog kann man wie üblich mit [myprog]. sein eigenes Programm laden und ausprobieren. Zu beachten ist, dass bei Benutzung dieser Erweiterung die Prolog-Programme keine Negation oder Cuts enthalten und auch keine anderen Module importieren, was aber am Anfang sowieso nicht verwendet wird.