FP-1.0 Funktionale Programmierung Prof. Dr. Uwe Kastens SS 2013 (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Funktionale Programmierung SS 2013 / Folie 100 Ziele: Begrüßung -------------------------------------------------------------------------------- FP-1.1 Functional Programming is Fun Fun ctional Programming is Fun ctional Programming is Fun ctional Programming is Fun ctional Programming is Fun ctional Programming is Fun ctional Programming is (c) 2004 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Funktionale Programmierung SS 2013 / Folie 101 Ziele: Motivation -------------------------------------------------------------------------------- FP-1.2 Ziele, Material Die Teilnehmer sollen * die Klarheit und Mächtigkeit der funktionalen Programmierung erkennen, * Paradigmen der funktionalen Programmierung erlernen, * Techniken der funktionalen Programmierung an praktischen Beispielen erproben und einüben Literatur: * Vorlesungsmaterial: http://ag-kastens.upb.de/lehre/material/fp * Textbuch: L. C. Paulson: ML for the Working Programmer, 2nd Edition, Cambridge University Press, 1996 Schwerpunkt stärker auf Paradigmen und Techniken als auf der Sprache SML, enthält viele Beispiele bis hin zu nützlichern Modulen. * Weiteres Buch zu SML: C. Myers, C. Clack, E.Poon: Programming with Standard ML, Prentice Hall, 1993 * siehe auch Internet-Links im Vorlesungsmaterial http://ag-kastens.upb.de/lehre/material/fp/wwwrefs.html (c) 2010 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Funktionale Programmierung SS 2013 / Folie 102 Ziele: Ziele und Durchführung klären in der Vorlesung: * Ziele, Material erläutern, * Übungen planen Verständnisfragen: Was sind Ihre Ziele? -------------------------------------------------------------------------------- FP-1.3 Inhalt Kapitel im Textbuch 1. Einführung 2. LISP: FP Grundlagen 3. Grundlagen von SML 2 4. Programmierparadigmen zu Listen 3 5. Typkonstruktoren, Module 2, 4, 7 6. Funktionen als Daten 5 7. Datenströme 5 8. Lazy Evaluation 9. Funktionale Sprachen: Haskell, Scala 10. Zusammenfassung (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Funktionale Programmierung SS 2013 / Folie 103 Ziele: Übersich über den Inhalt bekommen in der Vorlesung: Themen und Zusammenhang zum Textbuch erläutern -------------------------------------------------------------------------------- FP-1.4 Vorkenntnisse in FP aus Modellierung, GPS und PLaC Modellierung: * Modellierung mit Wertebereichen GPS: * Datentypen, parametrisierte Typen (Polytypen) * Funktionale Programmierung: SML-Eigenschaften: Programmiertechniken: * Notation * Rekursion zur Induktion * Deklarationen, Muster * Rekursion über Listen * Funktionen, Aufrufe * akkumulierender Parameter * Listen * Berechnungsschemata (HOF) * Datentypen, Polymorphie * Currying (HOF) PLaC: * Spracheigenschaften und ihre Implementierung * Typsysteme, Typanalyse für funktionale Sprachen (c) 2010 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Funktionale Programmierung SS 2013 / Folie 104 Ziele: Voraussetzungen für die Vorlesung FP klären in der Vorlesung: * Bezug der genannten Themen zu Abschnitten dieser Vorlesung herstellen, * Vereinbaren, welche Themen selbständig wiederholt werden und welche in der Vorlesung wiederholt und dann vertieft werden. Verständnisfragen: Beherrschen Sie die hier genannten Themen? -------------------------------------------------------------------------------- FP-1.5 Gedankenexperiment Wähle eine imperative Sprache, z. B. Pascal, C. Erlaube Eingabe nur als Parameter und Ausgabe nur als Ergebnis des Programmaufrufes. Eliminiere Variablen mit Zuweisungen. Eliminiere schrittweise alle Sprachkonstrukte, die nicht mehr sinnvoll anwendbar sind. eliminiertes Sprachkonstrukt Begründung ... ... ... ... Betrachte die restliche Programmiersprache. Ist sie sinnvoll anwendbar? Erweitere sie um nützliche Konstrukte (nicht Variablen mit Zuweisungen) ergänztes Sprachkonstrukt Begründung ... ... ... ... (c) 2010 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Funktionale Programmierung SS 2013 / Folie 105 Ziele: Imperative und funktionale Sprachkonstrukte klassifizieren in der Vorlesung: Die Gedankenexperimente werden gemeinsam diskutiert. -------------------------------------------------------------------------------- FP-2.1 2. LISP: FP Grundlagen Älteste funktionale Programmiersprache (McCarthy, 1960). Viele weit verbreitete Weiterentwicklungen (Common LISP, Scheme). Ursprünglich wichtigste Sprache für Anwendungen im Bereich Künstlicher Intelligenz. Hier nur Pure LISP: Notation: geklammerte Folge von Symbolen gleiche Notation für Programm und Daten Datenobjekte: Listen: (1 2 3 4) (ggt 24 36) atomare Werte: T, F, NIL, Zahlen, Bezeichner Beispiel: Fakultätsfunktion mit akkumulierendem Parameter (defun nicht in Pure Lisp) (defun AFac (n a) (cond ((eq n 0) a) (T (AFac (- n 1) (* a n))))) (defun Fac (n) (AFac n 1)) Aufruf: (Fac 4) (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Funktionale Programmierung SS 2013 / Folie 201 Ziele: Zurück zu den Wurzeln der Funktionalen Programmierung in der Vorlesung: An Beispielen wird ein erster Eindruck von LISP gegeben Übungsaufgaben: Vergleichen Sie die Funktion mit der Notation in SML -------------------------------------------------------------------------------- FP-2.2 Grundfunktionen Aufruf: (e0 e1 ... en). Ausdruck e0 liefert die aufzurufende Funktion, die übrigen liefern Werte der aktuellen Parameter. Grundfunktionen: (cons e l) Listenkonstruktor (car l) Listenkopf (cdr l) Listenrest (null l) leere Liste? (eq a b) Vergleich atomarer Werte (equal l1 l2) tiefer Vergleich von Listen (atom e) atomar? (cond (p1 e1) ... (pn en)) Fallunterscheidung; nicht-strikte Auswertung: (pi ei) von links nach rechts auswerten bis ein pj T liefert; Ergebnis ist dann ej. (quote e) e wird nicht ausgewertet, sondern ist selbst das Ergebnis (lambda (x1 ... xn) e) Funktionskonstruktor mit formalen Parametern x1...xn und Funktionsrumpf e nicht in Pure Lisp: (setq x e) Wert von e wird an x gebunden (top level) (defun f (x1 ... xn) e) Funktion wird an f gebunden (top level) (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Funktionale Programmierung SS 2013 / Folie 202 Ziele: Grundfunktionen von LISP verstehen in der Vorlesung: An Beispielen wird erläutert: * Notation, * Vergleiche, * Bedingungskonstrukt, * Striktheit, * Lambda-Ausdruck * Bindungen mit setq und defun * top-level des Interpretierers -------------------------------------------------------------------------------- FP-2.3 Listen als Programm und Daten Eine Liste ist eine evtl. leere Folge von Ausdrücken; Jeder Ausdruck ist ein Atom oder eine Liste: '() nil '((A B C) (D (E F))) nil nil A B C D nil E F (cdr (cdr '(1 2 3 4))) Ein Aufruf ist eine Liste; beim Auswerten liefert ihr erstes Element eine Funktion; die weiteren Elemente liefern die aktuellen Parameterwerte des Aufrufes. Ein Programm ist eine Liste von geschachtelten Aufrufen. Das Programm operiert auf Daten; sie sind Atome oder Listen. Die Funktion quote unterdrückt die Auswertung eines Ausdruckes; der Ausdruck selbst ist das Ergebnis der Auswertung: Die Auswertung von (quote (1 2 3 4)) liefert (1 2 3 4) Kurznotation für (quote (1 2 3 4)) ist '(1 2 3 4) Listen, die Daten in Programmen angeben, müssen durch quote gegen Auswerten geschützt werden: (length (quote 1 2 3)) oder (length '(1 2 3)) (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Funktionale Programmierung SS 2013 / Folie 203 Ziele: Listennotation und -darstellung verstehen in der Vorlesung: An Beispielen wird erläutert: * Listennotation: verkettete Paare, * Programme und Daten bestehen aus Listen und Atomen, * Unterdrückung der Auswertung verstehen (quote) -------------------------------------------------------------------------------- FP-2.4 Einige Funktionen über Listen Länge einer Liste: (defun Length (l) (cond ((null l) 0) (T (+ 1 (Length (cdr l)))))) Aufruf (Length '(A B C)) liefert 3 Map-Funktion (map ist vordefiniert): (defun Map (f l) (cond ((null l) nil) (T (cons (funcall f (car l)) (Map f (cdr l)))))) Aufruf (Map (lambda (n) (cons n (cons n nil))) '(1 2 3)) liefert '((1 1) (2 2) (3 3)) (funcall f p) wertet f zu einer Funktion aus und ruft diese mit dem Parameter p auf (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Funktionale Programmierung SS 2013 / Folie 204 Ziele: Notation und Struktur von Funktionen verstehen in der Vorlesung: An Beispielen wird erläutert: * Funktionen lesen, * aufrufen, * umformulieren in SML -------------------------------------------------------------------------------- FP-2.5 Statische oder dynamische Bindung von Namen dynamischer statischer Vorgänger Vorgänger test def x = 21 Aufrufkeller test x 21 f x g x 42 g def x = 42 f Benutzung von x (f ()) statische Bindung von x: nächste Definition von x auf der statischen Vorgängerkette, d. h. in der Definitionsumgebung (g ()) dynamische Bindung von x: nächste Definition von x auf der dynamischen Vorgängerkette, d. h. in der Aufrufumgebung (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Funktionale Programmierung SS 2013 / Folie 205 Ziele: Dynamische Bindung verstehen in der Vorlesung: Am Beispiel wird erläutert: * statische Bindung bei geschachtelten Funktionen, * Laufzeitkeller mit statischen und dynamischen Vorgängerverweisen, * dynamische Bindung * Regelung in LISP: ursprünglich dynamische Bindung Übungsaufgaben: Explorieren Sie, welche Bindung in Common LISP gilt. -------------------------------------------------------------------------------- FP-2.5a Statische oder dynamische Bindung in Common Lisp? Bindungen in geschachtelten Lambda-Ausdrücken: (print ((lambda (x) ; Umgebung test1 bindet x ((lambda (f) ; Umgebung test2 bindet f ((lambda (x) ; Umgebung g bindet x (funcall f 1) ; Aufruf von f benutzt ein x ) 42 ; gebunden an g.x ) ) (lambda (n) x) ; gebunden an test2.f, benutzt x ) ) 21 ; gebunden an test1.x ) ) Ergebnis bei statischer oder bei dynamischer Bindung? (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Funktionale Programmierung SS 2013 / Folie 205a Ziele: Bindung von Namen in LISP in der Vorlesung: Es wird erläutert: * Struktur des Programms entspricht der auf der vorigen Folie. * Das Programm enthält keine Variablen - nur Parameter. * Am Ergebnis der Ausführung kann statische von dynamischer Bindung unterschieden werden. -------------------------------------------------------------------------------- FP-2.6 Bindungen und Closures Definition (freie Variable): Wenn ein Name x innerhalb einer Funktion f nicht durch eine Parameterdefinition oder eine lokale Definition gebunden ist, dann bezeichnet x eine freie Variable bezüglich der Funktion f. Beispiele: fun f (a, b) = a*x+b fn (a, b) => a*x+b (defun f (a b) (+ (* a x) b)) (lambda (a b) (+ (* a x) b)) Beim Aufruf einer Funktion f werden ihre freien Variablen je nach statischer oder dynamischer Bindung in der Definitions- oder Aufrufumgebung gebunden. Funktionen können als Daten verwendet werden: Funktionen als Parameter, Ergebnis, Komponente von zusammengesetzten Werten, Wert von Variablen (imperativ). Für den Aufruf benötigen sie eine Closure: Die Closure einer Funktion f ist eine Menge von Bindungen, in der beim Aufruf von f die freien Variablen von f gebunden werden. Dynamische Bindung: Closure liegt im Aufrufkeller. Statische Bindung: Closure ist in der Kette der statischen Vorgänger enthalten; diese müssen ggf. auf der Halde statt im Laufzeitkeller gespeichert werden, da Schachteln (und deren Variablen) noch benötigt werden, wenn ihr Aufruf beendet ist (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Funktionale Programmierung SS 2013 / Folie 206 Ziele: Closures verstehen in der Vorlesung: An Beispielen wird erläutert: * Aufruf von Funktionen als Daten, * Bindung freier Variable in der Closure des Aufrufes. --------------------------------------------------------------------------------