Upload
zuehlke
View
390
Download
0
Embed Size (px)
DESCRIPTION
Funktionale Programmierung bietet viele Möglichkeiten, die Herausforderungen moderner Multi-Core-Rechner einfacher als mit klassischer OO-Programmierung zu bewältigen. Dadurch verlieren Objekte ihre dominante Rolle und damit die klassische Design- und Architekturmuster einen Teil ihrer Basis. Wir zeigen, welche Muster nicht mehr benötigt werden, welche in abgewandelter Form weiterhin bestehen und welche neuen Muster und Konstruktionsprinzipien wichtig und hilfreich sind. Die Grundideen können auch in der OO-Welt profitabel eingesetzt werden.
Citation preview
© Zühlke 2011
Januar 2011
Dr. Klaus Alfert Dr. Bernd Löchner
Folie 1
Jenseits von Fakultät und Fibonacci: Architektur Funktionaler Programme
Dr. Klaus Alfert Dr. Bernd Löchner
© Zühlke 2011
Januar 2011
Dr. Klaus Alfert Dr. Bernd Löchner
Folie 3
Warum ist Funktionale Programmierung in vieler Munde?
Sun T 2 »Niagara 2« 2007, 8 Cores × 8 Threads
Intel i7 »Nehalem« 2008, 4 Cores × 2 Threads
IBM POWER 7, 2010, 8 Cores × 4 Threads
Oracle T 3 »Rainbow Falls« 2010, 16 Cores × 8 Threads
Intel Cloud Computing on a Chip 2009, 48 Cores (Prototyp)
© Zühlke 2011
Januar 2011
Dr. Klaus Alfert Dr. Bernd Löchner
Folie 9
Warum ist Nebenläufigkeit mit Objekten schwierig?
Objekte haben eine Identität
:2 :3
:1
Objekte haben einen (lokalen) Zustand
:2 :3
:1
Objekte haben Verhalten
:2 :3
:1
Multithreading erfordert Locks
:2 :3
:1
Ein hoher Grad an Nebenläufigkeit wird leicht unübersichtlich
:2 :3
:1
Ein hoher Grad an Nebenläufigkeit wird leicht unübersichtlich
:2 :3
:1
Wie kann funktionale Programmierung hier helfen?
© Zühlke 2011
Januar 2011
Dr. Klaus Alfert Dr. Bernd Löchner
Folie 17
Was unterscheidet FP von OOP?
© Zühlke 2011
Zu den Programmbeispielen
Beispiele in Haskell & Erlang
• Haskell ist puristisch elegant
• Erlang hat Industrial-Strength
Die Beispiele sind aber alle übertragbar in andere funktionale Programmiersprachen. F#
© Zühlke 2011
A LISP programmer knows the value of everything, but
the cost of nothing.
–Alan J. Perlis Epigrams of Programming
© Zühlke 2011
Werte, Variablen, Veränderliche
Was sind imperative Variablen?
• Namen für Adressen von Speicherzellen
• Abstraktionsniveau: Assembler
• Objekte haben eine Identität: Entspricht einer Adresse von Speicherzellen
Was sind funktionale Variablen?
• Namen für Werte: „Sei x beliebig, aber fest“
• Variablen werden an Werte „gebunden“
• Abstraktionsniveau: Mathematik
• Notwendig: Effiziente Abbildung auf Speicherzellen durch Laufzeitsystem
42
42
x
x
Objekte versus Werte
:1 42 :1 42 :1 42
Funktionen erzeugen aus alten Werte neue!
:2 42 42 42
Copy Gleich, aber nicht identisch
Gleich und identisch
© Zühlke 2011
© Zühlke 2011
Rekursion statt Iteration: Hyper-Fakultät (Sloane: A Handbook of Integer Sequences)
Fakultät ist für Kinder – Hyper-Fakultät ist für Erwachsene
H(n) = 1, 1, 4, 108, 27648, 86400000, 4031078400000, 3319766398771200000, 55696437941726556979200000, 21577941222941856209168026828800000, 215779412229418562091680268288000000000000000, 61564384586635053951550731889313964883968000000000000000, …
n
k
kknH1
)(
© Zühlke 2011
Rekursion statt Iteration: Hyper-Fakultät (Sloane: A Handbook of Integer Sequences)
Imperativ: Zuweisungsorientiert
hfac(n): r := 1; while n > 0 do r := r * n^n; n := n – 1; od return r;
Rekursiv: Werteorientiert
hfac(n)-> if n == 0 then 1 else n^n * hfac(n-1)
© Zühlke 2011
Rekursion statt Iteration: Hyper-Fakultät (Sloane: A Handbook of Integer Sequences)
Imperativ: Zuweisungsorientiert
hfac(n): r := 1; while n > 0 do r := r * n^n; n := n – 1; od return r;
Berechnung: hfac(3)
3 n
? r 1 27
2
108
1
108
0
© Zühlke 2011
Rekursion statt Iteration: Hyper-Fakultät (Sloane: A Handbook of Integer Sequences)
Imperativ: Zuweisungsorientiert
hfac(n): r := 1; while n > 0 do r := r * n^n; n := n – 1; od return r;
Rekursiv: Werteorientiert
hfac(n)-> if n == 0 then 1 else n^n * hfac(n-1)
© Zühlke 2011
Rekursion statt Iteration: Hyper-Fakultät (Sloane: A Handbook of Integer Sequences)
Berechnung:
Rekursiv: Werteorientiert
hfac(n)-> if n == 0 then 1 else n^n * hfac(n-1)
if n == 0 then 1 else n^n * hfac(n-1)
3 n fun
hfac(3)
if n == 0 then 1 else n^n * hfac(n-1)
2 n fun
if n == 0 then 1 else n^n * hfac(n-1)
1 n fun
hfac(2)
hfac(1)
hfac(0)
if n == 0 then 1 else n^n * hfac(n-1)
0 n fun
1 1
1
4
108
Komplexe Werte sind oft baumartig
D11
D112 D111
C D A B
C1 C2
C21 C22 D12
D122 D121
D1
{ vorname : „Martin“, nachname : „Mustermann“, anschrift : { strasse : „Hauptstrasse 23“, ort : { plz : „76541“, stadt : „Neustadt“ } }, kurse : [ { id : „Mo1“, title: „Tutorial C#“ }, { id : „Ndo4“, title: „Architektur“ } ] }
Wie ändert man komplexe Werte?
5
8 3
15
20
21 18
26
27 25
28
35
41 33
24
update (Tree, Value) Tree
Update: Ersetze 41 durch 42
5
8 3
15
20
21 18
26
27 25
28
35
41 33
24
28
24
35
42
Alter Baum Neuer Baum
Beide Bäume existieren gleichzeitig!
© Zühlke 2011
Pattern Matching
sum ([]) -> 0; sum ([X | Xs]) -> X + sum (Xs).
abs (N) when N >= 0 -> N; abs (N) -> -N.
length [] = 0 length (x:xs) = 1 + length xs
zip [] _ = [] zip _ [] = [] zip (x:xs) (y:ys) = (x,y) : zip xs ys
© Zühlke 2011
Higher-order Funktionen, Polymorphie und Lambda-Ausdrücke
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
map abs [-2 .. 2]
>> [2, 1, 0, 1, 2]
map (\x -> x*x) [-2 .. 2]
>> [4, 1, 0, 1, 4]
© Zühlke 2011
Algebraische Datenstrukturen
data Tree a = Empty
| Node (Tree a) a (Tree a)
mapTree :: (a -> b) -> Tree a -> Tree b
mapTree f Empty = Empty
mapTree f (Node l x r) =
Node (mapTree f l) (f x) (mapTree f r)
data Color = Green | Red | ...
autumn t = mapTree change t
where change Green = Red
change c = c
© Zühlke 2011
Erlang hat Closures – und Clojure auch (und Scala, F#, …)
mk_mul_abs (M) -> fun (N) when N > 0 -> M * N; (N) -> M * (-N) end.
Ma3 = mk_mul_abs (3). lists:map(Ma3, [-2, -1, 0, 1, 2]).
>> [6, 3, 0, 3, 6]
when N > 0 -> M * N; M * (-N)
3
N fun
mk_mul_abs M
Ma3
© Zühlke 2011
Haskell erlaubt Partial Application
parabola a b c x = a*x^2 + b*x + c
p1 :: Double -> Double
p1 = parabola 4.2 -2.0 3.5
y = p1 1.0
linear = parabola 0.0
l1 = linear 3.0 2.1
a*x^2 + b*x + c
3.5 x fun
fun c
p1 fun b
a fun
-2.0
4.2
a*x^2 + b*x + c
x c b a fun
© Zühlke 2011
Programmierung im Großen
Verantwortlichkeiten bündeln
• Module, APIs und Interfaces
• Kontrakte: Daten, Funktionen, Eigenschaften
Information Hiding
• Sichtbarkeiten, Namespaces
• Implementierungsinterna verbergen
Wie in OOP:
Benötigt Augenmaß und Disziplin
Beispiel: Pattern Matching
Werteorientierung und Higher-order Funktionen
ermöglichen andere Schnittstellen und Kontrakte
Funktionale Programmierung = Werteorientierung & Higher-order Funktionen
Welche Auswirkungen hat Funktionale Programmierung auf Architektur und Design?
Eoin Wood: Software architecture is the set of design decisions which, if made incorrectly, may cause your project to be canceled.
Grady Booch: Architecture represents the significant design decisions that shape a system, where significant is measured by cost of change.
ANSI/IEEE 1471-2000 The fundamental organization of a system, embodied in its components, their relationships to each other and the environment, and the principles governing its design and evolution.
ANSI/IEEE 1471-2000 The fundamental organization of a system, embodied in its components, their relationships to each other and the environment, and the principles governing its design and evolution.
High-Level Architektur
Architektur auf Marketing-Niveau: Ein typisches „Marchitecture“-Diagramm
DB
System im Fokus
DWH
CRM Server
Auftrags-verwaltung
Kunden-verwaltung
Pricing Logistik
Enterprise Architektur: Funktionalität bleibt lokal, Kommunikation über Werte
DB
System im Fokus
DWH
CRM Server
Auftrags-verwaltung Kunden-
verwaltung
Pricing Logistik HTML
JSON/REST
QuerySet
AMQP
SOAP
Service Bus
Portal Server
MQ SOAP
Host
SOAP
© Zühlke 2011
High Level Architektur: Grobzerlegung bleibt bestehen
Treiber:
• Primär fachliche Zerlegung in Aufgaben- und Verantwortlichkeitsgebiete
• Reflektiert auch die Organisation (Conway’s Law)
Konsequenzen
• Architektur auf dieser Ebene ist unabhängig von der Implementierungstechnologie
• Interna der Komponenten/Subsysteme sind irrelevant
• Kommunikation erfolgt über Werte, Funktionen bleiben lokal und werden nicht transportiert
Mittlere Architektur
Mittlere Architektur: Geprägt von nicht-funktionalen Systemanforderungen
Portabilität Wartbarkeit
Funktionalität
Zuverlässig- keit
Bedienbarkeit
Effizienz Dokumentation
Machbarkeit
Gliederung gemäß ISO/IEC 9126
Enterprise Java
© Zühlke 2011
Ein Blick auf Enterprise Java
Historisch:
• Transaktionsmonitor für verteilte Objekte
• Anbindung an (Legacy)-Datenbanken
Ausgelegt für
• Informationssysteme
• Hohen Durchsatz
• Skalierbarkeit
PortabilitätWartbarkeit
Funktionalität
Zuverläs-sigkeit
Bedienbarkeit
EffizienzDoku-
mentationMachbarkeit
© Zühlke 2011
Struktur: N-Tier-Schichtenarchitektur
http://download.oracle.com/javaee/6/tutorial/doc/bnaay.html
© Zühlke 2011
Einfluss von Java
Everything is an Object
• Auch für Dinge, die eigentlich keine Objekte sind (Stateless Session Beans, MDB, Backing Beans, Servlets, Transaktionen)
Transparente Remote-Aufrufe (RMI)
Thread-Management nur im Container
• Das Lock-Model von Java erlaubt keine Komposition von Concurrent Libraries
Interfaces anstatt abstrakter Klassen
Erlang/OTP
To Iterate is Human, to Recurse Divine – L. Peter Deutsch
© Zühlke 2011
Ein Blick auf Erlang/OTP
Historisch:
• Soft-Realtime Systeme, PBX, Telco
Ausgelegt für
• (sehr hohe) Zuverlässigkeit und Fehlertoleranz
• Skalierbarkeit mit massiver Parallelität
• Kommunikationssysteme
Anwendungsbeispiele
• Diverse Telco-Systeme von Ericsson
• Ejabberd, RabbitMQ, CouchDB PortabilitätWartbarkeit
Funktionalität
Zuverläs-sigkeit
Bedienbarkeit
EffizienzDoku-
mentationMachbarkeit
OTP besteht aus lose gekoppelten „Anwendungen“ …
Anwendung Web Server
odbc
crypto
gen_tcp
uses
… und aus Supervisor-Prozesshierarchien
Anwendung
Supervisor
Worker Supervisor
Worker Worker überwacht
© Zühlke 2011
Einfluss von Erlang auf OTP
Erlang stellt die Basismechanismen bereit
• Pure Funktionen, Datenstrukturen sind immer Werte
• Nebenläufigkeit durch Prozesse – Prozesse sind referenzierbar Entitäten im Sinne von Domain Driven Design
– Halten lokalen State, teilen sich aber keinen State!
• Massive Parallelität durch leichtgewichtige Prozesse und asynchrones Messaging
• Monitoring von Prozessen über VM-Grenzen hinaus
• Hot-Code Swapping: Updates im laufenden System
Nachbau in Scala: Akka (www.akka.io)
© Zühlke 2011
Mittlere Architektur: Domäne der Blue-Print-Architekturen
Standardarchitektur für eine bestimmte Systemklasse
• Anwendungsdomäne und -typ sind relevant
• Abgestimmt auf Hardware und Infrastruktur
Geprägt von den nicht-funktionalen Anforderungen
• Priorisierung und Balancierung der Qualitätsattribute
Das technisch Machbare bestimmt den Lösungsraum
• Programmiersprachen
• Laufzeitsysteme
• Bibliotheken PortabilitätWartbarkeit
Funktionalität
Zuverlässig-keit
Bedienbarkeit
EffizienzDokumentation
Machbarkeit
PortabilitätWartbarkeit
Funktionalität
Zuverlässig-keit
Bedienbarkeit
EffizienzDokumentation
Machbarkeit
Kleinteilige Architektur
© Zühlke 2011
© Zühlke 2011
Peter Norvig: Design Patterns in Dynamic Languages (1998) Analyse der Design Patterns aus Lisp/Dylan-Sicht
• GoF verwendet C++ und Smalltalk
Unterscheidung von Implementierungsebenen
• Unsichtbar: Wird von der Sprache abgedeckt
• Informell: Wird jedes mal neu implementiert
• Formell: Implementierung mit Template oder Macro
Norvigs Fazit für die 23 GoF Patterns:
• 16 werden deutlich einfacher oder unsichtbar
© Zühlke 2011
GoF Command Pattern
http
://e
n.w
ikip
edia
.org
/wik
i/Co
mm
and_
patte
rn
© Zühlke 2011
Ein Command ist eine Closure
shutdown_command(Receiver) -> fun() -> Receiver ! {shutdown, now} end.
@Client: MyMachine = …, Cmd = shutdown_command(MyMachine),
add_action(Cmd, Target),
@Target: ... Cmd().
Receiver ! {shutdown, now}
MyMachine
() fun
fun Receiver
Cmd
© Zühlke 2011
Commands mit Undo sind Closures mit Pattern Matching
start_command(Receiver) -> fun(do) -> Receiver ! {start, now}; (undo) -> Receiver ! {shutdown, now} end.
@Client MyMachine = …, Cmd = start_command(MyMachine),
@Target ... Cmd(do), ... Cmd(undo).
Receiver ! {start, now}
MyMachine
(do) fun
fun Receiver
Cmd
Receiver ! {shutdown, now}
(undo)
GoF Visitor Pattern
Ein Composite
http
://e
n.w
ikip
edia
.org
/wik
i/Vi
sito
r_pa
ttern
“Languages that support double- or multiple dispatch lessen the need for the Visitor pattern.
(CLOS actually supports multiple dispatch).” [GoF: p.339]
Composite = Algebraischer Datentyp Visitor = Durchlauf der Struktur
data CarElement = Car [CarElement] | Wheel String | Body | Engine
toString Body = ["Visit Body"] toString Engine = ["Visit Engine"] toString (Wheel s) = ["Visit Wheel " ++ s] toString (Car es) = concat (map toString es) ++ ["Visit Car"]
doCar Body = ["Moving my Body"] doCar Engine = ["Starting my Engine"] doCar (Wheel s) = ["Kicking Wheel " ++ s] doCar (Car es) = concat (map doCar es) ++ ["Starting my Car"]
Die Java Implementierung bei Wikipedia braucht dafür ca. 100 Zeilen
© Zühlke 2011
Charakteristik der GoF Patterns (1)
Creational Patterns
• Factories und Builder lösen allgemeine Probleme, unabhängig von OO, auch in C, Modula2, Haskell, Erlang
• Prototypen und Singletons verschwinden
Structural Patterns
• Interface-Probleme und -Lösungen sind sprachunabhängig (Facade, Bridge, Adapter, Proxy)
• Composite und Decorator werden unsichtbar
© Zühlke 2011
Charakteristik der GoF Patterns (2)
Behavioral Patterns
• Können durch Lambdas, Pattern Matching, … anders realisiert werden.
• Einige werden unsichtbar, andere sind nicht immer offensichtlich umzusetzen.
Generelle Beobachtung:
• Patterns, die auf Objektidentitäten basieren, müssen ganz anders umgesetzt werden.
© Zühlke 2011
Januar 2011
Dr. Klaus Alfert Dr. Bernd Löchner
Folie 69
Funktionale Patterns
http://www.flickr.com/photos/robbie73/
© Zühlke 2011
Standardisierte Rekursion
Listenfunktionen in Haskell:
sum [] = 0 sum (x:xs) = x + sum xs
product [] = 1 product (x:xs) = x * product xs
allTrue [] = True allTrue (x:xs) = x && allTrue xs
Extrahiere das Rekursionsschema
foldList startVal combFct [] = startVal foldList startVal combFct (x:xs) = combFct x (foldList startVal combFct xs)
sum = foldList 0 (+)
product = foldList 1 (*)
allTrue = foldList True (&&)
© Zühlke 2011
Standardisierte Rekursion
Mit foldList können viele Listenfunktionen implementiert werden
length [] = 0 length (x:xs) = 1 + length xs
map f [] = [] map f (x:xs) = f x : map f xs
length = foldList 0 cFct where cFct x len = 1 + len
map f = foldList [] cFct where cFct x ys = f x : ys
© Zühlke 2011
Standardisierte Rekursion für Algebraische Datentypen
Generalisiere für andere Datenstrukturen data Tree a = Empty
| Node (Tree a) a (Tree a)
foldTree eVal cFct Empty = eVal
foldTree eVal cFct (Node l x r) =
cFct (foldTree eVal cFct l) x (foldTree eVal cFct r)
sumTree = foldTree 0 cFct where cFct sl x sr = sl + x + sr
mapTree f = foldTree Empty cFct where cFct ml x mr = Node ml (f x) mr
heightTree = foldTree 0 cFct where cFct hl x hr = 1 + max hl hr
© Zühlke 2011
Auch im Visitor findet sich strukturierte Rekursion
data CarElement = Car [CarElement] | Wheel String | Body | Engine
visit :: (CarElement -> a) -> CarElement -> [a] visit f (Car es) = concat (map (visit f) es) ++ [f (Car es)] visit f x = [f x]
printCar car = visit toString car where toString Body = "Visit Body" toString Engine = "Visit Engine" toString Wheel s = "Visit Wheel " ++ s toString Car es = "Visit Car"
Separation of Concerns
© Zühlke 2011
Recursion is the goto of functional programming.
–Erik Meijer
© Zühlke 2011
Leichtgewichtige Threads
Erlang Prozesse sind nebenläufige, meist rekursive Funktionen
CalcProc = spawn(fun() -> calc_loop(0))
calc_loop(Acc) -> NewAcc = receive {mul, X} -> Acc * X; {add, X} -> Acc + X; clear -> 0; {get, Pid} -> Pid ! {result, Acc}, Acc; _IgnoredMsg -> Acc end, calc_loop(NewAcc).
Auswahl der Nachrichten durch Pattern Matching
Funktioniert dank Tail Call Optimization
Nebenläufige Endliche Automaten durch Prozesse, Funktionen und Messaging statt State-Pattern
Idle
Ringing Dial
Connected off_hook
on_hook
incoming off_hook
idle() -> receive {Number, incoming} -> start_ringing(), ringing(Number); off_hook -> start_tone(), dial() end. ringing(Number) -> receive {Number, off_hook} -> stop_ringing(), connected(Number); {Number, other_on_hook} -> stop_ringing(), idle() end.
other_ on_hook
Cesarini/Thompson: Erlang Programming 2009
© Zühlke 2011
Lazy Evaluation und unendliche Datenstrukturen
Lazy Evaluation:
(Teil-)Ausdrücke werden nur ausgewertet, wenn sie benötigt werden
head (x:xs) = x
Mit Lazy Evaluation gilt:
head [42.0, 1.0/0] == 42.0
Essentiell, um eigene Kontrollstrukturen zu definieren
unless cond x y = if !cond then x else y
Ideal für DSLs
© Zühlke 2011
Lazy Evaluation und unendliche Datenstrukturen
Mit Lazy Evaluation werden (potentiell) unendliche Datenstrukturen möglich
nats = [0 ..] take 5 nats == [0, 1, 2, 3, 4]
Wurzel-Berechnung nach Newton-Raphson:
sqrtSequence n = iterate (next n) n where next n x = (x + n/x)/2.0
sqrtSequence 2
>> [2.0, 1.5, 1.4166666666666665, 1.4142156862745097, 1.4142135623746899, 1.414213562373095, 1.414213562373095, 1.414213562373095, 1.414213562373095, …
iterate f n = [n,f(n),f2(n),f3(n), …]
http
://w
ww
.flic
kr.c
om/p
hoto
s/ro
bbie
73/
© Zühlke 2011
Pipes and Filters
Die Mächtigkeit der Unix-Shell kommt durch Pipes&Filters Konstruktionen cat *.txt | tr –sc A-Za-z '\n' | tr a-z A-Z | sort | uniq –c | sort –nr | head
Allgemein
prg1 –p1 <arg | prg2 –p2 | prg3 –p3 | prg4 –p4
Dies geht auch mit lazy Lists und Funktionskomposition
fct4 p4 . fct3 p3 . fct2 p2 . fct1 p1 $ arg
Idiomatisch in Haskell
Partial Application
Listen als Transfer-Container
Funktions- komposition
enspricht Pipe
Funktions- applikation enspricht <
Map/Reduce
Berechnung der (unabhängigen)
Zwischenergebnisse
Zusammenfassung
zum Endergebnis
Inspiration für s Map-Reduce-Framework (C++)
x1
x2
.
.
.
xn
f(x1)
f(x2)
.
.
.
f(xn)
map f reduce y = f(x1) … f(xn)
© Zühlke 2011
Was es sonst noch gibt
Eine Reihe weiterer Themen müssen wir auslassen
• Memoization
• Kombinatoren
• Monaden
• Macros
• Typeful Programming
• Continuations
• Co-Algebraische Konstruktionen
• …
Fazit
© Zühlke 2011
Funktionale Programmierung
Andersartiger Programmierstil
• Neue Abstraktionen und Kombinationsmöglichkeiten
• Andere Zerlegung von Problemen
• Andere Denkweisen und Idiome
Einfachere Strukturen machen das Leben leichter
• Keine (kaum) Seiteneffekte
• Pure Functions
• Testen und Parallelität werden sehr viel einfacher
© Zühlke 2011
Auswirkungen auf Architektur
Vieles bleibt gleich
• Architekturtreiber sind weiterhin die Qualitätsattribute
• Patterns werden zur Kommunikation für die Entwickler benötigt
Kreativität und Augenmaß bleiben zwei wichtige Eigenschaften der Architekten
• Gutes Design
• Klare Verantwortlichkeiten