> module Juli30 where > import Control.Monad.Par > import Control.DeepSeq > import Control.Concurrent.STM > import Control.Concurrent > import Control.Monad (forever) > import Data.List (splitAt,insert, foldl') -------------- Nachtrag Concurrency / Parallelism -------------- 1) Parallelism exemplarisch an Control.Monad.Par ----------------- Eine eher explizitere Zuteilung von parallelen Programmaufrufen können wir mit der |Par|-Monade aus |Control.Monad.Par| erreichen. Dies erinnert einen vielleicht ein bisschen an TI 3, wo wir ebenfalls mit Befehlen wie fork oder join Prozesse gestartet, bzw. auf deren Terminisierung gewartet haben. Ähnlich dazu haben wir hier die Funktionen |fork| bzw. |spawn| und |get|. Das Starten einer parallelen Berechnung kann mit der Funktion |fork| initiiert werden; allerdings gibt uns diese Funktion nicht wirklich Aufschluss über das Ergebnis der Berechnung bzw. modelliert die Ausführung von Seiteneffekten. Siehe Signatur: < fork :: Par () -> Par () Hier kommen die sogenannten |IVar|s ins Spiel: Sie dienen als Kommunikationshilfsmittel und können Werte "nach außen" tragen, oder aber auch zwischen Prozessen austauschen. Hier beschränken wir uns auf ersteres: Starten wir einen Prozess mit < spawn :: NFData a => Par a -> Par (IVar a) so übergeben wir implizit eine Variable (einen IVar), an die das Ergebnis der Berechnung gebunden werden wird (Das NFData ignorieren wir jetzt einfach). Die Rückgabe dieser (IVar a) kann als Versprechen gesehen werden, den Wert der Berechnung in diese Variable zu schreiben, sobald dieser verfügbar ist (also sobald die Berechnung terminiert). Dieses Konzept gibt es auch in anderen Sprachen und wird häufig als Futures bezeichnet (Future = In der Zukunft wird ein Ergebnis geliefert). Da |Par| eine Monade ist, können wir wie üblich mit der |<-|-Notation auf den gekapselten Wert zugreifen, also < do ivar_fuer_die_berechnung_von_f <- spawn (return (f x)) Da wir von außen nicht wissen, wann der Prozess fertig sein wird, wartet die Funktion |get| solange, bis das als Argument übergebene IVar einen Wert trägt. Die Funktion |runPar| extrahiert letztendlich den Wert der monadischen Berechnung aus der |Par|-Monade. 2) Concurrency Control.Concurrent ------------------ Um einen neuen nebenläufigen Thread zu erstellen, können wir eine Berechung vom Typ |IO ()| durch den Aufruf von < forkIO :: IO () -> IO ThreadId in einem neuen Thread ausführen lassen. Dadurch, dass die Berechnung nebenläufig passiert, werden Effekte nichtdeterministisch verzahnt (siehe Interleaving, z.B. ALP IV). Hierbei ist wichtig, dass kein schwergewichtiger Prozess erstellt wird; die Verwaltung von Threads passiert innerhalb der Laufzeitumgebung von GHC und wird auch von dieser verwaltet (z.B. Scheduling). Der Einsatz von nebenläufigen Programmen ist genau dann sinnvoll, wenn es um eine Art von Interaktion zwischen Akteuren (hier: Threads) geht. Damit sich die Thread untereinander unterhalten können (z.B. Absprachen, wer dann auf welche Resourcen zugreifen darf), gibt es u.A. die MVars. In MVars können Werte gelagert und herausgenommen werden; möchte man einen Wert von einem MVar lesen, der gerade keinen Wert enthält, so wird man blockert, bis dieser einen Wert enthält. Analog verhält es sich beim Schreiben auf MVars. (Wer ALP IV schon gehört hat: Fällt euch etwas auf? MVars dienen also als Locks, oder aber als asynchroner Channel mit Puffergröße 1). Außerdem gibt es noch Kanäle, |Channel|s, die man zwischen Threads benutzen kann. Hiermit können mehrere Werte zwischen den jeweiligen Threads hin- und hergeschickt werden. -------------- Übungsaufgaben vom 29. Juli -------------- In den Übungsaufgaben sollte die |Par|-Monade für die Umsetzung von parallelen Programmen benutzt werden. Aus dem vorigen Abschnitt wissen wir bereits, wie wir dies mit Hilfe der |Par|-Monade tun können. 1) Quicksort parallel Zur Erinnerung: Wir können (sequentielles!) Quicksort in Haskell relativ elegant durch die folgende Funktion |quickSort| beschreiben: > quicksort :: Ord a => [a] -> [a] > quicksort [] = [] > quicksort (x:xs) = quicksort [y | y <- xs, y <= x] ++ [x] ++ quicksort [y | y <- xs, y > x] Um nun ein paralleles Quicksort zu erstellen, benutzen wir die Funktion |spawn| und lagern die rekursiven Aufrufe aus. Mit der Funktion |runPar| holen wir uns das Ergebnis der Berechnung, die Funktion |get| wartet jeweils auf die Teilergebnisse. Die ähnlich zum obigen Programm ist kaum übersehbar! Durch wenige Änderungen haben wir tatsächlich ein paralleles Programm geschrieben. > parQuicksort [] = [] > parQuicksort (x:xs) = runPar $ do > left <- spawn (return (parQuicksort [y | y <- xs, y <= x])) > right <- spawn (return (parQuicksort [y | y <- xs, y > x])) > l <- get left > r <- get right > return $ l ++ [x] ++ r 2) Mergesort parallel Schreiben wir uns erst mal eine |merge|-Funktion; das kann z.B. so aussehen: > merge :: Ord a => [a] -> [a] -> [a] > merge [] ys = ys > merge xs [] = xs > merge x'@(x:xs) y'@(y:ys) = case x <= y of > False -> insert x $ merge xs y' > True -> insert y $ merge x' ys Falls die Eingabelisten sortiert sind, garantiert uns |merge|, dass die resultierende Liste ebenfalls sortiert ist. Die Funktion |insert| aus |Data.List| fügt sortiert in eine Liste ein. Mergesort ergibt sich dann fast automatisch durch: > mergesort :: Ord a => [a] -> [a] > mergesort [] = [] > mergesort [x] = [x] > mergesort xs = (mergesort a) `merge` (mergesort b) > where (a,b) = splitAt (length xs `div` 2) xs Wieder wollen wir ein paralleles Mergesort haben. Also gehen wir wie gewohnt vor: > parMergesort [] = [] > parMergesort [x] = [x] > parMergesort xs = runPar $ do > left <- spawn (return (parMergesort a)) > right <- spawn (return (parMergesort b)) > l <- get left > r <- get right > return $ merge l r > where (a,b) = splitAt (length xs `div` 2) xs 3) Fibonacci parallel Die Funktion |fib| soll uns bei Eingabe n die n-te Fibonaccizahl liefern. Die Fibonaccizahlen sind spezifiziert durch die folgende rekursive Bildungsregel: > fib 0 = 0 > fib 1 = 1 > fib n = fib (n-1) + fib (n-2) Gut, dass wir in Haskell sind: Die Spezifikation der Fibonaccizahlen ist gleichzeitig ein lauffähiges Programm für ihre Berechnung. Zugegeben: Kein besonders effizientes (Übung: Wie viele rekursive Aufrufe finden bei Eingabe n statt?), aber immerhin! Das können wir natürlich auch parallelisieren: > parFib 0 = 0 > parFib 1 = 1 > parFib n = runPar $ do > fib' <- spawn (return (parFib (n-1))) > fib'' <- spawn (return (parFib (n-2))) > a <- get fib' > b <- get fib'' > return $ a + b Hierbei müssen wir natürlich dran denken, dass die immense Ineffizienz der naiver Implementierung nicht wirklich durch die Parallelisierung ausgeglichen wird. -------------- Concurrency: STM -------------- Eine eher neuere Idee um Konsistenzproblemen der Nebenläufigkeit zu begegnen, ist Software Transactional Memory (STM). Hierbei orientiert man sich das Transaktionskonzept, wie man es z.B. aus Datenbanksystemen kennt, und ist erst mal optimistisch: Es wird gehofft, dass keine Konflikte auftreten und man greift erst ein, falls welche entdeckt werden. Recap: Transaktionen Transaktionen kapseln eine Folge von Aktionen in einer logischen Einheit, die komplett erfolgreich ausgeführt werden muss, oder sonst rückgängig gemacht wird. Ein typisches Beispiel sind Überweisungen im Bankensystem; eine Transaktion ist hierbei die Bündelung BEGIN Entferne x Euro von Konto a Füge x Euro zu Konto b hinzu END also eine Überweisung. Dass diese Aktion nur komplett ausgeführt werden soll, ist wohl offensichtlich (sonst würde ja Geld verschwinden!). Eine Transaktion kann in Haskell durch die |STM|-Monade aus |Control.Concurrent.STM| dargestellt werden. Dabei können wir eine Funktion |atomically| verwenden, die eine Transaktion atomar ausführt. Das Abbrechen, was wir aus Datenbanktransaktionen kennen, können wir hier auch machen: Die Funktion |retry| erlaubt uns eine Transaktion neuzustarten (falls wir z.B. gesehen haben, dass wir eine bestimmte Aktion gerade nicht ausführen dürfen), die Funktion |orElse| erlaubt es uns sogar, eine Alternativtransaktion anzubieten, falls die erste nicht erfolgreich war. Die Variablen, die durch die Transaktionen manipuliert werden, sind die sog. TVars, die mit der Funktion |newTVar| erstellt werden können. Lesen und schreiben können wir mit den Funktionen |readTVar| respektive |writeTVar|. Die Transaktionen und TVars sind dabei zu klug implementiert, dass ein Prozess, der eine Transaktion abbrechen musste, schlafen gelegt wird bis die beteiligte TVar von einem anderen Thread verändert wurde (Für die ALP IV-Leute: Das ist vergleichbar mit implizieten Monitor- Conditions). Damit können wir z.B. einfach eine Semaphore implementieren: > data Semaphore = Sema (TVar Int) > mkSema :: Int -> IO Semaphore > mkSema n = atomically $ do s <- newTVar n > return $ Sema s Und damit können wir die P-Operation als Transaktion auf der Semaphore implementieren: > p :: Semaphore -> IO () > p (Sema sem) = atomically $ do s <- readTVar sem > case s of > 0 -> retry > _ -> writeTVar sem (s - 1) Falls der interne Wert der Semaphore Null erreicht hat, dürfen wir |p| nicht ausführen, sondern müssen warten (die Transkation später noch mal neu probieren). Die |v|-Operation ergibt sich analog durch > v :: Semaphore -> IO () > v (Sema sem) = atomically $ do s <- readTVar sem > writeTVar sem (s+1) > test = do forkIO (forever $ putStr "Hallo" >> threadDelay 10000) > forkIO (forever $ putStrLn " Welt!" >> threadDelay 10000) > test' = do sema <- mkSema 0 > sema' <- mkSema 1 > forkIO (forever $ do > p sema' > putStr "Hallo" > v sema > threadDelay 10000) > forkIO (forever $ do > p sema > putStrLn " Welt" > v sema' > threadDelay 10000) -------------- Laziness vs. strictness -------------- Laziness macht zwar vieles sehr schön (unendliche Strukturen; Berechnung von Ausdrücken, nur wenn dies tatsächlich notwendig ist), macht aber manchmal auch einige Probleme. Ein typisches Szenario ist folgendes: Wir haben einen hohen Speicherplatzbedarf, da viele nicht oder nur teilweise berechnete Ausdrucke noch im Speicher liegen. Dies ist manchmal auch nicht wünschenswert, wenn wir eine schnelle Antwort auf eine Anfrage haben wollen (diese also vorberechnet sein soll). Betrachten wir den Ausdruck > redex = foldl (+) 0 [1, 2, 3, 4, 5, 6] so stellen wir fest, dass Haskell diesen wegen seiner Laziness wie folgt auswertet: < foldl (+) 0 [1, 2, 3, 4, 5, 6] < = foldl (+) (0 + 1) [2, 3, 4, 5, 6] < = foldl (+) ((0 + 1) + 2) [3, 4, 5, 6] < = foldl (+) (((0 + 1) + 2) + 3) [4, 5, 6] < = foldl (+) ((((0 + 1) + 2) + 3) + 4) [5, 6] < = foldl (+) (((((0 + 1) + 2) + 3) + 4) + 5) [6] < = foldl (+) ((((((0 + 1) + 2) + 3) + 4) + 5) + 6) [] < = (((((0 + 1) + 2) + 3) + 4) + 5) + 6 < = ((((1 + 2) + 3) + 4) + 5) + 6 < = (((3 + 3) + 4) + 5) + 6 < = ((6 + 4) + 5) + 6 < = (10 + 5) + 6 < = 15 + 6 < = 21 Wir bauen also erst mal einen riesigen Ausdruck auf, um diesen dann am Ende zu einer Zahl zu reduzieren. Das wollen wir nicht wirklich haben, wir würden gerne den Wert des Akkumulators strikt berechnen. Dafür gibt es in Haskell die Funktion |seq| mit den Eigenschaften < bottom `seq` b = bottom < a `seq` b = b Sie ist also strikt in ihrem ersten Argument. Was nun genau intern passiert, wollen wir uns hier nicht anschauen. Uns reicht es, dass die Funktion irgendwie eine Auswertung ihres ersten Arguments erzwingt. Was das genau heißt, werden wir später sehen. Die Striktheit können wir z.B. bei folgendem Code sehen: > lazy = let x = undefined in 5 > strict = let x = undefined in x `seq` 5 Dabei gibt |lazy| kein undefined zurück, |strict| aber schon. Das liegt daran, dass das |x| im zweiten Fall durch |seq| ausgewertet wird. Zur einfachen Benutzung von seq wurde ($!) analog zu ($) als strikte Applikation definiert. Damit ergibt sich > lazy1 = const "hallo" $ (error "welt") Kein Fehler! > strict1 = const "hallo" $! (error "welt") Fehler! |error| wurde ausgewertet. Damit können wir nun eine strikte Variante von |foldl|, genannt |foldl'| implementieren: < foldl' :: (a -> b -> a) -> a -> [b] -> a < foldl' f a [] = a < foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs und damit den neuen Ausdruck > redex' = foldl' (+) 0 [1, 2, 3, 4, 5, 6] Damit würde die Reduktion nun so aussehen: < foldl' (+) 0 [1, 2, 3, 4, 5, 6] < = foldl' (+) 1 [2, 3, 4, 5, 6] < = foldl' (+) 3 [3, 4, 5, 6] < = foldl' (+) 6 [4, 5, 6] < = foldl' (+) 10 [5, 6] < = foldl' (+) 15 [6] < = foldl' (+) 21 [] < = 21 Schauen wir nochmal zurück auf die Funktionen |lazy1| und |strict1|, beobachten wir aber, dass das nicht immer reicht! Denn wie ist es mit den folgenden Beispielen? > lazy2 = const "hallo" $ [error "welt"] > strict2 = const "hallo" $! [error "welt"] Beide geben keinen Fehler, sondern "hallo" zurück. Wie kann das sein? Das liegt daran, dass die |seq| Funktion ihren ersten Parameter "nur" in weak head normal form (whnf) bringt, also nur teilweise auswertet. Was heißt das nun genau? Erinnern wir uns an ALP 1: Ein Ausdruck ist in Normalform, wenn er nicht mehr weiter reduziert (Beta-Reduktion) werden kann. Diese Audrücke können noch weiter reduziert werden: < 1+2 nicht in Normalform < (\x -> f x) 2 nicht in Normalform < (2*5, 0) nicht in Normalform Diese Ausdrücke können nicht weiter reduziert werden: < 3 in Normalform < (\x -> 2*x} in Normalform < (5,6) in Normalform Eine schwächere Form von Normalform ist die sog. Weak head normal form (WHNF). Ein Ausdruck ist in WHNF wenn der äußerste Ausdruck ein Konstruktur oder eine Lambda-Abstraktion ist. Merke: Jeder Term, der in Normalform ist, ist automatisch auch in WHNF - nicht aber andersherum! < (2*5, 0) in WHNF < [5, 1+0, 5*5] in WHNF < (\x -> 2 + 2) in WHNF In den ersten beiden Fällen sind Konstruktoren ganz außen (Tupelkonstruktor, Listenkonstruktor); im dritten Fall eine Lambda-Abstraktion. Sind dagegen ganz außen Funktionsapplikationen, so sind diese nicht in WHNF: < 2 + 5 nicht in WHNF < (\x -> f x) 2 nicht in WHNF Ist unser Ausdruck also > redex2 = foldl' f (0,0) [1, 2, 3, 4, 5, 6] mit > f (a,b) x = (a+x,b+x) (ja, die Funktion macht nicht wirklich Sinn, egal!) ergibt sich die Auswertung durch < foldl' f (0,0) [1, 2, 3, 4, 5, 6] < = foldl' f (0 + 1,0 + 1) [2, 3, 4, 5, 6] < = foldl' f ((0 + 1) + 2,(0 + 1) + 2) [3,4,5,6] < = ... < = ((((((0 + 1) + 2) + 3) + 4) + 5) + 6,(((((0 + 1) + 2) + 3) + 4) + 5) + 6) < = ... < = (21,21) Hier wird also wieder ein riesiger Ausdruck erzeugt. Das liegt ganz einfach daran, dass der Akkumulator (x,y) der Faltung immer im WHNF vorliegt und damit nicht weiter ausgewertet wird. Wenn wir also garantieren wollen, dass eine Datenstruktur komplett berechnet wird, müssen wir etwas mehr machen. Auftritt |deepseq|: Wie der Name schon andeutet, tut deepseq genau das, was wir wollen; wir werden komplett "in die Tiefe" aus. Genau wie bei seq gibt es auch für deepseq eine infix-Schreibweise: < ($!!) :: NFData a => (a -> b) -> a -> b Erinnern wir uns also an < strict2 = const "hallo" $! [error "welt"] so wurde hier kein Fehler angezeigt, da |[error "..."]| bereits in WHNF ist. Die Auswertung in Normalform können wir aber nun erzwingen: > strict3 = const "hallo" $!! ([error "welt"] :: [String]) Liefert wie erwartet einen Fehler. Inzwischen gemerkt? Das |NFData a => ...| heißt, dass wir mit einem Typ arbeiten wollen, der überhaupt eine Normalform hat. Wie wir eben gesehen haben, wertet |deepseq| bis zur Normalform aus. Allerdings haben nicht alle Ausdrücke eine Normalform (welcher z.B. nicht?), darum müssen wir sicherstellen, dass die eingegebenen Werte eine Normalform haben. Damit können wir uns nun auch eine "ultrastrikte" Version von fold schreiben > foldl'' :: NFData a => (a -> b -> a) -> a -> [b] -> a > foldl'' f a [] = a > foldl'' f a (x:xs) = let a' = f a x in a' `deepseq` foldl'' f a' xs und damit den vorigen Ausdruck strikt auswerten: > redex3 = foldl'' f ((0,0)::(Int,Int)) [1, 2, 3, 4, 5, 6]