Funktionale Programmierung (WS 05/06)

Klausuren:

1. Teil (40%): 12.12.2005, 18:00-19:00, HS 13 IM.
2. Teil (60%): 10.02.2006, 10:00-12:00, 010 IM, Rechnerklausur.

Übersicht Nachrichtenkasten Eintrag im kommentierten Vorlesungsverzeichnis Vorlesungsplan und Folien Übungsmaterialien Was ist funktionale Programmierung? Die Vorlesung basiert auf der Programmiersprache Haskell Haskell (ghc) im Performance-Vergleich Schein zur Vorlesung Begleitende Literatur Tools zur Programmentwicklung GUIs in funktionalen Programmen Hintergrundinformationen

Nachrichtenkasten

• [13.02., 16:51] Die Klausuren sind korrigiert und können ohne Termin in Raum IM 128 eingesehen werden.

Vorlesungsplan, Folien und Ergänzungsmaterialien

1. [18.10.,20.10.] Einführung
2. [20.10.-31.10.] Grundlegende Elemente der Sprache Haskell
3. [31.10.-07.11.] Programmierung mit Kombinatoren
4. [07.11.-21.11.] Beweis und Herleitung von Programmen
   • Programm zur Simulation der Vereinfachung induktiv definierter Funktionen: SimReduce.hs.
5. [21.11.-28.11.] Lambda-Kalkül und Laziness
6. [28.11.-05.12.] Interpretation, abstrakte Interpretation, Typinferenz
   Beispielprogramme
   • zum Curry-Howard-Isomorphismus: CurryHoward.hs
   • Größeninformation in Typen: List.hs
7. [05.12.-13.12.] Monaden
   • Kombination von Monaden und Interpretern
     • alles: interpreter.tgz
     • Monaden: MonIdent.hs, MonError.hs, MonStateTrans.hs
     • Interpreter: InterStrict.hs, InterNonStrict.hs
   • Editor: IOS.hs, Editor.hs
8. [19.12.-20.12.] Effizienzaspekte
   Beispielprogramme
   • Sortieren und Heaptrees: effsort.tgz
   • Amortisation: Queue.hs
9. [09.01.-10.01.] Parsing mit Kombinatoren und Generatoren
   Beispielprogramme
   • Kombinatoren
     • alles: Kombinatoren.tgz
     • einzeln: Scanner.hs, Parser.hs, Expr.hs
   • Generatoren
     • alles: Generator.tgz
     • Einzelbeispiele: Example1.y, Example2.y, Example3.y, Example4.y
     • Mini-Pascal-Interpreter:
       • Interpreter: Scanner.x, Parser.y, Main.hs
       • Eingabe-Programme: loop.pas, fibs.pas, err.pas
10. [16.01.-23.01.] Metaprogrammierung in Template-Haskell und MetaOCaml
    Beispielprogramme:
    • MetaOCaml (> metaocaml, dann laden mit z.B. #use "power.ml";;)
      • Potenzfunktion:
        • ungestaged: power.ml
        • günstig gestaged: power1.ml
        • ungünstig gestaged: power2.ml
      • Interpreter: interp.ml (laden und ca. 1 Minute warten)
    • Template Haskell
      • printf: Printf.hs, Main.hs
      • Tupel: Sel.hs, Zip.hs, Main.hs
11. [24.01.-31.01.] Funktionale Hardware-Spezifikation und -Simulation
12. [06.02.-07.02.] Parallelisierung funktionaler Sprachen

Übungsmaterialien

• [19.10.] Einführung
  • Interaktion mit dem Interpreter ghci:
    • einfache Beispiele: Inter.1
    • Unterschiede Int/Integer-Zahlen: Inter.2
    • Unterschiede Double/Rational-Zahlen: Inter.3
  • Verwendung einer Skriptdatei (lesen Sie bitte die Kommentare darin): Ex1.hs, Version ohne Kommentare: Ex1woc.hs
• Aufgabenblatt 1
• [26.10.] Funktionen als Argumente und Ergebnis
  • Lösung von Blatt 1: Sol1.hs
  • zusätzlich: Main.hs
• Aufgabenblatt 2
• [02.11.] Datenstrukturen, Listenkombinatoren
  • Lösung von Blatt 2: Sol2.hs
  • Algebraische Datentypen: Robot.hs
  • Einfügen und Sortieren auf Listen: Sort.hs
• Aufgabenblatt 3
• [09.11.] Listenkombinatoren, algebraische Datentypen
  • Musterlösung von Blatt 3: Sol3.hs
  • Lösung aus der Übung: Sol3ueb.hs
• Aufgabenblatt 4
  • [16.11.] Lösung aus der Übung: Sol4.hs
  Aufgabenblatt 5
  • Lösung aus der Übung: Sol5.hs
  • Musterlösung mit Induktion über zweite Liste: Sol5a.hs
• Aufgabenblatt 6, MSS ohne Bereichsangabe: MSS.hs
  Lösungen:
  • MSS mit Bereichsangaben: MssRange.hs
  • Reduktion auf Normalform: Lambda.hs
• Aufgabenblatt 7
  
  • Vorgabe: vorgabe.tgz
  • Lösung: loesung.tgz, Einzeldateien: Syntax.hs, Reduce.hs, Environment.hs, Eval.hs, Main.hs
• Aufgabenblatt 8
  • Lösung zu Aufg. 22: Main.hs
  Aufgabenblatt 9
  • Vorgabe: IOS.hs, Editor.hs
  • Lösung: Editor2.hs
• Aufgabenblatt 10
  • Vorgabe: alex Scanner.x, happy Parser.y, ghci -fglasgow-exts Main.hs
  • Beispieleingaben: loop.pas, while.pas, fibs.pas
  • Lösungen: Loesung24.tgz, Loesung25.tgz
  • Dynamische Codegenerierung aus der Übung: dyncodegen.ml
• Aufgabenblatt 11
  
  • Lösung: Power.hs

Schein zur Vorlesung

• Bachelor: Der Schein ist für den Bachelorstudiengang Informatik mit 7 ECTS-Punkten anrechenbar.
• Diplom: Der Schein ist formell kein Bestandteil des Diplomstudiengangs. Es wird aber empfohlen, einen Schein zu erwerben, um eine objektive Einschätzung des Lernerfolgs zu haben.

Literatur

• Einstieg: Simon Thompson: Haskell: The Craft of Functional Programming, Addison-Wesley, 2nd ed., 1999. Signatur ST 245 H349 T4.
• Theoretische Grundlagen: Peter Thiemann: Grundlagen der funktionalen Programmierung, Teubner, 1994. Signatur ST 245 T 433. Errata
• Hintergrundliteratur
  • Richard Bird: Introduction to Functional Programming using Haskell, Prentice Hall, 2nd ed., 1998. Signatur ST 230 B618.
  • Chris Hankin: Lambda Calculi, a guide for computer scientists, Oxford University Press, 1994. Signatur SK 130 H241.
  • Anthony Field, Peter Harrison: Functional Programming, Addison-Wesley, 1988. Signatur ST 230 F453.
  • Simon Peyton Jones: The Implementation of Functional Programming Languages, Prentice Hall, 1987. Signatur ST 245 P519.
  • Martin Erwig: Grundlagen funktionaler Programmierung, Oldenbourg-Verlag, 1999. Signatur ST 245 E 73.

• Haskell 98 Standard
• GHC-Benutzerinformationen

Tools zur Programmentwicklung

• Glasgow Haskell-Compiler/Interpreter
• Scannergenerator Alex
• Parsergenerator Happy
• MetaOCaml-Compiler/Interpreter

Grafische Bedienoberflächen (GUIs) in funktionalen Programmen

• Gtk2Hs
• wxHaskell.

Hintergrundinformationen

Wissenschaftler, deren Namen in der Vorlesung erwähnt wird

• John Backus ist der Erfinder der Programmiersprache FORTRAN, der Backus-Naur-Form und der funktionalen Sprache FP
• Nach Alan Turing ist die höchste Auszeichnung in der Informatik benannt: der Turing Award der ACM (Association for Computing Machinery).
• Guiseppe Peano, nach dem die die natürlichen Zahlen definierenden Axiome benannt sind.
• Leonardo Pisano Fibonacci, nach dem die Fibonacci-Zahlen benannt sind.
• George Boole, nach dem die Booleschen Terme und die Boolesche Algebra benannt sind.
• Alonzo Church, der den Lambda-Kalkül erfand.
• Haskell Curry, nach dem das "Currying" und die funktionale Programmiersprache Haskell benannt sind.
• John von Neumann, nach dem das "von Neumann" Rechnermodell benannt ist.