Spiker exam 18/19 PDF

Preview

Summary

spiker für examen...

Description

(*Kompilieren mit Threadunterstützung:*) (*ocamlc -o test.out -thread -I +threads unix.cma threads.cma *) (* Natürlich beherrscht OCaml auch Threading. Ein Thread wird erzeugt durch Thread.create . Der Thread berechnet dann die übergeben Funktion mit dem übergebenen Parameter und terminiert danach. Thread.create gibt eine Thread-ID des erstellten Threads zurück, die man z.B. verwenden kann, um den erzeugten Thread zu killen. Die Signatur lautet ('a -> 'b) -> 'a -> t *) (* Beispiel: Erstelle einen Thread, der seinen Parameter mit 1 addiert wir übergeben dem neuen Thread die Zahl 10 *) let t = Thread.create (fun x -> x+1) 10 (* Beachte: t enthält nicht jetzt nicht das Ergebnis der Berechnung des Threads 11, sondern die Thread-ID. Wie wir die Kommunikation zwischen den Threads herstellen können, also z.B. hier das Ergebnis 11 zurückerhalten, kommt später. *) (* Anderes Beispiel: fold_left in einem neuen Thread*) Thread.create (fold_left (fun a x -> a+x) 0) [1;2;3] (* Alternativ hätten wir auch schreiben können: *) Thread.create (fun () -> fold_left (fun a x -> a+x) 0 [1;2;3]) () (* Die Klammern () entsprechen was man aus Java als void kennt. In OCaml haben sie den Typ unit. *) (* Aufgabe: * 1) Erstelle eine Funktion, die eine int liste nimmt und alle Elemente auf die Konsole * ausgibt * 2) Führe die Funktion aus 1) nebenläufig in einen Thread aus. * Print-Funktionen: print_string, print_int, print_float, ...*) (*Lösung Aufgabe 1) *) let rec f = function [] -> print_string "\n" | x::xs -> print_int x ; print_string ", "; f xs (*Lösung fuer Aufgabe 2*) let _ = Thread.create f [1;2;3] (* Der Infix-Operator ; nimmt zwei Ausdrücke und gibt das Ergebnis des rechten Ausdruckes zurück. z.B. liefert (1+2);(2+3) die Zahl 5 zurück. Im Normalfall sollte der linke Term einen unit zurückliefern. *) open Event (* Nun widmen wir uns dem Datenaustausch zischen Threads. Dies geschieht mit channels, die man sich wie eine Datenleitung zwischen Threads vorstellen kann. Die notwendigen Funktionen (new_channel, sync, send, receive, wrap, select) befinden sich im Event Modul. Zunächst erstellen wir uns einen channel: *) let ch = new_channel () (* Jetzt wollen wir einen neuen Thread starten, und auf dessen Ergebnis warten Dafür erstellen wir einen Thread, der uns ganz primitv nur die Zahl 10 zurücksenden soll. Das senden passiert über den Channel mit Hilfe von send und sync. send liefert ein sogenannten Event zurück. Auf dieses können wir uns dann mit sync synchronisieren, um die Daten, die im Event stecken, wirklich loszusenden. Das kann man sich so vorstellen, als ob wir uns zunächst nur vorbereiten, Daten über die Leitung zu schicken, aber noch nicht wirklich lossenden. Erst mit sync senden wir die Nachricht los UND blockieren danach solange, bis jemand unsere Nachricht vom Kanal abnimmt. *) let _ = Thread.create (fun c -> sync(send c 10)) ch (* Analog verläuft es mit dem Empfang von Daten. mit receive bereiten wir uns zunächst nur aufs Empfangen vor und mit sync warten wir solange, bis wir Daten vom Kanal erhalten *) let e = sync (receive ch) let _ = print_int e (* Würden wir jetzt erneut sync (receive ch) aufrufen, erhalten wir nicht erneut die Zahl 10, sondern würden für immer blockieren/warten. *) (* Es können auch mehrere Threads über einen Kanal senden *) let ch = new_channel () let t1 = Thread.create (fun ch -> sync(send ch "Thread 1")) ch let t2 = Thread.create (fun ch -> Thread.delay 1; sync(send ch "Thread 2")) ch (* Zuerst vom schnellen Thread empfangen *) let s = sync (receive c) (* Aber danach auch vom langsamen Thread *) let s = (s, sync(receive c)) (* Das ganze hätte man auch etwas anders schreiben können: Mit hilfe von select können wir aus einer Liste von Events, das Ergebnis des schnellsten Events auswählen *) let (c1,c2) = (new_channel (), new_channel ()) let t1 = Thread.create (fun ch -> sync(send ch "Thread 1")) c1 let t2 = Thread.create (fun ch -> sync(send ch "Thread 2")) c2 (* Zuerst vom schnellen Thread empfangen *) let f = select[receive c1;receive c2] (* Dann aber auch vom langsameren Thread *) let s = select[receive c1;receive c2] (* Analog funktioniert choose . Choose liefert aber das schnellere Event und nicht dessen Ergebnis zurück. select ist in OCaml eigentlich wie folgt definiert: *) let select l = sync (choose l) (* Manchmal will man wissen, welches Event gewählt wurde. Das kann man mit wrap erzielen. wrap packt um das übergebene Event im ersten Parameter ein neues Event, indem es auf das Ergebnis des ersten Events die übergebene Funktion anwendet. val wrap : 'a event -> ('a -> 'b) -> 'b event *) let (c_odd,c_even) = (new_channel(), new_channel()) let t1 = Thread.create (fun ch -> sync(send ch 1)) c_odd let t2 = Thread.create (fun ch -> sync(send ch 2)) c_even (* Nimm das Ergebnis vom schnelleren und verpacke es in ein neues Event, das ein Tupel zurückgibt, mit dem ursprünglichen Ergebnis und einem Identifikationsstring *) let (n,v) = select [ wrap (receive c_odd) (fun a -> ("odd",a)) ; wrap (receive c_even) (fun a -> ("even",a)) ] (* (n,v) ist jetzt entweder ("odd",1) oder ("even",2) *) let _ = print_string n (* oder äquivalent *) let s = choose [ wrap (receive c_odd) (fun a -> ("odd",a)); wrap (receive c_even) (fun a -> ("even",a)) ] |> sync (* Starte zwei Threads. Thread 1 wartet zuerst 100 Sekunden und sendet dann, Thread 2 sendet sofort *) let _ = Thread.create (fun x -> Thread.delay 100; sync(send c_odd x)) 1 let _ = Thread.create (fun x -> sync(send c_even x)) 2 (* Beide Ergebnisse werden empfangen. Zuerst vom schnelleren, dann vom langsamen *) let (c_odd_val, c_even_val) = select [ wrap (receive c_odd) (fun a -> (a, sync(receive c_even))); wrap (receive c_even) (fun a -> (sync(receive c_odd), a)) ] (* Das würde zwar auch funktionieren, allerdings muss Thread 2 jetzt 100 Sekunden auf Thread 1 warten da auf Thread 1 zuerst synchronisiert wird *) let (c_odd_val, c_even_val) = (sync(receive c_odd), sync(receive c_even)) (* Was ist Endrekursion und warum brauchen wir es? *)

(* Betrachte zunächst die folgende Implementierung für die Fibonacci Zahlen *) let rec fib n = let rec aux_fib n' = if n'=0 then (0,0) else if n'=1 then (0,1) else let (ppred, pred) = aux_fib (n'-1) in (pred, ppred+pred) in snd (aux_fib n)

Basics (* Ungleichheit testen *) (* a ist nicht gleich 5 *) a 5

(*Modulo rechnen*) (* Ein Aufruf von fib 1000000 würde nun 1000000 rekursive Aufrufe benötigen. Da 9 mod 2 (* gibt 1 zurueck *) muss jedem Informatiker sofort das Herz aufschreien, denn unser Stack würde dann ebenfalls (* Global Definition mit let *) eine Tiefe let x = 7 von mindestens 1000000 benötigen --> Stackoverflow/OutOfMemory exceptions. (* x hat jetzt den Wert 7 *) In imperativen Programmiersprachen können wir häufig Rekursion durch let z = x+3 Verwendung von Schleifen vermeiden. (* z hat jetzt den Wert 10, x immer noch 7 *) Wie soll das aber in funktionalen Programmiersprachen funktionieren? let x = 5 Die Antwort: Endrekursion. Wir schreiben die fib Funktion so um, dass der letzte (* x hat jetzt den Wert 5, z aber immer noch den Wert 10 *) Aufruf der Funktion der rekursive Aufruf ist. Somit kann der Compiler einfach den aktuellen Stackframe wiederverwenden und (* Lokale Definition mit let = in *) muss keinen neuen Rahmen auf den Stack erzeugen let z = let x = 1 in x+1 --> Effizient wie eine Schleife. *) (* z hat jetzt den Wert 2, x hat global immer noch den Wert 5, denn das innere let fib_tail n = let rec fib_aux (ppred,pred) n' = if n'=n then ppred+pred * x ist hier nicht mehr sichtbar *) else fib_aux (pred,ppred+pred) (n'+1) in if n a+b muss durch eine Konstante begrenzbar sein. *) let add = fun a -> fun b -> a+b let rec not_tail_rec = function x when x x | x -> let r = fib x in not_tail_rec (-r) (* Das geht nicht, da fib in der Definition noch unbekannt ist *) let fib a = if a=0 then 0 else if a=1 then 1 else fib(a-1)+fib(a-2) (* Diese offensichtliche nicht endrekursive Funktion... *) (* Wir muessen die Definition mit rec als rekursiv definieren *) let rec list_sum = function [] -> 0 | x::xs -> x+list_sum xs let rec fib a = if a=0 then 0 else if a=1 then 1 else fib(a-1)+fib(a-2) (* ...kann durch eine neue Hilfsfunktion mit einem Akkumulator einfach endrekursiv gemacht werden. *) let list_sum_tail l = let rec sum_aux acc = function [] -> acc | x::xs -> sum_aux (acc+x) xs in sum_aux 0 l

(* Eine absteigende Verzweigung*) type 'a desc_twig = Twig of {data: 'a; sub: 'a desc_twig; stop: 'a} | End (* Künstlerische Visualisierung für Twig {data=a; sub=Twig {data=b; sub=Twig {data=c; sub=End;stop=d};stop=e};stop=f} /a\ /b\ f /c\ e END d *) (* Wende rekursiv g zuerst von oben nach unten auf alle Sub-Zweige an und dann von unten nach oben auf alle Stop-Zweige. Also ergäbe sich als Reihenfolge für das obige Beispiel: a,b,c,d,e,f. Zunächst nicht endrekursiv: *) let rec fold_twig g acc = function End -> acc | Twig {data=d;sub;stop=s} -> g (fold_twig g (g acc d) sub) s (* Und jetzt endrekursiv. Die Idee dabei ist, sich die noch ausstehenden Stop-Zweige in einer Liste zu merken. (Anmerkung: fold_left ist endrekursiv, fold_right allerdings nicht) *) let fold_twig_tail g acc t = let rec fold_aux acc rem = function | End -> List.fold_left g acc rem | Twig {data=d;sub;stop=s} -> fold_aux (g acc d) (s::rem) sub in fold_aux acc [] t (* Alternative mit Continuations für die OCaml-Profis *) type ('a,'b) cont = Cont of ('a -> ('a,'b) cont list -> 'b) let fold_twig_conts g acc t = let rec fold_aux acc conts = function | End -> (match conts with (Cont x)::xs -> x acc xs | [] -> acc) | Twig {data=d;sub;stop=s} -> let c = Cont (fun acc conts -> fold_aux (g acc s) conts End) in fold_aux (g acc d) (c::conts) sub in fold_aux acc [] t (* Tipps, um Funktionen in endrekursive Funktionen abzuändern: 1) Definiere eine neue innere Hilfsfunktion, die einen Akkumulator übernimmt und das Ergebnis im rekursiven Aufruf direkt berechnet, anstatt als letzte Operation im Aufrufer (vgl. list_sum und list_sum_tail). Der Akkumulator kann nicht nur dazu dienen, bereits berechnete Werte zu speichern (vgl. list_sum_tail), sondern auch, um sich noch ausstehende Operationen/Elemente zu speichern (vgl. fold_twig_tail) 2) Versuche rekursive Berechnungen bottom-up anstatt top-down zu berechnen (vgl. fib und fib_tail) *) Module und funktoren module type BitGenerator = sig type t val init : int -> t val next : t -> (bool * t) val getint : t -> int end module type NumberGenerator = sig type t val init : int -> t val next : t -> (int * t) val getint : t -> int end (*10.4.1-Modul AlternatingBitGenerator, welches die Signatur BitGenerator erfüllt*) module AlternatingBitGenerator : BitGenerator =struct type t = string let init seed= if (seed mod 2) = 1 then"1" else "0" let next binary= if binary.[(String.length binary)-1]='1' then (false , binary ^ "0") else (true , binary ^ "1") let getint binary =if (String.length binary) empty | x::xs -> n_empty (* Direkt auf Tupel matchen *) match (a,empty) with ([],x) -> x | (x::xs, _) -> "Nonempty list" (* _ sagt so viel wie `hier ist was, aber mich interessiert nicht was` *) (* when in matches *) match a with | x when (x mod 2)=0 -> "gerade" | _ -> "ungerade" (* Folgende zwei Sachen machen das selbe *) (* function matched direkt auf einen weiteren Parameter *) let f a = function [] -> 0 | x::xs -> a let f a x = match x with [] -> 0 | x::xs -> a (* Man kann auch Operatoren definieren! *) let (==>) a b = a mod b (* Jetzt kann man schreiben: *) a ==> b (* Rechnet a mod b *) (* Inline Funktionen *) let a f x = f x a (fun x -> x*2) 4 (* Gibt als Ergebnis 8 *) (* Was passiert hier denn? *) let f x = let x = 1 in x (* Welchen Wert hat wohl b? *) let b = f 0 (* Antwort: 1 *) (* fold left und right *) let mystring = ["Hallo";"du";"EIDI2";"Student"] let ergebnis = fold_left (fun a s -> a^" "^s) "" mystring (* Ergebnis: " Hallo du EIDI2 Student" *) let ergebnis = fold_right (fun s a -> a^" "^s) mystring "" (* Ergebnis: " Student EIDI2 du Hallo" *) let ergebnis = fold_right (fun s a -> s^" "^a) mystring "" (* Ergebnis: "Hallo du EIDI2 Student " *) (* Summentypen *) type farbe = Gruen | Rot | Blau | Lilablassblau type 'a option = Some of 'a | None (*Beispiel für einen einfachen Zug *) type 'a train = Lok of ('a * 'a train) | Waggon of ('a * 'a train) | Ende let chuchu = Lok (1,Waggon(2,Ende))

Schleifeninvariante Jetzt kommt der schwierige Teil: Wir sind bei der Schleife angelangt und konnen  nun nicht einfach mehr sequentiell unsere Zusicherungen berechnen, sondern mussen  eine geeignete Schleifeninvariante I _nden. Um dies zu tun, gibt es ein paar Tipps: _ Die Schleifeninvariante hangt  im Normalfall irgendwie von der Laufvariable ab. _ Oft hangt  die Invariante stark mit der Aussage am \Ausstiegspunkt" (hier E) zusammen und beschreibt diesen in Abhangigkeit  der Laufvariable (hier i). _ Es ist besser, eine gultige  Aussage zu viel in die Invariante zu packen, als zu wenig (z.B. scheint hier i _ 0 vielleicht zunachst  uberussig;   manchmal ist dies aber eine entscheidende Notwendigkeit in der Veri_kation). _ Wenn man keine gute Vermutung hat, hilft es oft sich den Programmablauf (d.h. den Verlauf der Variablenwerte) fur eine Beispieleingabe aufzuschreiben Endrekusiv Rekusiver aufruf ist die letzte aktion zur berechnung Vorteil kein zusätzlicher speicher zur verwaltung der rekusion nötig, effizenter Currying(f a b = a+b+1) Anwendung von f auf a liefert funktion auf b lifert ergeniss

module MakeNumberGenerator( X : BitGenerator) : NumberGenerator =struct include X let rec next31 binary n = if n next31 y (n+1) ) else binary let init seed =next31 (X.init seed) 0 let next alt =match (X.next alt) with |(x,y) -> (X.getint y,y) end module RNG0 =MakeNumberGenerator(AlternatingBitGenerator) module RNG1 =MakeNumberGenerator(PolynomeBitGenerator)

Partelle Anwendung Ergebnis ist nicht vollständig ausgewertet , erfordert eingabe Funktion höherer ordnung: ergebnis oder argument ist wieder eine funktion Polymorph Typvariable nicht eingeschränkt á...