-
Notifications
You must be signed in to change notification settings - Fork 7
/
Copy pathprogrammierparadigmen.tex
1332 lines (1147 loc) · 65.1 KB
/
programmierparadigmen.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\chapter{Programmierparadigmen}
Zusammenfassung der Vorlesung "`Programmierparadigmen"' aus dem Wintersemester 2014.\footnote{\url{https://pp.info.uni-karlsruhe.de/lehre/WS201415/paradigmen/}}
\section{Funktionale Programmierung (S16)}
\subsection{Einführung: Funktionale Programmierung in Haskell}
\begin{itemize}
\item Funktionale Programme sind kompakt, frei von Seiteneffekten, unabhängig von der Anweisungsreihenfolge
\item Der Begriff \textit{Funktion} in Sprachen wie Haskell entspricht der mathematischen Sicht: Ausgaben hängen lediglich von Eingaben ab \(\rightarrow\) Auswertungen haben keinen Effekt auf Daten des Programms.
\item Haskellprogramme sind Folgen von Funktionsdefinitionen
\end{itemize}
\subsection{Rekursion (S27)}
\begin{itemize}
\item Auswertung: Zwischenausdrücke können mit Eingabegröße wachsen
\item Speicherverbrauch in \(\mathcal{O}(n)\) bei \(\mathcal{O}(n)\) Aufrufen
\item \textbf{Akkumulation}
\begin{itemize}
\item Übergebe Zwischenergebnisse in Hilfsparameter \texttt{acc}
\item Speicherverbrauch in \(\mathcal{O}(1)\) bei \(\mathcal{O}(n)\) Aufrufen
\end{itemize}
\end{itemize}
\subsubsection{Endrekursion (S30)}
\begin{itemize}
\item Linearität: Eine Funktion heißt \textit{linear rekursiv}, wenn in jedem Definitionszweig nur ein rekursiver Aufruf vorkommt.
\item Endrekursion: Eine linear rekursive Funktion heißt \textit{endrekursiv}, wenn in jedem Zweig der rekursive Aufruf nicht in andere Aufrufe eingebettet ist.
\end{itemize}
\subsection{Listen (S34)}
\begin{itemize}
\item Eine Liste \texttt{(x:xs)} besteht immer aus Listenkopf \texttt{x} und Listenrest \texttt{xs}
\end{itemize}
\subsubsection{Pattern Matching (S37)}
\begin{itemize}
\item Mehrere Gleichungen zur Definition einer Funktion
\item Jede Gleichung gilt für Argumente mit speziellem Strukturmuster
\item Überlappende Muster: Erste Gleichung wird angewandt
\end{itemize}
\subsection{Funktionen höherer Ordnung (S44)}
\subsubsection{Lambda-Notation (S45)}
\begin{itemize}
\item Anonyme Funktionen und Funktionen höherer Ordnung möglich
\item Beispiel: \(g(x,y)=x-\frac{y}{2} \longrightarrow\) \texttt{g = \textbackslash x y -> x - 2/y}
\end{itemize}
\subsubsection{Definition: Funktion höherer Ordnung (S47)}
Funktionen, die andere Funktionen als Parameter erhalten oder Funktionen als Rückgabewerte liefern, heißen Funktionen höherer Ordnung.
\subsubsection{Currying (S50)}
\begin{itemize}
\item Ersetzung einer mehrstelligen Funktion durch Schachtelung einstelliger Funktionen.
\item Jede Funktion erhält, wie oben erwähnt, nur ein Argument. Werden scheinbar mehrere Argumente definiert, so steckt immer Currying dahinter.
\item Unterversorgung: Anwendung mehrstelliger Funktionen auf zu wenig Parameter
\end{itemize}
\textbf{Beispiel\footnote{\url{https://de.wikipedia.org/wiki/Currying\#Haskell}}}
\begin{lstlisting}[frame=single,numbers=left,mathescape,language=Haskell]
addiere x y = x + y
addiere 1 3 -- ist aequivalent zu (addiere 1) 3
addiereZu2 = addiere 2
addiereZu2 1 -- 3
\end{lstlisting}
\subsubsection{Namensbindung (S54)}
\begin{itemize}
\item Bindungsstrukte legen Bedeutung und Geltungsbereiche von Variablen fest
\item Verdeckung: Innere Bindungen verdecken äußere
\item \textbf{Bindung}
\begin{itemize}
\item \texttt{f x = x*x}: Bindung von \texttt{x} im Rumpf von \texttt{f}, globale Bindung von \texttt{f}
\item \texttt{\textbackslash x -> x*x}: Bindung von \texttt{x} innerhalb des \(\lambda\)-Ausdrucks
\end{itemize}
\end{itemize}
\subsubsection{Lokale Bindung (S57)}
\begin{itemize}
\item Anwendung: Lokale Hilfsfunktionen
\item \texttt{let} bindet stärker als \texttt{where}
\end{itemize}
\textbf{Beispiele}
\begin{lstlisting}[frame=single,numbers=left,mathescape,language=Haskell]
energy m = let c = 299792458
in m * c * c
energy m = m * c * c
where c = 299792458
\end{lstlisting}
\subsection{Kombinatoren (S64)}
\subsubsection{Folds (S65)}
\begin{itemize}
\item Anwendung einer Operation und eines Initialwertes auf eine Liste
\item \textbf{Beispiel Summenberechnung}
\begin{itemize}
\item \texttt{sum = (+) 0}
\item Berechnung mittels \texttt{foldr}: \texttt{(1 + (2 + (3 + (4 + 0))))} (rechts-geklammert)
\item Berechnung mittels \texttt{foldl}: \texttt{((((1 + 0) + 2) + 3) + 4)} (links-geklammert)
\end{itemize}
\item Anwendung: Komplexe Funktionen als Kombination einfacher Funktionen
\end{itemize}
\subsubsection{Kombination von Listen (S67)}
\begin{itemize}
\item Zusammenfügen von Listen per Reißverschluss: \texttt{zip = zipWith (,)}
\item \texttt{zipWith} definiert eine Zusätzliche Operation
\item Bricht ab, wenn eine der Listen keine weiteren Elemente enthält
\end{itemize}
\subsubsection{List Comprehensions (S67)}
\begin{itemize}
\item Automatisiertes Erzeugen von Listen, basierend auf bereits existierenden Listen
\item Inspiriert durch die mathematische Mengenschreibweise: \texttt{s = {[} 2 * x {|} x <- {[}0..{]}, x\textasciicircum 2 > 3 {]} } \footnote{\url{https://en.wikipedia.org/wiki/List_comprehension\#Haskell}}
\item Multidimensionale Liste: \texttt{s = {[} 2*x*y {|} x <- {[}0..{]}, x\textasciicircum2 > 3, y <- {[}1,3..x{]}, y\textasciicircum2 < 100-x\textasciicircum2 {]}}
\item Bei mehrdimensionaler Eingabe: Nur die erste Liste gegen Unendlich laufen lassen (siehe Klausur WS2014, Aufgabe 1)
\end{itemize}
\subsection{Lazy Evaluation (S70)}
\subsubsection{Auswertung (S73)}
\begin{itemize}
\item Strukturierte Daten: Nur auswerten, falls wirklich benötigt wird
\item Duplizierte Argumente: Auswertung maximal einmal (\textit{sharing})
\item Pattern-Matching: So weit wie nötig, bis passendes Muster gematched
\item Boolsche Operatoren: Auswertung bis zum ersten \textit{false} (\textit{short-circuit-Auswertung})
\item \textbf{Nachteile}
\begin{itemize}
\item Erschwerte Fehlersuche
\item Fehler, die beim Testen nicht beachten wurden, tauchen eventuell später im Betrieb auf
\end{itemize}
\end{itemize}
\subsection{Typen (S82)}
\begin{itemize}
\item Haskell ist statisch typisiert
\item Jeder gültige Ausdruck hat immer einen Typ und wertet immer zu gültigen Werten dieses Typs aus
\item Schreibweise: \texttt{e :: t} falls Ausdruck \texttt{e} und Typ \texttt{t}
\item Untypisierbare Ausdrücke erzeugen Übersetzerfehler
\item Haskell erkennt den korrekten Typ (fast immer) zuverlässig, optional manuelle Deklaration möglich
\end{itemize}
\subsubsection{Polymorphe Typen (S86)}
\begin{itemize}
\item Der Listen-Typ sind polymorph, die Typvariable \texttt{{[}t{]}} steht auch für Nicht-Basistypen
\item Typvariablen parametrisieren polymorphe Typen
\item Typkonstruktoren wie \texttt{{[} {]}} erzeugen neue Typen aus bestehenden
\item Funktionstypen sind ebenfalls polymorph
\end{itemize}
\subsubsection{Beispiele}
\begin{itemize}
\item Typen mehrstelliger Funktionen: \texttt{f x y = x * y, f :: Integer -> Integer -> Integer}
\item Typen eingebauter Operatoren: \texttt{(<=) :: Integer -> Integer -> Bool}
\item Tupel: \texttt{(3, True) :: (Integer, Bool); (not, 7) :: (Bool -> Bool, Integer)}
\end{itemize}
\subsubsection{Typinferenz (S91)}
Errechnen der Typen durch den Compiler, dadurch entstehen kompakte Programme, die trotzdem typsicher sind. Manuelle Deklaration ist dennoch möglich.
\subsubsection{Typsynonyme (S93)}
Ableiten neuer Typen aus vorhandenen. Z.B. \texttt{type String = {[}char{]}} (kann die Lesbarkeit erhöhen). Es werden keine explizit neuen Typen erzeugt.
\subsubsection{Typen bei der Fehlersuche (S94)}
\begin{itemize}
\item Typendeklarationen können beim Lokalisieren von Programmfehlern helfen
\item Beabsichtigten Typ der Funktion deklarieren
\item \textbf{Beispiel}
\begin{itemize}
\item \texttt{isDigit :: Char -> Bool}\\\texttt{isDigit c = isIn c "0123456789"}
\item \texttt{*Main> isDigit '3'} würde zu einem Typfehler führen
\end{itemize}
\end{itemize}
\subsubsection{Mengen (S95)}
\begin{itemize}
\item Mengen bestehen aus dem Typ \texttt{Set = ...} sowie Funktionen zum Iterieren, Einfügen, Löschen, Vergleichen, usw.
\item Einfachste Implementierung als Listen: \texttt{type Set t = {[} {]}}
\end{itemize}
\subsection{Algebraische und rekursive Datentypen (S102)}
\subsubsection{Produkttypen}
Typen mit mehreren Komponenten.
\subsubsection{Nachteile von Tupeln (S103)}
\begin{itemize}
\item Typsynonyme: Typen mit mehreren Komponenten. Beispiel: Personen mit Name und Alter \texttt{type Person = (String, Int)}
\item Nachteil: Bedeutung von Werten nicht explizit; ungewollte Verwendung gleicher Tupel (z.B. \texttt{(String, Int)}) mit verschiedener Bedeutung
\end{itemize}
\subsubsection{Algebraische Datentypen (S104)}
\begin{itemize}
\item Verwendung des Schlüsselwortes \texttt{data} statt \texttt{type} zur definition \textit{neuer} Typen
\item Einfachste Anwendung: Aufzählungstypen. Funktionsimplementierung über Pattern Matching\\\\
\begin{minipage}{\linewidth}
\begin{lstlisting}[frame=single,numbers=left,mathescape,language=Haskell]
data Temp = Cold | Hot
data Season = Spring | Summer | Autumn | Winter
weather :: Season -> Temp
weather spring = Cold
weather summer = Hot
weather autumn = Cold
weather winter = Cold
\end{lstlisting}
\end{minipage}
\item Alternativ-Typen mit mehreren Konstruktoren\\\\
\begin{minipage}{\linewidth}
\begin{lstlisting}[frame=single,numbers=left,mathescape,language=Haskell]
data Shape = Circle Double | Rectangle Double Double | Square Double
-- Konstruktor
dinA4 = Rectangle 210.0 297.0
-- Flaechenberechnung
area (Circle r) = pi*r*r
area (Rectangle a b) = a*b
area (Square a) = a*a
\end{lstlisting}
\end{minipage}
\item Optionale Werte
\begin{itemize}
\item Anwendung: Funktionen, die bei bestimmten Eingaben fehlschlagen können (Vgl. \texttt{null} in Java)
\item Auswertung/Abfangen über Pattern-Matching
\end{itemize}
\begin{minipage}{\linewidth}
\begin{lstlisting}[frame=single,numbers=left,mathescape,language=Haskell]
data Maybe t = Nothing | Just t
\end{lstlisting}
\end{minipage}
\end{itemize}
\subsection{Anwendung algebraischer Datentypen (S108)}
\begin{itemize}
\item \textbf{Algebraischer Datenstrukturen ermöglichen}
\begin{itemize}
\item Implementierung von Datenstrukturen
\item Modellierung problemspezifischer Daten
\end{itemize}
\item \textbf{Einsatz von Pattern-Matching}
\begin{itemize}
\item Erleichtert Umsetzung komplexer Algorithmen
\item Besonders für baumartige Strukturen
\end{itemize}
\item \textbf{Anwendungsbeispiele}
\begin{itemize}
\item Datenstrukturen: Maps, Bäume, Rot-Schwarz-Bäume \\\\
\begin{minipage}{\linewidth}
\begin{lstlisting}[frame=single,numbers=left,mathescape,language=Haskell]
data Tree = Leaf | Node (Tree t) t (Tree t)
someTree = Node (Node Leaf 1 Leaf) 3 Leaf
\end{lstlisting}
\end{minipage}
\item Polymorphe Datentypen
\item Fehlerbehandlung
\item Termersetzungssysteme
\end{itemize}
\end{itemize}
\subsection{Typklassen (S124)}
Motivation am Beispiel \textit{Quicksort}: Algorithmus prinzipiell für alle (sortierbaren) Element-Typen umsetzbar.
\subsubsection{Implementierungsansätze (S126)}
\begin{enumerate}
\item Eigene Funktion je Datentype: Softwaretechnisch katastrophal\\\\
\begin{minipage}{\linewidth}
\begin{lstlisting}[frame=single,numbers=left,mathescape,language=Haskell]
qsortI :: [Integer] -> [Integer]
qsortD :: [Double] -> [Double]
\end{lstlisting}
\end{minipage}
\item Umsetzung als polymorphe Funktion: Funktioniert nicht, da nicht alle Typen \texttt{t} sortierbar sind.\\\\
\begin{minipage}{\linewidth}
\begin{lstlisting}[frame=single,numbers=left,mathescape,language=Haskell]
qsort :: [t] -> [t]
\end{lstlisting}
\end{minipage}
\item Lösung: Polymorphe Funktion mit Typeinschränkung\\\\
\begin{minipage}{\linewidth}
\begin{lstlisting}[frame=single,numbers=left,mathescape,language=Haskell]
qsort :: Ord t => [t] -> [t]
\end{lstlisting}
\end{minipage}
\end{enumerate}
\subsubsection{Standard-Typklassen (S127)}
\begin{itemize}
\item Fassen Typen anhand auf ihnen definierter Operationen zusammen
\item Ähneln grob Java-Interfaces
\item \texttt{Beispiele}
\begin{itemize}
\item Äquivalenzrelation: \texttt{Eq t} (vergleichbar)
\item Geordnete Typen: \texttt{Ord t} (sortierbar)
\item Numerische Typen: \texttt{Num t} (berechenbar)
\item Anzeigbare Typen: \texttt{Show t}
\item Aufzählungstypen: \texttt{Enum t} (beispielsweise Vorgänger oder Nachfolger berechenbar)
\end{itemize}
\end{itemize}
\subsubsection{Typklassendefinition (S128)}
\begin{minipage}{\linewidth}
\begin{lstlisting}[frame=single,numbers=left,mathescape,language=Haskell]
-- Typklassendefinition: Eq t
class (Eq t) where
(==) :: t -> t -> Bool
(/=) :: t -> t -> Bool
-- Typklasseninstanziierung: Gleichheit von Bool
instance (Eq Bool) where
True == True = True
False == False = True
False == True = False
True == False = False
-- oder alternativ
instance (Eq Bool) where
True /= True = False
False /= False = False
False /= True = True
True /= False = True
\end{lstlisting}
\end{minipage}
\subsubsection{Automatische Instanziierung (S129)}
\begin{minipage}{\linewidth}
\begin{lstlisting}[frame=single,numbers=left,mathescape,language=Haskell]
data Shape = Circle Double | Rectangle Double Double | Square Double deriving Eq
-- Verschiedene Konstruktoren ergibt verschiedene Werte
Circel 1 == Square 1 $\rightarrow$ False
Rectangle 1 1 == Square 1 $\rightarrow$ False
-- Gleicher Konstruktor, verschiedene Werte ergibt verschiedene Werte
Circle 1 == Circle 3 $\rightarrow$ False
-- Gleicher Konstruktor, gleiche Werte ergibt gleiche Werte
Square 2 == Square 2 $\rightarrow$ True
\end{lstlisting}
\end{minipage}
\subsubsection{Vererbung von Typklassen (S130)}
Typklassen sind vererbbar. Beispielsweise ist jede Instanz von \texttt{Ord} auch eine Instanz von \texttt{Eq}.
\section{Theoretische Grundlagen (S153)}
Kalküle sind minimalistische Programmiersprachen zur Beschreibung von Berechnungen.
\subsection{Der untypisierte $\lambda$-Kalkül (S159)}
\begin{itemize}
\item Turing-mächtiges Modell funktionaler Programme zur Beschreibung sequentieller imperativer Konstrukte
\item Linksassoziative Funktionsanwendung
\item \(\lambda\)-Term: Ein Term der Form \texttt{(\(\lambda\)x.\(t_1\))\(t_2\)}
\item \textbf{\(\alpha\)-Äquivalenz}
\begin{itemize}
\item \(t_1\) und \(t_2\) heißen \(\alpha\)-äquivalent, wenn \(t_1\) in \(t_2\) durch konsistente Umbenennung der \(\lambda\)-gebundenen Variablen überführt werden kann
\item Funktionsbezeichnungen dürfen nicht geändert werden
\item Beispiel: \texttt{\(\lambda\)x. (\(\lambda\)z. f(\(\lambda\)y. z y) x) = \(\lambda\)y. (\(\lambda\)x. f(\(\lambda\)z. x z) y)}
\end{itemize}
\item \textbf{\(\eta\)-Äquivalenz (S160)}
\begin{itemize}
\item Zwei Funktionen genau dann gleich sind, wenn sie für alle Argumente dasselbe Resultat liefern\footnote{\url{https://de.wikipedia.org/wiki/Lambda-Kalkül\#.CE.B7-Konversion}}
\item Terme \texttt{\(\lambda\)x. f x} und \texttt{f} heißen \(\eta\)-äquivalent, falls \texttt{x} eine nicht-freie Variable von \texttt{f} ist
\end{itemize}
\end{itemize}
\subsubsection{$\beta$-Reduktion (S161)}
\begin{itemize}
\item Formalisiert das Konzept der Funktionsanwendung
\item Anwendung ausschließlich von links nach rechts
\item Eine \(\beta\)-Reduktion entspricht der Ausführung der Funktionsanwendung auf einem Redex: \texttt{(\(\lambda\)x.\(t_1\))\(t_2 \Rightarrow\) \(t_1\){[} x \(\mapsto t_2\) {]}}
\item Volle \(\beta\)-Reduktion: Jeder Redex kann reduziert werden
\item \textbf{Beispiele}
\begin{itemize}
\item \texttt{(\(\lambda\)x.x)y \(\Rightarrow\) x{[} x \(\mapsto\) y {]} = y}
\item \texttt{(\(\lambda\)x.x (\(\lambda\)x.x))(y z) \(\Rightarrow\) (x (\(\lambda\)x.x)){[} x \(\mapsto\) y z {]} = (y z)(\(\lambda\)x.x)}
\end{itemize}
\item \textbf{Braucht man primitive Operationen?}
\begin{itemize}
\item Nein, nicht unbedingt. Beispiel: \texttt{let}
\item \texttt{let x = \(t_1\) in \(t_2\)} wird zu \texttt{(\(\lambda\)x.\(t_2\)) \(t_1\)}
\item \texttt{let x = g y in f x = (\(\lambda\)x.f x)(g y) \(\Rightarrow\) f(g y)}
\end{itemize}
\end{itemize}
\subsubsection{Kodierung natürlicher Zahlen (S172)}
\begin{itemize}
\item Einbettung von Daten und Operationen in den \(\lambda\)-Kalkül
\item Eine (natürliche) Zahl drückt aus, wie oft die Funktion \texttt{s} angewendet wird
\item \textbf{Church-Zahlen}
\begin{itemize}
\item \texttt{\(c_0\) = \(\lambda\)s. \(\lambda\)z. z}
\item \texttt{\(c_1\) = \(\lambda\)s. \(\lambda\)z. s z}
\item \texttt{\(c_2\) = \(\lambda\)s. \(\lambda\)z. s (s z)}
\item \texttt{\(c_3\) = \(\lambda\)s. \(\lambda\)z. s (s (s z))} \\ \(\vdots\)
\item \texttt{\(c_n\) = \(\lambda\)s. \(\lambda\)z. \(s^n\) z}
\end{itemize}
\end{itemize}
\subsubsection{Kodierung boolscher Werte (S174)}
\begin{itemize}
\item \texttt{True} und \texttt{False} wird zu \texttt{\(c_{true}\) = \(\lambda\)t. \(\lambda\)f. t} und \texttt{\(c_{false}\) = \(\lambda\)t. \(\lambda\)f. f}
\item \texttt{True} gibt den ersten Wert zurück, \texttt{false} den zweiten \(\rightarrow\) ermöglicht Entscheidungen
\item \texttt{if \_ then \_ else \_} wird zu \texttt{\(\lambda\)a. a}. Beispielsweise wird aus \texttt{if True then x else y}: \texttt{(\(\lambda\)a. a) (\(\lambda\)t. \(\lambda\)f. t) x y \(\Rightarrow\) (\(\lambda\)t. \(\lambda\)f. t) x y \(\Rightarrow\) (\(\lambda\)f. x) y}
\item \texttt{\(b_1\) \&\& \(b_2\)} wird zu \texttt{if \(b_1\) then \(b_2\) else False}
\item \texttt{True \&\& True} ergibt: \texttt{(\(\lambda\)a. a) \(c_{true}\) \(c_{true}\) (\(\lambda\)t. \(\lambda\)f. t)}
\end{itemize}
\subsubsection{Divergenz (S175)}
\begin{itemize}
\item Terme, die nicht zu einer Normalform auswerten, divergieren. Diese modellieren unendliche Ausführungen
\item Beispiel: \texttt{\(\lambda\)x. x x} wendet sein Argument auf das Argument selbst an und reproduziert sich selbst. \texttt{\(\omega\) = (\(\lambda\)x. x x)(\(\lambda\)x. x x) \(\Rightarrow\) (\(\lambda\)x. x x)(\(\lambda\)x. x x)}
\end{itemize}
\subsubsection{Rekursionsoperator (S177)} % TODO
\begin{itemize}
\item \texttt{\(\hat{f}\)} reproduziert sich ein jedem Schritt zusätzlich
\item \texttt{Y \(\hat{f}\) = (\(\lambda\)f. (\(\lambda\)x. f (x x))(\(\lambda\)x. f (x x))) \(\hat{f}\)}
\end{itemize}
\subsubsection{Auswertungsstrategien (S182)}
\begin{itemize}
\item \textbf{Auswertungsstrategien}
\begin{itemize}
\item Normalenreihenfolge: Immer der linkeste, äußerste Redex wird reduziert (S170)
\item \textbf{Call-by-Name}
\begin{itemize}
\item Reduziere linkesten, äußersten Redex. Aber nur, falls nicht von einem \(\lambda\) umgeben
\item Ituitiv: Reduziere Argumente erst, wenn benötigt
\item Standardauswertungsstrategie für Funktionen/Konstruktoren
\end{itemize}
\item \textbf{Call-by-Value}
\begin{itemize}
\item Reduziere linkesten Redex, der nicht von einem \(\lambda\) umgeben ist und dessen Argument kein Wert ist
\item Intuitiv: Argumente vor Funktionsaufruf auswerten
\item Auswertungsstrategie vieler Sprachen: Java, C, Scheme, ML, etc.
\end{itemize}
\end{itemize}
\end{itemize}
\subsection{Typsysteme (S192)}
\begin{itemize}
\item \textit{Typen} legen die möglichen Werte von Variablen, Operationen und Operanden fest. Beispiel: Integer, Float, String
\item Statisch typisierte Sprachen: Jede Variable/jeder Ausdruck hat einen vom Compiler bestimmbaren Typ. Beispiel: Java, Haskell, C++
\item Dynamisch typisierte Sprachen: Typ von Variablen kann sich zur Laufzeit ändern. Beispiele: JavaScript, Python, PHP
\item \textbf{Vorteile von Typsystemen}
\begin{itemize}
\item Code ist verständlicher
\item Compiler kann effizienteren Code erzeugen
\item Typsicherheit: Abstürze wegen falscher Typen zur Laufzeit unmöglich
\end{itemize}
\item Typklassen definieren Funktionen, die für jede Instanz der Typklasse aufgerufen werden können
\item Man kann eine Instanz für jeden Typ erstellen, indem man die Funktionen der Typklasse für den jeweiligen Typ definiert
\item Beispiel: Vergleichsoperator (\texttt{==})
\end{itemize}
\subsubsection{Typherleitung (S196)} % TODO
\begin{itemize}
\item Nachweis von Herleitbarkeit als Herleitungsbaum
\item Die Struktur des Herleitungsbaums wird durch den \(\lambda\)-Term bestimmt
\item Zu jedem Subterm genau eine passende Regel: \texttt{App, Var, Abs oder Const}
\item \texttt{t} ist typisierbar im Kontext \(\Gamma\), falls \(\tau\) mit \(\Gamma\vdash t_2~:~\tau_2\) exisitiert
\item Beispiel mit Ableitungsbaum auf Folie 196
\item \textbf{Beispiele zum direkten Ablesen}
\begin{itemize}
\item \texttt{\(\lambda\)f. \(\lambda\)x. f x \\ x: \(\alpha\) \\ f x: \(\beta\) \(\Rightarrow\) f: \(\alpha\) \(\rightarrow\) \(\beta\) \\ \(\lambda\)x. f x: \(\alpha\) \(\rightarrow\) \(\beta\) \\ \(\lambda\)f. \(\lambda\)x. f x: (\(\alpha\) \(\rightarrow\) \(\beta\)) \(\rightarrow\) \(\alpha\) \(\rightarrow\) \(\beta\)}
\item \texttt{\(\lambda\)o. \(\lambda\)f. \(\lambda\)g. \(\lambda\)x. o (f g) (g x) \\ x: \(\alpha\) \\ g x: \(\beta\) \(\Rightarrow\) g: \(\alpha\) \(\rightarrow\) \(\beta\) \\ f x: \(\gamma\) \(\Rightarrow\) f: \(\alpha\) \(\rightarrow\) \(\gamma\) \\ o (f x) (g x): \(\delta\) \(\Rightarrow\) \(\gamma\) \(\rightarrow\) \(\beta\) \(\rightarrow\) \(\delta\) \\ \(\lambda\)o. \(\lambda\)f. \(\lambda\)g. \(\lambda\)x. o (f g) (g x): (\(\gamma\) \(\rightarrow\) \(\beta\) \(\rightarrow\) \(\delta\)) \(\rightarrow\) (\(\alpha\) \(\rightarrow\) \(\gamma\)) \(\rightarrow\) (\(\alpha\) \(\rightarrow\) \(\beta\)) \(\rightarrow\) \(\alpha\) \(\rightarrow\) \(\delta\) \(\Rightarrow\) (\(\alpha\) \(\rightarrow\) \(\beta\) \(\rightarrow\) \(\gamma\)) \(\rightarrow\) (\(\delta\) \(\rightarrow\) \(\alpha\)) \(\rightarrow\) (\(\delta\) \(\rightarrow\) \(\beta\)) \(\rightarrow\) \(\delta\) \(\rightarrow\) \(\gamma\)}
\item \textbf{Typschema einer \texttt{let}-gebundenen Variable \texttt{f}}
\begin{itemize}
\item \texttt{G = \(\lambda\)y. let f = \(\lambda\)x. x 0 in f (\(\lambda\)z. y)}
\item Lösung: Typschema für \texttt{f} in \texttt{G: f: \(\forall\)\(\alpha\). (int \(\rightarrow\) \(\alpha\)) \(\rightarrow\) \(\alpha\)}
\end{itemize}
\end{itemize}
\end{itemize}
\subsubsection{Untypisierbare \(\lambda\)-Terme (S197)}
\begin{itemize}
\item Nicht alle sicheren Programme sind typisierbar \(\rightarrow\) Typsystem nicht vollständig bzgl. \(\beta\)-Reduktion
\item Beispiel: \texttt{(\(\lambda\)x. x + 42) true} ist nicht typisierbar
\item Die Korrektheit des Typsystems ist per Induktion über die Typsystemregeln beweisbar (S198)
\end{itemize}
\subsection{Polymorphie (S199)}
\begin{itemize}
\item Polymorphe Funktionen: Verhalten hängt nicht vom konkreten Typ \(\tau\) der Elemente ab und haben unendlich viele Typen
\item Beispiel: Operationen auf Containern (Zusammenfügen von Listen)
\end{itemize}
\subsubsection{\texttt{let}-Polymorphismus (S201)}
\begin{itemize}
\item Beispielprogramm P: \texttt{let f = \(\lambda\)x. 2 in f (f true)}
\item \texttt{f} ist eine polymorphe Hilfsfunktion: Anwendung erst auf \texttt{true}, dann auf \texttt{2}
\item Typisierung so nicht möglich. Daher: \texttt{let x = \(t_1\) in \(t_2\)} als neues Konstrukt im \(\lambda\)-Kalkül. Neue Typregeln mit \textit{Typschemata}
\item \textbf{Typschemata (S202)}
\begin{itemize}
\item Ein Typ der Gestalt \(\forall\alpha_1.\forall\alpha_2.~...~\forall\alpha_n.~\tau\) heißt Typschema
\item Es bindet freie Typvariablen \(\alpha_1,...,\alpha_n\) in \(\tau\)
\item Beispiel: \(\forall\alpha.~\alpha\rightarrow\alpha\) steht für unendlich viele Typen
\item Ausführliches Ableitungsbeispiel auf Folie S205 % TODO
\end{itemize}
\item Flexibel einsetzbar, trotzdem bleibt Typsicherheit garantiert
\end{itemize}
\section{Logische Programmierung (S210)}
Prolog-Programme bestehen aus einer Datenbasis, deren Einträge sich Fakten und Regeln nennen. Der Benutzer formuliert Anfragen an diese Datenbasis. Der Prolog-Interpreter benutzt die Fakten und Regeln, um systematisch eine Antwort zu finden. Ein positives Resultat bedeutet, dass die Anfrage logisch ableitbar ist. Ein negatives Resultat bedeutet nur, dass aufgrund der Datenbasis keine Ableitung gefunden werden kann.\footnote{\url{https://de.wikipedia.org/wiki/Prolog_(Programmiersprache)\#Grundprinzip}}
\subsection{Einführung in Prolog (S211)}
\begin{itemize}
\item Situationsbeschreibung sowie Definition von Objekten und Beziehungen zwischen Objekten. Prolog-Programme definieren eine Liste von Regeln und Fakten
\item Elemente: \textit{Atome} (z.B. \texttt{hans, inge, fritz, fisch}), \textit{Zahlen (z.B. \texttt{3, 4.5})}, \textit{Variablen} (z.B. \texttt{X, Y, \_X, X1, Fisch}) oder \textit{Termlisten (z.B. \texttt{3, 4.5, X, fritz})}
\end{itemize}
\subsubsection{Abfragen (S217)}
\begin{itemize}
\item Alle Fakten werden zur Laufzeit in einer Datenbank gehalten
\item Abfragen per \texttt{?}: z.B. \texttt{?liebt(fritz,fisch)}
\item \textbf{Mehrfachlösungen}
\begin{itemize}
\item Durchsuche Datenbank von vorne nach hinten
\item Versuche jeweils, Abfrageparameter mit Datenbankfaktor zu unifizieren
\item Wenn Variablen übergeben werden, dann werden diese gefüllt. Es wird immer die erste Lösung zurückgegeben
\item Bei Bedarf kann nach weiteren Lösungen gesucht werden
\end{itemize}
\item \textbf{Konjunktion von Abfragen}
\begin{itemize}
\item Konjunktion von Teilzielen getrennt durch Komma, entspricht logischem \(\wedge\)
\item Erfülle Teilziele von links nach rechts und nehme jeweils erstes Ergebnis
\item Mehrere Ergebnisse: Fahre mit dem ersten Ergebnis bis zum Ende fort, prüfe danach weitere Ergebnisse
\item Nach Erfüllung eines Teilziels: Nächstes Teilziel erbt Instanziierung
\end{itemize}
\end{itemize}
\subsubsection{Regeln (S222)}
\begin{itemize}
\item Aufbau: Regelkopf (1 Term) und Regelrumpf (1+ Terme): \texttt{term :- termlist .}
\item \texttt{:-} liest sich als \textit{wenn}, Kommata als \textit{und}
\item \textbf{Beispiele}
\begin{itemize}
\item "`Wenn Inge X liebt und wenn X Fisch liebt, dann liebt Hugo X"':\newline\texttt{liebt(hugo,X) :- liebt(inge,X),liebt(X,fisch)}
\item "`Wenn es jemanden gibt, der Fisch mag, dann liebt Emil Erna"':\newline\texttt{liebt(emil,erna) :- liebt(X,fisch)}
\end{itemize}
\end{itemize}
\subsubsection{Logische Programmierung ist anders (S225)}
\begin{itemize}
\item Keine herkömmlichen Variablen
\item Prädikate liefern außer ihrer Erfüllbarkeit keinen Ergebniswert
\item Aber Unifikation und Backtracking eingebaut
\item Sehr gut geeignet für Such- und Constraintprobleme, weniger für Berechnungen
\end{itemize}
\subsection{Backtracking (S226)}
\begin{itemize}
\item Visualisierung durch einen Ausführungsbaum
\item Jedes Teilziel wird als Box mit vier Ein- bzw. Ausgängen dargestellt
\end{itemize}
\subsubsection{Der Algorithmus informell (S228)}
\begin{enumerate}
\item Anlegen und erstmaliges Betreten der Box durch den \texttt{call}-Eingang beim ersten Aufruf des Teilziels
\item Falls keine passende Regel gefunden wird, wird die Box durch den \texttt{fail}-Ausgang verlassen und gelöscht
\item Für eine passende Regel werden Kind-Boxen für Teilziele im Regelrumpf angelegt. Die Box wird durch den \texttt{success}-Ausgang verlassen. Dieser verweist auf den \texttt{call}-Eingang der ersten Kindbox
\item Falls keine Kinder existieren (Fakt), verweist \texttt{success} auf den \texttt{call}-Eingang des nächsten Teilziels
\item Der \texttt{fail}-Ausgang verweist auf den \texttt{redo}-Eingang des vorherigen Teilziels
\item Wird eine Box durch den \texttt{redo}-Eingang betreten, werden mit Hilfe des Choice Points weitere anwendbare Regeln gesucht. Falls kein Choice Point existiert, wird die Box durch \texttt{fail}
\item Der \texttt{fail}-Ausgang der obersten/ersten Box erzeugt die Ausgabe \texttt{no}
\item Der \texttt{success}-Ausgang der rechtest-untersten/letzten Box gib Substitution aus. Falls der Benutzer eine alternative Lösungen anfordert, wird die Box durch \texttt{redo} wieder betreten
\end{enumerate}
\subsection{Arithmetik und Listen (S230)}
\subsubsection{Listen: \texttt{{[}X{|}Y{]}} (S231)}
\begin{itemize}
\item \texttt{X} ist das erste Element der Liste (\textit{head}), \texttt{Y} ist der Rest der Liste (\textit{tail}), \texttt{{[}{]}} bezeichnet die leere Liste
\item \texttt{Y} muss nicht instanziiert sein
\item Listen können von vorne aufgebaut werden (im Gegensatz zu Haskell)
\item \textbf{Listenfunktionen}
\begin{itemize}
\item \texttt{member (S232)}
\begin{itemize}
\item Berechnet, ob ein Element in der Liste vorkommt
\item \texttt{member(X, {[}X{|}R{]}).} \\ \texttt{member(X, {[}Y{|}R{]}) := member(X,R).}
\end{itemize}
\item \texttt{append (S232)}
\begin{itemize}
\item Fügt zwei Listen zusammen (Konkatenation)
\item Wenn die Konkatenation von \texttt{R} und \texttt{L} die Liste \texttt{T} ergibt, dann ergibt die Konkatenation von \texttt{{[}X{|}R{]}} und \texttt{L} die Liste \texttt{{[}X{|}T{]}}.
\item \texttt{append({[]}, L, L).} \\ \texttt{append({[}X{|}R{]}, L, {[}X{|}T{]}) :- append(R, L, T).}
\item Beispiel: \texttt{?append({[}1, 2, 3, 4{]}, {[}2, 3, 4, 5{]}, X).} ergibt \texttt{X = {[}1, 2, 3, 4, 2, 3, 4, 5{]}}
\end{itemize}
\item \texttt{rev (S234)}
\begin{itemize}
\item Naiver Ansatz: Eine nichtleere Liste wird invertiert, in dem man rekursiv den Listenrest invertiert und jeweils die Listenköpfe davor hängt
\item Ineffizient, da in jedem Schritt die neue Liste durchlaufen und kopiert werden muss, um ein neues Element anzuhängen
\item Alternativ: Nutze Akkumulator zum Zwischenspeichern des Ergebnisses
\end{itemize}
\item \texttt{Quicksort (S236)}
\item \texttt{permute (S237)}: Erzeugt alle möglichen Permutationen einer Liste
\end{itemize}
\end{itemize}
\subsubsection{Arithmetik (S238)}
\begin{itemize}
\item Reines Prolog kann alle berechenbaren Funktionen verarbeiten, Prädikate werden über Atome dargestellt. In der Praxis können Arithmetik/Datentypen trotzdem nützlich sein
\item Zuweisung per Teilziel: \texttt{is}
\item Unterschied zur normalen Resolution: Variablen im \textit{rechten} Term müssen instanziiert sein \(\rightarrow\) nur vorwärts anwendbar
\end{itemize}
\subsubsection{Funktionen (S239)}
\begin{itemize}
\item Funktionen in Prolog als Prädikate
\item Prädikate tragen außer der Erfüllbarkeit keinen Rückgabewert \(\rightarrow\) Rückgabewert als zusätzliche, uninstanziirte Variable
\item Formal ähnlich zum Pattern Matching
\end{itemize}
\subsubsection{Generate und Test (S241)}
Prolog ist besonders gut:
\begin{itemize}
\item Für systematisches Durchprobieren mittels mehrfach reerfüllbarer Prädikate
\item Erzeugen von Lösungskandidaten, welche danach getestet werden
\item Häufiges Entwurfsmuster in Prolog. Zur Vermeidung von kombinatorischen Explosionen: Generator möglichst intelligent machen
\item Beispiel: \texttt{nat(X) :- nat(Y), X is Y+1.}
\end{itemize}
\subsection{Der Cut (S243)}
\subsubsection{Determinismus (S244)}
Ein Prädikat heißt \textit{deterministisch}, wenn es stets auf höchstens eine Weise erfüllt werden kann; hat es möglicherweise mehrere Lösungen, so heißt es nichtdeterministisch.
In der nichtfunktionalen Welt kann Nichtdeterminismus nur behandelt werden, indem man von Lösungen zu Listen von Lösungen übergeht.
\subsubsection{Beschneiden des Ausführungsbaums}
\begin{itemize}
\item Die Lösungsfindung kann vorzeitig durch den Programmierer abgebrochen werden ("`Cut"')
\item Das Einfügen eines Cuts ("`\texttt{!}"') verhindert, dass im Fehlerfall, die Teilziele links davon nicht erneut aufgerufen werden
\item Beispiel auf Folie 246
\end{itemize}
\subsubsection{Blaue, grüne und rote Cuts (S248)}
\begin{itemize}
\item \textbf{Blauer Cut}
\begin{itemize}
\item Beeinflusst weder Programmlaufzeit noch -verhalten
\end{itemize}
\item \textbf{Grüner Cut (S249)}
\begin{itemize}
\item Beeinflusst Programmlaufzeit aber nicht -verhalten
\item Schnellere Ausführung und weniger Speicherbedarf
\item Beispiel: Einfügen in Funktionen, von denen man weiß, dass sie deterministisch sind
\end{itemize}
\item \textbf{Roter Cut (S250)}
\begin{itemize}
\item Beeinflusst das Programmverhalten
\item Werden verwendet, um Wächter zu ersetzen. Ist der erste Wächter erfolgreich, wird der zweite nie angewendet
\item Können zu erheblichem Effiziensgewinn führen, da sie u.U. sehr komplexe und teure Wächter ersetzen
\end{itemize}
\item Faustregel: Der Cut darf erst kommen, wenn man weiß, dass man in der rechtigen Regel ist, aber muss vor der Instanziierung der Ausgabevariablen stehen
\item Negation: Ein Negationsprädikat ist in Prolog ohne (roten) Cut nicht ausdrückbar
\end{itemize}
\subsection{Unifikation und Resolution (S272)}
\subsubsection{Unifikation (S273)}
\begin{itemize}
\item Methode zur Vereinheitlichung prädikatenlogischer Ausdrücke\footnote{\url{https://de.wikipedia.org/wiki/Unifikation_(Logik)}}
\item Ziel: Finde Substitution, die alle Gleichungen erfüllt \(\rightarrow\) "`Unifikator"'
\item Formaler Algorithmus auf Folie S274, ausführliches Beispiel auf Folie S275
\item Klammersetzung beachten!
\end{itemize}
\subsubsection{Der Algorithmus}
\begin{itemize}
\item Eingabe: Eine Liste von Gleichungen
\item Wiederhole, solange Gleichungen in der Liste
\begin{enumerate}
\item Nehme die erste Gleichung und versuche die Variable, die alleine steht, in den anderen Gleichungen zu ersetzen. Steht auf beiden Seiten eine Funktion kann gleichgesetzt werden (Beispiel: \texttt{f(X1, X2) = f(X3, X4) \(\rightarrow\) X1 = X2, X3 = X4}). Beide Gleichungen werden anschließend hinten an der Liste der zu bearbeitenden Gleichungen angefügt
\item Falls eingesetzt werden konnte, füge die Gleichung einer invertierten Ergebnisliste hinzu. NICHT hinzufügen bei Gleichsetzungen
\end{enumerate}
\item Anschließend: Ersetzen der Nichtterminale durch Terminale sowie Zusammenfassen zu einem Ausdruck
\end{itemize}
\section{Grundlagen der Parallelprogrammierung (RE1)}
Motivation: Leistungssteigerung über steigende Taktfrequenzen hinaus. Murphys Gesetz der mangelnden Performance: Jeder Computer ist zu langsam.
\subsubsection{Grundbegriffe}
\begin{itemize}
\item Race Condition: Ein kritischer Wettlauf ist in der Programmierung eine Konstellation, in der das Ergebnis einer Operation vom zeitlichen Verhalten bestimmter Einzeloperationen abhängt. Im Allgemeinen ist die Möglichkeit, dass eine Race Condition entsteht, zu vermeiden.\footnote{\url{https://de.wikipedia.org/wiki/Race_Condition}}
\item \textbf{Bedingungen für einen Deadlock\footnote{\url{https://de.wikipedia.org/wiki/Deadlock_\%28Informatik\%29\#Allgemeines}}}
\begin{enumerate}
\item No Preemption: Die Betriebsmittel werden ausschließlich durch die Prozesse freigegeben
\item Hold and Wait: Die Prozesse fordern Betriebsmittel an, behalten aber zugleich den Zugriff auf andere
\item Mutual Exclusion: Der Zugriff auf die Betriebsmittel ist exklusiv
\item Circular Wait: Mindestens zwei Prozesse besitzen bezüglich der Betriebsmittel eine zirkuläre Abhängigkeit
\end{enumerate}
\end{itemize}
\subsubsection{Programmieransätze gemäß der Computerarchitektur (RE11)}
\begin{itemize}
\item Gemeinsamer Speicher: Jeder Prozessor kann jede Speicherzelle ansprechen (z.B. Multikernrechner)
\item Verteilter Speicher: Jeder Prozessor hat seinen eigenen Speicher, Kommunikation über \textit{Message Passing} (z.B. bei Computerclustern)
\end{itemize}
Bei sequentieller Programmierung arbeitet der Prozessor nacheinander einzelne Befehle aus dem Arbeitsspeicher ab (von-Neumann-Architektur).
Bei paralleler Programmierung wird in der Theorie häufig das \textit{PRAM-Modell} (RE12) mit einer beliebigen Anzahl an Prozessoren mit
\begin{itemize}
\item jeweils lokalem Speicher
\item und synchronem Zugriff auf globalen, gemeinsam genutzten Speicher (in der Praxis eher problematisch bei der Umsetzung)
\end{itemize}
zu Grunde gelegt.
\subsubsection{Flynn's Taxonomy (RE13)}
\begin{enumerate}
\item \textit{Single Instruction x Single Data:} Klassische von-Neumann-Architektur, ein Befehlsstrom arbeitet auf dem Speicher
\item \textit{Single Instruction x Multiple Data:} Ein Befehl wird auf gleichartige Daten (z.B. Arrays) angewendet, typischerweise in Vektorprozessoren früherer Supercomputers
\item \textit{Multiple Instruction x Multiple Data:} Verschiedene Prozessoren arbeiten auf verschiedenen Daten, beispielsweise in heutigen Multicore-Maschinen
\item \textit{Multiple Instruction x Single Data:} Mehrere Befehle werden gleichzeitig auf den gleichen Daten ausgeführt, beispielsweise in redundanten Architekturen oder in den Pipelines moderner Prozessoren (Ansicht ist umstritten)
\end{enumerate}
\subsubsection{Herausforderungen (RE14)}
\begin{itemize}
\item Bereits schrittweise Parallelität benötigt Synchronisation
\item Kommunikation der Prozesse untereinander
\item Wettlaufbedingungen und Verklemmungen
\end{itemize}
Idealerweise lassen sich Probleme für Parallelverarbeitung so zerlegen, dass sie ohne Abhängigkeiten berechnet werden können; auch stückweise Parallelisierung ist möglich.
\subsubsection{Mögliche Beschleunigung (RE17)}
\begin{itemize}
\item Speedup: \(S(p) = \frac{T(n,1)}{T(n,p)} = \frac{Aufwand~mit~einem~Prozessor}{Aufwand~mit~p~Prozessoren}\)
\item Amdahls Gesetz berechnet die maximale Beschleunigung, die durch Parallelverarbeitung erreicht werden kann: \(\frac{1}{(1-P)+\frac{P}{N}}\). \(P\) beziffert den Anteil des Programms, der parallel ausgeführt werden kann
\item Beispiele in Klausur vom WS2014 und auf Übungsblatt 11
\end{itemize}
\subsection{Fortgeschrittene Konzepte in Java (R21)}
Beispiele befinden sich jeweils bei den entsprechenden Folien.
\subsubsection{Multithreading in Java (RE22)}
\begin{itemize}
\item Threads vor Java oft eher schwierig zu implementieren (in C/C++ zusätzliche Bibliotheken notwendig)
\item In Java bereits in der Sprache enthalten
\item Nicht vorgegeben ist allerdings die interne Implementierung des Multithreading in der jeweiligen VM
\item Erben von der Klasse \textit{Thread} oder implementieren des Interface \textit{Runnable}
\item Threads beenden (RE27): \(stop()\) mit Hilfe von Pollen realisiert; ein Thread, der nicht beendet werden will, kann von außen nicht "`sauber"' beendet werden
\item Rückgabewerte (RE30): Über \(Thread.join()\) realisierbar oder durch die Verwendung von \(Callables\) oder \(Futures\)
\item Prioritäten (RE31): Threads können mit Hilfe von \texttt{setPriority()} Prioritäten zugewiesen werden
\item Synchronisation (RE31): Methoden und Blöcke können mit dem Schlüsselwort \texttt{synchronized} vor Unterbrechnung geschützt werden
\end{itemize}
\subsubsection{Java ThreadPools und Executors (RE32)}
\begin{itemize}
\item Seit Java 5 gibt es eine Reihe von Erleichterungen zur Umsetzung von Parallelität
\item \texttt{ThreadPools} und \texttt{Executors} ersparen eine eigene Thread-Verwaltung
\item \texttt{Futures} erlauben die Rückgabe von Ergebnissen (R33)
\item Ausführliches Beispiel auf Folie 34
\end{itemize}
\subsection{Message Passing Interface (RM1)}
\begin{itemize}
\item Prozesse mit separaten Speicherbereichen kommunizieren via \textit{Messages}
\item SIMD: Das selbe Programm wird auf allen Rechnern ausgeführt (RM6)
\item Jeder Teilnehmer kennt seinen eigenen Rang (ID) und die Anzahl an Teilnehmern (RM5)
\item Es gibt keinen direkten Master, allerdings wird Prozess 0 per Konvention als "`master control program"' verwendet (RM9)
\item Die Prozesse können explizit synchronisiert werden, um eine sortierte Ausgabe zu erhalten (RM9)
\end{itemize}
\subsubsection{Übertragen von Nachrichten (RM11)}
\begin{itemize}
\item Asynchrone oder synchrone Übertragung möglich
\item \texttt{MPI\_Send} blockiert bis der Nachrichtenpuffer wiederverwendet werden kann
\item \texttt{MPI\_Recv} blockiert bis die Nachricht komplett gelesen worden ist
\item Non-blocking ebenfalls möglich, allerdings muss dann zusätzlich überprüft werden, ob die Nachricht vollständig übertragen worden ist (RM18)
\item Scatter/Gather schicken eine immer gleich große Datenmenge. Die vektorbasierten Funktionen können unterschiedlich große Mengen schicken
\end{itemize}
\subsubsection{Data Distribution (RM19)}
\begin{itemize}
\item \textbf{Generelles Vorgehen}
\begin{enumerate}
\item Verteilen der Daten ("`breakup"')
\item Durchführen der Berechnungen
\item Zusammenführen der Ergebnisse
\end{enumerate}
\item Spezielle Operationen zum Verteilen und Zusammenführen der Daten
\item Master-Teilnehmer zum Verteilen und Zusammenführen verantwortlich
\item Verschiedene Möglichkeiten zum Verteilen und Zusammenführen der Daten. Beispiele ab Folie 22
\end{itemize}
\subsection{Scala (RS1)}
\subsubsection{Überblick (RS3)}
\begin{itemize}
\item \textit{scalable language} mit kompakterem Code (beispielsweise automatische Getter und Setter)
\item Erweiterte Unterstützung für Parallelprogrammierung (Actors)
\item Kompiliert zu Java Bytecode
\item \textbf{Vergleich zu Java (RS5)}
\begin{itemize}
\item Primitive Datentype sind Objekte (vermeided Overhead beim boxing und unboxing)
\item In beiden Fällen keine Mehrfachvererbung
\item Compiler erkennt den Typ von Variablen ohne explizite Dekleration
\item \textit{Traits} (Interfaces) können bereits konkrete Implementierung enthalten
\item Direkte Integration von Singletons über das Schlüsselwort \texttt{objekt}
\item Funktional: Funktionen sind First-Class-Objects, Pattern-Matching, Closures, etc)
\end{itemize}
\end{itemize}
\subsubsection{Referenz}
\begin{itemize}
\item Variablen können als Konstanten definiert werden (RS8)
\item \textbf{Klassen und Konstruktoren (RS13)}
\begin{itemize}
\item Der primäre Konstruktor definiert impliziert \textit{einige} Getter und Setter (\texttt{.lastName} und \texttt{.lastName =})
\item Für Parameter ohne explizite Definition als Variable oder Konstante werden nicht als Feld initialisiert und erhalten daher auch weder Getter noch Setter
\item Uniform Access: Zugriffe werden auf Getter und Setter gemappt (RS14)
\end{itemize}
\item Methoden sind vergleichbar mit Java-Methoden, allerdings sind Kurzschreibweisen möglich, da Typen automatisch erkannt werden können (RS15)
\item Spezifische Getter und Setter: Die Namen von Feldern müssen umbenannt werden (RS16)
\item Typhierarchie (RS18)
\item \textbf{Traits (RS19)}
\begin{itemize}
\item Vergleichbar zu Java-Interfaces ("`Wesenszug"' oder "`Charaktereigenschaft"')
\item Können bereits (teilweise) implementiert sein (Vgl. Java-Abstract-Class)
\end{itemize}
\item Pattern-Matching: Vgl. mit Java-Switch (RS25)
\end{itemize}
\subsubsection{Parallelität in Scala (RS45)}
\begin{itemize}
\item Java: Feingranular, threadbasiert
\item Scala unterstützt die Java API
\item \textbf{Actors (RS46)}
\begin{itemize}
\item Implementierung ähnlich wie bei einem Java-Thread (Erweitern einer Klasse oder per Factory)
\item Nachrichtenbasierte Kommunikation mit asynchroner, race-freier und non-blocking Warteschlange (RS48)
\item Implementierung vergleichsweise schwergewichtig, beispielsweise blockiert ein \texttt{receive} den kompletten Thread
\item Shared-Nothing-Prinzip
\end{itemize}
\item \textbf{Futures in Scala (RS52)}
\begin{itemize}
\item Konzept: Platzhalter für ein Ergebnis, das später von einem bestimmten Thread ausgefüllt wird
\item Non-blocking und asynchron \(\rightarrow\) erlaubt Parallelität
\end{itemize}
\end{itemize}
\subsubsection{Code-Beispiel: Actor}
\begin{minipage}{\linewidth}
\begin{lstlisting}[frame=single,numbers=left,mathescape,language=Scala]
class MyActor extends Actor {
def act() {
loop {
receive {
// do something fancy and answer to sender
sender ! "stuff"
}
}
}
}
\end{lstlisting}
\end{minipage}
\subsubsection{Code-Beispiel: Future}
\begin{minipage}{\linewidth}
\begin{lstlisting}[frame=single,numbers=left,mathescape,language=Scala]
val i = 10;
val tasks = for (d <- 0 until b.length()) yield future {
// do something fancy and return
// can access elements defined out of the future
val x = 1000 * i;
// return as a result
x;
}
val futuresResult = awaitAll(20000L, tasks: _*);
\end{lstlisting}
\end{minipage}
\subsection{X10}
\subsubsection{Motivation (RX4)}
\begin{itemize}
\item Parallele Berechnung ist von der Unterstützung der Programmiersprache abhängig
\item Automatisierte Parallelprogrammierung durch den Compiler funktioniert nicht
\item Existierende Programmiersprache sind weitestgehend auf Threads limitiert
\item Programmiersprachen mit direkter Integration
\item Anwendungsbeispiel auf Blatt 12, Aufgabe 3
\end{itemize}
\subsubsection{Design}
\begin{itemize}
\item \textbf{Designziele (RX7)}
\begin{itemize}
\item Safety: Vermeidung von typischen Programmierfehlern wie beispielsweise NPE, Initialisierungsfehler, Overflows, etc
\item Analyzability: Automatische Erkennung von Parallelpfaden innerhalb des Programms
\item Scalability: Hinzufügen von Prozessoren sollte die Performance verbessern
\item Flexibility: Unterstützung für verschiedene Parallelentwicklungsansätze
\end{itemize}
\item \textbf{Designentscheidungen (RX8)}
\begin{enumerate}
\item Neue Programmiersprache: Keine Bibliothek oder Framework
\item Java als Ausgangspunkt
\item Einführung des \textit{Partitioned global address space} (PGAS)
\item Leichtgewichtige Nebenläufigkeit
\item Unterstützung für große, mehrdimensionale Arrays
\end{enumerate}
\item \textbf{Gemeinsamkeiten mit Java (RX9)}
\begin{itemize}
\item Klassen und Interfaces mit Einfachvererbeung und Objekthierarchie
\item Die üblichen Programm- und Kontrollstrukturen
\end{itemize}
\item \textbf{Unterschiede gegenüber Java (RX11)}
\begin{itemize}
\item Zusätzliche arithmetische Datentypen
\item Variablen und Konstanten wie in Scala
\item "`Richtige"' mehrdimensionale Arrays (keine Arrays in Arrays)
\item Eingeschränkte Typen und Methoden
\end{itemize}
\item Structs: Performanter als Objekte, allerdings ohne Vererbung (RX13)
\item Functions sind First-Class-Objects (RX14)
\item \textbf{Distribution (RX15)}
\begin{itemize}
\item Fundamentale Möglichkeiten zur Datenverteilung
\item Messages: Message-passing, MPI, Actors
\item Prozesse/Threads: Gemeinsamer Speicher, OpenMP, Java
\item Address Space: PGAS, UPC, CAF, Chapel, X10
\end{itemize}
\end{itemize}
\subsubsection{PGAS (RX17)}
\begin{itemize}
\item \textbf{Eigenschaften eines PGAS-System}
\begin{itemize}
\item Besteht aus einer Menge von Prozessoren und Arbeitsspeicher. Letzterer wird zwischen den Porzessoren aufgeteilt
\item Es gibt einen Mechanismus, um auf den Speicherbereich anderer Prozessoren zuzugreifen, was allerdings zwangsläufig mit einer Verzögerung verbunden ist
\item Jede Speicherzelle ist mit einem Thread assoziiert
\end{itemize}
\item \textbf{Einfache Parallelität mit async: \texttt{async S} (RX19)}
\begin{itemize}
\item Legt eine neue Kind-Activity an, welches das Statement \texttt{S} ausführt und sofort zurückgibt
\item Kann nicht benannt oder abgebrochen werden
\item Ersetzt kein \texttt{atomic} bei konkurierendem Zugriff auf ein Objekt!
\end{itemize}
\item \textbf{Synchronisation: \texttt{finish S} (RX20)}
\begin{itemize}
\item Führt \texttt{S} aus und wartet, bis alle \texttt{asyncs} abgearbeitet worden sind \(\rightarrow\) geschachtelt mit \texttt{async} verwendbar
\item Nützlich für lokale oder entfernte Daten
\end{itemize}
\item \textbf{Isolation: \texttt{atomic S} (RX21)}
\begin{itemize}
\item Führt \texttt{S} atomar seriell aus
\item Vergleichbar mit \texttt{synchronized} in Java
\item Atomare Blöcke müssen non-blocking und sequentiell sein und müssen auf lokalen daten arbeiten
\item Diese Einschränkungen werden dynamisch überprüft
\end{itemize}
\item \textbf{Conditional Wait: \texttt{when (E) S} (RX22)}
\begin{itemize}
\item Die Activity setzt aus, bis der Zustand des Guard \texttt{E} \texttt{true} gesetzt wird
\item \texttt{S} wird dann atomar ausgeführt
\item Für den Guard \texttt{E} gelten die selben Eigenschaften, wie für atomare Blöcke
\end{itemize}
\item \textbf{Localization: \texttt{at (p) S} (RX23)}
\begin{itemize}
\item Leichtgewichtiger Thread ohne eigenen Namen, der asynchron ausgeführt wird
\item \texttt{S} wird bei \texttt{p} ausgeführt
\item Während der Ausführung von \texttt{S} wird \texttt{p} blockiert
\end{itemize}
\end{itemize}
\section{Compiler (S323)}
\subsection{Einführung (S324)}
\begin{itemize}