Upload
others
View
0
Download
0
Embed Size (px)
Citation preview
Zürcher Fachhochschule
Funktionale Programmierung Teil 2Mehr zu funktionaler Programmierung
Programmiersprachen und -paradigmen (PSPP)
Zürcher Fachhochschule
Übersicht
• Objektorientiert oder funktional?
• OOP und FP: Beispiel in JavaScript
• Aspekte funktionaler Programmierung?
• Quellen, weitere Informationen
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 2
Zürcher Fachhochschule
Aufgabe: Perfect Numbers
• Es soll für eine Zahl entschieden werden, ob sie eine vollkommene, eine defiziente oder eine abundante Zahl ist
• Vollkommene Zahl: Summe ihrer Teiler (ausser der Zahl selbst) ist gleich der Zahl
• Vollkommene Zahlen sind selten, die kleinsten sind:6, 28, 496 und 8128
• Defiziente Zahl:Teilersumme ist kleiner als die Zahl
• Abundante Zahl:Teilersumme ist grösser als die Zahl
3pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Zürcher Fachhochschule
Erster Versuch in Java
4
public class Classifier6 {private Set<Integer> _factors;private int _number;
public Classifier6(int number) {if (number < 1) { ... }_number = number;_factors = new HashSet<Integer>>();_factors.add(1);_factors.add(_number);
}private boolean isFactor(int factor) {
return _number % factor == 0;}private void calculateFactors() {
for (int i = 1; i <= sqrt(_number) + 1; i++)if (isFactor(i)) addFactor(i);
}...
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • Quelle: Thinking functionally, Part 1 – Learning to think like a functional programmerIBM developerWorks
Zürcher Fachhochschule
Erster Versuch in Java
5
private void addFactor(int factor) {_factors.add(factor);_factors.add(_number / factor);
}
private int sumOfFactors() {calculateFactors();int sum = 0;for (int i : _factors) sum += i;return sum;
}
public boolean isPerfect() {return sumOfFactors() - _number == _number;
}
...}
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • Quelle: Thinking functionally, Part 1 – Learning to think like a functional programmerIBM developerWorks
Zürcher Fachhochschule
Erster Versuch in Java
• Typische OO-Lösung
• Zustand des Objekts in Instanzenvariablen
• Methoden zum Ändern des Zustands
• Optimierung: Teiler nur bis zur Wurzel der Zahl getestet
6pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
• Zugegeben, das ist nicht gerade eine Aufgabe, die eine objektorientierte Lösung nahelegt...
• Schrittweiser Umbau zu einer mehr funktionalen Lösung in den Ergänzungsfolien
Zürcher Fachhochschule
Perfect Numbers in Common Lisp
7
(defun is-factor (factor number)(= (rem number factor) 0))
(defun get-factors-for (number)(filter (lambda (n) (is-factor n number))
(range 2 number)))
(defun is-perfect (number)(= (reduce #'+ (cons 1 (get-factors-for number)))
number))
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
• Funktionaler Ansatz: Verben und Prädikate
• Vorerst keine Überlegung zu Optimierungsmöglichkeiten
Zürcher Fachhochschule
Exkurs: Kindom of Nouns
• Quelle: Steve Yegge, Execution in the Kingdom of Nouns
• Use Case: Ablauf:
"Johnny, take out that garbage! It's overflowing!"
8
• get the garbage bag from under the sink• carry it out to the garage• dump it in the garbage can• walk back inside• wash your hands• plop back down on the couch• resume playing your video game (or
whatever you were doing)
• get the garbage bag from under the sink• carry it out to the garage• dump it in the garbage can• walk back inside• wash your hands• plop back down on the couch• resume playing your video game (or
whatever you were doing)
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Zürcher Fachhochschule
Exkurs
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 9
carry
garbage bag
garage
carry
garbage bag garage
garbageBag.carry(garage)hands.wash()
carry(garbageBag, garage)wash(hands)
Zürcher Fachhochschule
Exkurs
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 10
Quelle: Gutes Deutsch in Schrift und Rede, Bertelsmann, 1978.
Zürcher Fachhochschule
Exkurs: Kindom of Nouns
• In unserem Denken spielen Verben eine zentrale Rolle
• Auch in natürlicher Sprache: Substantivstil ist umständlich und wenn möglich zu vermeiden
• OOP entspricht Substantivstil
11
Need to wait? Waiter.execute()Brush your teeth? ToothBrusher(myTeeth).go()
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Zürcher Fachhochschule
Exkurs: Kindom of Nouns
• Substantivstil in Java besonders ausgeprägt, da kaum Alternativen
• Notbehelfe wie anonyme innere Klassen notwendig
• Man wird kaum einen AbstractProxyMediator, eine Notification-StrategyFactory, oder ähnlich künstliche Konstrukte in einem Python- oder Ruby-Programm finden
• Python, Ruby, JavaScript, Perl und natürlich alle funktionalen Sprachen erlauben Funktionen als eigenständige Einheiten und behandeln diese als Elemente erster Klasse
12pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Zürcher Fachhochschule
Exkurs: Kindom of Nouns
13
„AdvocatingObject-OrientedProgrammingislikeadvocatingPants-OrientedClothing“(JacobGabrielson)
StateManager.getConsiderationSetter("Noun Oriented Thinking", State.HARMFUL).run()
Or, as it is said outside the Kingdom of Java:
„Noun Oriented Thinking Considered Harmful“
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Zürcher Fachhochschule
Objektorientiert oder funktional?
• Die letzte Aussage war natürlich überspitzt ... J
• Zentrale Probleme der Software-Entwicklung: Komplexität, Überblick, Abhängigkeiten, ...
• Lösungsansatz: – Problem in einfachere Teilprobleme zerlegen– Teilprobleme einzeln lösen– Lösungen zur Gesamtlösung zusammenfügen
• Unterschiedliche Antworten und Hilfsmittel in verschiedenen Programmierparadigmen
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 14
Zürcher Fachhochschule
Objektorientiert oder funktional?
• Prozeduraler Ansatz: Prozeduren, Funktionen(kombiniert mit imperativer / strukturierter Programmierung)
• Objektorientierter Ansatz: Objekte, Klassen(kombiniert mit imperativer / strukturierter Programmierung)
• Funktionaler Ansatz: Funktionen(und Mechanismen zum flexiblen Umgang mit Funktionen wie: Funktionen höherer Ordnung, Lambdas, Closures, ...)
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 15
Zürcher Fachhochschule
OOP
• Komposition von Klassen und Objekten
• Spezialisierung durch Erweiterung
• Operationen an Klassen gebunden
• Operationen führen zu Zustandsänderun-gen
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 16Bild: Michael Fogus, Functional JavaScript
Zürcher Fachhochschule
FP
• Komposition von Funktionen
• Anstatt Dingen werden Aktivitäten zerlegt
• Zustandsänderungen nach Möglichkeit vermieden
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 17Bild: Michael Fogus, Functional JavaScript
Zürcher Fachhochschule
OOP und FP
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 18http://scott.sauyet.com/Javascript/Talk/FunctionalProgramming/
Zürcher Fachhochschule
Übersicht
• Objektorientiert oder funktional?
• OOP und FP: Beispiel in JavaScript
• Aspekte funktionaler Programmierung?
• Quellen, weitere Informationen
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 19
Zürcher Fachhochschule
Datenstruktur einer TaskList-Applikation
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 20
var data = {result: "SUCCESS",interfaceVersion: "1.0.3",requested: "10/17/2013 15:31:20".lastUpdated: "10/16/2013 10:52:39",tasks: [
{id: 104, complete: false, priority: "high",dueDate: "11/29/2013", member: "Scott",title: "Do something", created: "9/22/2013"},
{id: 105, complete: false, priority: "medium",dueDate: "11/22/2013", member: "Lena",title: "Do something else", created: "9/22/2013"},
{id: 107, complete: true, priority: "high",dueDate: "11/22/2013", member: "Mike",title: "Fix the foo", created: "9/22/2013"},
// , ...]
};
Scott Sauyet: Functional Programming
Zürcher Fachhochschule
Aufgabe
• Gesucht sind alle Aufgaben – für bestimmten Member,– die noch nicht abgeschlossen sind (complete: false),– davon nur ID, Priorität, Titel, Datum,– sortiert nach Datum
• Vorerst nicht berücksichtigt:– Fehlerbehandlung– genaue Datums-Verarbeitung
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 21
Zürcher Fachhochschule
Imperativer Ansatz
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 22
var getIncompleteTaskSummariesForMember_imperative = function(memberName) {return fetchData()
.then(function(data) {return data.tasks;
}).then(function(tasks) {
var results = [];for (var i = 0, len = tasks.length; i < len; i++) {
if (tasks[i].member == memberName) {results.push(tasks[i]);
}}return results;
}).then(function(tasks) {
var results = [];for (var i = 0, len = tasks.length; i < len; i++) {
if (!tasks[i].complete) {results.push(tasks[i]);
}}return results;
})
Scott Sauyet: Functional Programming
Zürcher Fachhochschule
Imperativer Ansatz
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 23
.then(function(tasks) {var results = [], task;for (var i = 0, len = tasks.length; i < len; i++) {
task = tasks[i];results.push({
id: task.id,dueDate: task.dueDate,title: task.title,priority: task.priority
})}return results;
}).then(function(tasks) {
tasks.sort(function(first, second) {return first.dueDate - second.dueDate;
});return tasks;
});};
Scott Sauyet: Functional Programming
Zürcher Fachhochschule
Objektorientierter Ansatz
• Ähnlich imperativer Ansatz
• In einzelne Methoden aufgeteilt und Objekten zugeordnet
• “Objekttypen“ z.B.: TaskList, TaskListSorter, Task
• Eher etwas umfangreicher als imperativer Ansatz
• Dafür besser organisiert, strukturiert
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 24
Zürcher Fachhochschule
Funktionaler Ansatz
• Nun wird Schritt für Schritt eine funktionale Lösung erarbeitet
• Annahme: JS-Bibliothek, die einige typische Features funktionaler Programmierung zur Verfügung stellt
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 25
Zürcher Fachhochschule
Attributwert holen
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 26
.then(function(data) {return data.tasks;
})
.then(prop('tasks'))
// in FP-Bibliothek (z.B. Ramda) so oder ähnlich enthalten:var prop = curry(function(propty, obj) {return obj[propty];});
// oder ohne curry:var prop = function(propty) {
return function(obj) {return obj[propty];
};};
??
Zürcher Fachhochschule
Liste filtern (1)
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 27
.then(function(tasks) {var results = [];for (var i = 0, len = tasks.length; i < len; i++) {
if (tasks[i].member == memberName) {results.push(tasks[i]);
}}return results;
})
.then(filter(propEq('member', memberName)))
.then(filter(function(task) {return task.member == memberName;
}))
Zürcher Fachhochschule
Liste filtern (2)
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 28
.then(reject(propEq('complete', true)))
var propEq = function(propty, val) {return pipeline(prop(propty), eq(val));
}
• Alle Aufgaben, die bereits erledigt sind, entfernen (reject)
• propEq: könnte in FP-Bibliothek definiert sein
• Ansonsten:
Zürcher Fachhochschule
Attribute beschränken
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 29
.then(function(tasks) {var results = [], task;for (var i = 0, len = tasks.length; i < len; i++) {
task = tasks[i];results.push({
id: task.id,dueDate: task.dueDate,title: task.title,priority: task.priority
})}return results;
})
// pick und map sind curried und liefern Funktionen .then(map(pick(['id', 'dueDate', 'title', 'priority'])))
Zürcher Fachhochschule
Ergebnis sortieren
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 30
.then(function(tasks) {tasks.sort(function(first, second) {
return first.dueDate - second.dueDate;});return tasks;
});
.then(sortBy(prop('dueDate')))
• Ok, bei der Datumsbehandlung wäre noch etwas zu tun...
• Das gilt auch für die funktionale Variante:
Zürcher Fachhochschule
Abschluss
• Deutlich weniger Code (–75% loc), besser lesbar
• Ausser einem Parameter keine Variablen, keine Zuweisung
• Hintereinanderschaltung von Funktionen
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 31
var propEq = function(propty, val) { // To do: move to library?return pipe(prop(propty), eq(val));
}var getIncompleteTaskSummariesForMemberFunctional = function(memberName) {
return fetchData().then(prop('tasks')).then(filter(propEq('member', memberName))).then(reject(propEq('complete', true))).then(map(pick(['id', 'dueDate', 'title', 'priority']))).then(sortBy(prop('dueDate')));
};
Zürcher Fachhochschule
Fliessband
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 32
Bash: Sortierte Wortliste aus Menge von Textdateien:
cat *.txt | tr -cs "[a-z][A-Z]" "\012" | sort | uniq -c
A functional program is a machine for transforming data(Quelle: Michael Fogus: Functional JavaScript, Introducing Functional Programming with Underscore.js. O'Reilly, 2013)
Zürcher Fachhochschule
Übersicht
• Objektorientiert oder funktional?
• OOP und FP: Beispiel in JavaScript
• Aspekte funktionaler Programmierung?
• Quellen, weitere Informationen
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 33
Zürcher Fachhochschule
Funktionale Programmierung
• Theoretische Basis: Lambda-Kalkül
• Für den praktischen Einsatz:Programmiersprachen, die sich mehr oder weniger am Lambda-Kalkül orientieren
• Ausserdem:Eine Reihe von Merkmalen, die man mit funktionaler Programmierung verbindet
34pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Zürcher Fachhochschule
Rekursive Funktionen
• Kompakte, oft elegante Problembeschreibung
• Vermeiden von Zuweisung (auf Argumente/Stack verlagert)
• Eher Aussagen über Korrektheit möglich
35
;; Fibonacci;; Bestimmt die n-te Fibonacci-Zahl
(defun fibo (n)(cond ((< n 2) n)
(t (+ (fibo (- n 1)) (fibo (- n 2))))))
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Zürcher Fachhochschule
Rekursive Funktionen
• In funktionaler Programmierung kann Wiederholung meist durch map oder reduce ersetzt werden
• Weder Rekursion noch Schleifen sind dann nötig
• So kann beides auch als Implementierungsdetail für Funktionen auf einem höheren Abstraktionsniveau angesehen werden
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 36
„Recursion Is a Low-Level Operation“Michael Fogus: Functional JavaScript
Zürcher Fachhochschule
Tail Call Optimization
• Rekursion: Probleme mit Stack Overflow möglich
• Je nach PL: Optimierung von endrekursiven Funktionen
• Common Lisp: von den meisten Implementierungen unterstützt
• JavaScript: seit ES6
37
;; Fibonacci;; Bestimmt die n-te Fibonacci-Zahl
(defun fibo (n &optional (a 0) (b 1))(if (<= n 0) a
(fibo (- n 1) b (+ a b))))
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Zürcher Fachhochschule
Pure Funktionen
• Funktionsergebnis hängt ausschliesslich von den übergebenen Argumenten ab
• Funktion im mathematischen Sinne
• Programmieren ohne Seiteneffekte
• Vorteil u.a.: beliebige Reihenfolge der Auswertung
Referenzielle Transparenz:Der Wert eines Ausdrucks ist immer gleich, der Ausdruck kann also jederzeit durch seinen Wert ersetzt werden, ohne dadurch das Verhalten des Programms zu ändern
38pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Zürcher Fachhochschule
Pure Funktionen
f(g1(x), g2(y), g3(z))
• Völlig egal, in welcher Reihenfolge g1..g3 ausgeführt werden
• Auch parallel auf mehreren Prozessorkernen möglich
• Problem:– In realen Programmen ist das nicht ganz zu erreichen:
I/O, random(), date(), …– Wichtig: Diese Teile vom Rest trennen– Auch im Hinblick auf Test-Driven Development (TDD)
39pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Zürcher Fachhochschule
Pure Funktionen: Beispiel
40pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
function square(x) {return x * x;
}
function squareAll(items) {return items.map(square);
}
function square(x) {updateXInDatabase(x);return x * x;
}
function squareAll(items) {for (let i = 0; i < items.length; i++) {items[i] = square(items[i]);
}}
Ja, pure Funktionen Nein, kein puren Funktionen
Dan Abramov: Getting Started with Redux
Zürcher Fachhochschule
Memoizing
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 41
(defun memoize (fn)(let ((cache (make-hash-table :test #'equal)))(lambda (&rest args)(multiple-value-bind (val win) (gethash args cache)(if win
val(setf (gethash args cache)
(apply fn args)))))))
;; Memoizer an Funktion anhängen(setfun fib (memoize #'fib))
Zürcher Fachhochschule
Zustand und Veränderung
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 42
Autorvon:WorkingwithLegacyCode (viaTwitter)
Zürcher Fachhochschule
Zustand und Veränderung
• Unveränderbare Objekte können ihren Zustand nicht verändern
• Anstatt den Zustand eines solchen Objekts zu ändern wird ein neues Objekt angelegt
• Zum Beispiel: Strings in Java, Tupel in Python
• Unveränderbare Objekte sind vielseitiger einsetzbar (Schlüssel in Maps, thread-safe, ...)
• Konflikt: Die Welt verändert sich
• Ziel: Veränderung an wenigen Stellen konzentrieren
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 43
Zürcher Fachhochschule
Immutable Classes in Java
44
public final class Address {private final String name;private final List<String> streets;private final String city;private final String state;private final String zip;
public Address(String name, List<String> streets, String city, String state, String zip) {
this.name = name;this.streets = streets;this.city = city;this.state = state;this.zip = zip;
}
public String getName() {return name;
}
public List<String> getStreets() {return Collections.unmodifiableList(streets);
}
public String getCity() {return city;
}
public String getState() {return state;
}
public String getZip() {return zip;
}}
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Zürcher Fachhochschule
Redux: Avoiding Array Mutations
45
const removeCounter = (list, index) => {return [...list.slice(0, index),...list.slice(index + 1)
];};
const testRemoveCounter = () => {const listBefore = [0, 10, 20];const listAfter = [0, 20];
deepFreeze(listBefore);
expect (removeCounter(listBefore, 1)
).toEqual(listAfter);};
testRemoveCounter();console.log('All tests passed');
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Redux is a predictable state container for JavaScript apps
Three principles:
• State of the app represented by one JavaScript object
• State tree is read only
• Reducer function returns the next state – must be pure
Dan Abramov: Getting Started with Redux
Zürcher Fachhochschule
First Class Functions
• Funktionen als eigenständige Einheiten
• Verwandtes Konzept zu Funktionen höherer Ordnung (s.u.)
• Funktionen können an verschiedenen Stellen im Programm vorkommen, ebenso wie Zahlen oder Strings
• Funktionsliterale (anonyme Funktionen, Lambdas)
46
var obj = {doit: function(n) { return 2*n+1; }
}var feld = [ obj.doit, obj.doit(3), function(m){ return m; } ];
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Zürcher Fachhochschule
Einheitliche Datenstrukturen
• Einfache Datenstrukturen wie Listen oder Dictionaries
• Zahlreiche, möglichst universelle Funktionen auf diesen Datenstrukturen
• Eigentliche Aufgabe mit Funktionsparametern präzisieren
• Bilden weiterer Funktionen aus den vorhandenen
• Hoher Grad an Wiederverwendung
Zum Vergleich: objektorientierter Ansatz
• Funktionen und zugehörige Daten kapseln
47pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Zürcher Fachhochschule
Einheitliche Datenstrukturen
• JavaScript: Arrays, Objects (Hashes)
• Python: Listen, Tupel, Dictionaries
• ...
• Common Lisp: Listen, Assoziationslisten– Grundlegende Funktionen
car, cdr, length, nth, ...– Abtraktionen für bestimmte Aufgaben
mapcar, reduce, remove-if, ...– Zahlreiche weitere, knapp 1000, u.a.: last, butlast, append,
member, assoc, subseq, reverse, find, some, every, sort, ...
48pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Zürcher Fachhochschule
Einheitliche Datenstrukturen
• Basierend auf den Grundfunktionen können dann weitere generische oder spezifische Funktionen geschrieben werden
• Zum Beispiel:
49
(defun mapcat (fun coll)(apply #'append (mapcar fun coll)))
(defun interpose (inter coll)(butlast (mapcat (lambda (e) (cons e (list inter)))
coll)))
> (interpose "," '(1 2 3 4 5))(1 "," 2 "," 3 "," 4 "," 5)
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Zürcher Fachhochschule
Funktionen höherer Ordnung
• Funktionen wie reduce erhalten Funktionen als Argumente
• Solche Funktionen nennt man Funktionen höherer Ordnung
• Auch: Funktionen als Rückgabewert von Funktionen
50
Möglichkeit,generischeFunktionenzuschreibenunddurchÜbergabevonFunktionenfürspezifischeZweckezuverwenden
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Zürcher Fachhochschule
Funktionen höherer Ordnung
• Funktionen als Parameter und /oder Rückgabewert
• Mehr oder weniger umständlich in vielen Programmiersprachen
• Vielfältige Möglichkeiten zum Parametrisieren und Bilden von Funktionen
• Java 8: Lambda-AusdrückeFilenameFilter pf = (f, s) -> s.toLowerCase().endsWith(".pdf");File[] pdfs = basedir.listFiles(pf);
• C: Umständlich mit Function Pointers
• C++: Funktionsobjekte (Aufrufoperator definiert)
51pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Zürcher Fachhochschule
Funktionen höherer Ordnung (Swift)
52
func addTwoInts(a: Int, b: Int) -> Int {return a + b
}
// Funktion als Parameter:func printMathResult(mathFunction: (Int, Int) -> Int, a: Int, b: Int) {
println("Result: \(mathFunction(a, b))")}printMathResult(addTwoInts, 3, 5) // prints "Result: 8"
// Funktion als Rückgabewertfunc chooseStepFunction(backwards: Bool) -> (Int) -> Int {
return backwards ? stepBackward : stepForward}
// filter, map, reduceprintln(words.filter { $0.hasSuffix("gry") }
.map { $0.uppercaseString }
.reduce("HULK") { "\($0) \($1)" })
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Typ: Funktion mit zwei Int-Parametern, liefert Int
Zürcher Fachhochschule
Closures
53
„[...]aclosure[...]isafunctionorreferencetoafunctiontogetherwithareferencingenvironment— atablestoringareferencetoeachofthenon-localvariables(alsocalledfreevariables)ofthatfunction.[...]Theconceptofclosureswasdevelopedinthe1960sandwasfirstfullyimplementedin1975asalanguagefeatureintheSchemeprogramminglanguagetosupportlexicallyscopedfirst-classfunctions.“
Quelle:Wikipedia
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Zürcher Fachhochschule
Closures
54
(defun prefix (pre)(lambda (n) (concatenate 'string pre (format nil "~D" n))))
> (setfun id (prefix "id"))ID> (id 12)"id12"
• Closures ermöglichen es, Funktionen mit einem (ggf. anpassbaren) Zustand zu versehen
• Wenn der Zustand änderbar ist, hat man keine puren Funktionen mehr (keine referenzielle Transparenz)
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Zürcher Fachhochschule
Pattern Matching (Miranda)
• Parameter Matching entscheidet, welche Implementierung der Funktion ausgewählt wird
• Dadurch werden if-Blöcke vermieden und die Lesbarkeit erhöht
• Sprachen: Miranda, Haskell, Erlangauch: Clojure
55
rev [] = []rev (a:x) = rev x ++ [a]
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Zürcher Fachhochschule
Pattern Matching (Haskell)
56
-- Type annotation (optional)fib :: Integer -> Integer
-- Simple implementation fib 0 = 0fib 1 = 1fib n = fib (n - 2) + fib (n - 1)
-- As a list, using zipWithfibs :: [Integer]fibs = 0 : 1 : (zipWith (+) fibs (tail fibs))
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Zürcher Fachhochschule
Lazy Evaluation (Haskell)
• Um das Minimum zu bestimmen, muss die Liste mit den Zahlen grösser als x gar nicht bestimmt werden
• Sprachen: Haskell, Miranda
• Auch möglich: Einsatz unendlich grosser Listen(Python 3: Lazy Sequences mit Iteratoren)
57
quickSort [] = []quickSort (x:xs) = quickSort (filter (< x) xs)
++ [x]++ quickSort (filter (>= x) xs)
minimum ls = head (quickSort ls)
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •
Zürcher Fachhochschule
Lazy Evaluation in Clojure
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 58
iterate
function
Usage: (iterate f x)
Returns a lazy sequence of x, (f x), (f (f x)) etc. f must be free of side-effectsAdded in Clojure version 1.0
$ cljClojure 1.4.0user=> (take 20 (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)
Zürcher Fachhochschule
Programmiersprachen
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 59
• Reine funktionale Sprachen:Haskell, Miranda, ...
• Multiparadigmensprachen mit umfassender Unterstützung funktionaler Programmierung:APL, Erlang, JavaScript, Lisp-Dialekte (Common Lisp, Scheme, Clojure, ...), Scala, ...
• Zunehmende Unterstützung funktionaler Programmierung in vielen anderen Programmiersprachen:PHP, Python, ...
Zürcher Fachhochschule
Programmiersprachen
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 60
• Reine funktionale Sprachen:Haskell, Miranda, ...
-- Factorial using recursionfactorial 0 = 1factorial n | n > 0 = n * factorial (n - 1)
-- Using recursion but written without pattern matchingfactorial n = if n > 0 then n * factorial (n-1) else 1
-- Using a listfactorial n = product [1..n]
-- Using fold (implements product)factorial n = foldl1 (*) [1..n]
Zürcher Fachhochschule
Programmiersprachen
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 61
• Multiparadigmensprachen mit umfassender Unterstützung funktionaler Programmierung:APL, Erlang, JavaScript, Lisp-Dialekte (Common Lisp, Scheme, Clojure, Arc...), Scala, ...
(define (map f lst)(if (null? lst)
'()(cons (f (car lst)) (map f (cdr lst)))))
Zürcher Fachhochschule
Programmiersprachen
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 62
• Zunehmende Unterstützung funktionaler Programmierung in vielen anderen Programmiersprachen:PHP, Python, ...
• Anonyme Funktionen seit PHP 5.3
• Umgang mit Arrays: range, array_map, array_filter, array_reduce
array_filter(range(0, 10), function($val) { return $val % 2 == 0; });
array_map(function($val) { return $val * $val; }, range(0, 100, 10));
Zürcher Fachhochschule
Python
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 63
>>> [x for x in range(10) if is_even(x)][0, 2, 4, 6, 8]
>>> from functools import reduce>>> import operator
>>> reduce(operator.mul, [1,2,3], 1)6
>>> list(filter(lambda x: x % 3 == 0, range(0, 100, 7)))[0, 21, 42, 63, 84]
Zürcher Fachhochschule
Übersicht
• Objektorientiert oder funktional?
• OOP und FP: Beispiel in JavaScript
• Aspekte funktionaler Programmierung?
• Quellen, weitere Informationen
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 64
Zürcher Fachhochschule
Quellen und weitere Informationen
• John Hughes: Why Functional Programming Matters (PDF)http://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf
• Scott Sauyet: Functional Programming (Slides)http://scott.sauyet.com/Javascript/Talk/FunctionalProgramming/
• Michael Fogus: Functional JavaScript, Introducing Functional Programming with Underscore.js, O'Reilly, 2013
• IBM developerWorks: Artikelserie Functional Thinkinghttp://www.ibm.com/developerworks/
• Erster Artikel dieser Serie: Thinking functionally, Part 1http://www.ibm.com/developerworks/java/library/j-ft1/index.html
• Dan Abramov: Getting Started with Redux (Tutorial)https://egghead.io/courses/getting-started-with-redux
• Steve Yegge: Execution in the Kingdom of Nounshttp://steve-yegge.blogspot.ch/2006/03/execution-in-kingdom-of-nouns.html
pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 • 65
Zürcher Fachhochschule
Ziel erreicht?
• Sie verstehen die Unterschiede zwischen dem objektorientierten und dem funktionalen Paradigma
• Sie kennen die wichtigsten Merkmale funktionaler Program-mierung und können diese anhand von Beispielen erklären
66pspp • funktionale programmierung (2) • gerrit burkert • 11/2019 •