Paradygmaty programowania - ćwiczenia
Lista 10
1. Skomentuj efektywność użycia wątków w poniższej współbieżnej wersji funkcji Filter.
fun {Filter L F}
case thread L end
of X|Xs then if thread {F X} end
then X|{Filter Xs F}
else {Filter Xs F} end
[] nil then nil
end
end
2. Wyjaśnij sposób wykonania poniższych instrukcji przez maszynę abstrakcyjną (rysując obraz pamięci) i podaj wartości zmiennych po zakończeniu wykonania.
a) declare X Y Z
thread if X==1 then Y=2 else Z=2 end end
thread if Y==1 then X=1 else Z=2 end end
X=1
b) declare X Y Z
thread if X==1 then Y=2 else Z=2 end end
thread if Y==1 then X=1 else Z=2 end end
X=2
3. Napisz program zawierający wątek producenta, produkującego skończony strumień N>0 losowych liczb całkowitych, oraz wątek konsumenta, znajdującego najmniejszą i największą wartość w tym strumieniu.
Wykorzystaj generator liczb pseudolosowych {OS.rand ? I}.
4. Na wykładzie 3 przedstawiono generowanie liczb pierwszych metodą sita Eratostenesa. Napisz program, generujący liczby pierwsze z przedziału 2..N dla zadanego N z wykorzystaniem potoku. Producent generuje strumień kolejnych liczb naturalnych od 2 do N. Przetwornik jest sitem, które przepuszcza otrzymany element strumienia (głowę listy) i tworzy filtr usuwający wszystkie jego wielokrotności z reszty strumienia (ogona listy), a następnie wywołuje się rekurencyjnie dla przefiltrowanego strumienia.
Konsumentem jest przeglądarka (Browser), wyświetlająca otrzymany strumień liczb pierwszych. Wykorzystaj funkcjonał biblioteczny Filter.
5.
a) Zdefiniuj funkcję {ScaleStream S C}, mnożącą każdy element strumienia liczb zmiennoprzecinkowych S przez C.
b) Zdefiniuj funkcję PartialSums, której argumentem jest strumień liczb zmiennoprzecinkowych S, a wynikiem jest strumień o elementach równych S0, S0+S1, S0+S1+S2, … . Na przykład dla strumienia 1.|2.|3.|4|5.|… funkcja powinna zwracać strumień 1.|3.|6.|10.|15.|… .
6. Od Leibniza pochodzi przedstawienie liczby π w postaci szeregu naprzemiennego: π/4 = 1-1/3+1/5-1/7+ …
a) Zdefiniuj potok, w którym konsument (Browser) otrzymuje strumień coraz lepszych przybliżeń π. Producent generuje strumień składników szeregu o zadanej długości, czyli odwrotności nieparzystych liczb całkowitych, o naprzemiennych znakach. Pierwszym przetwornikiem jest PartialSums, a drugim ScaleStream.
b) Powyższy szereg jest niestety bardzo wolno zbieżny. Możemy jednak przekształcić strumień za pomocą akceleratora ciągów zmieniającego ciąg przybliżeń w nowy ciąg, który zbiega do tej samej wartości, ale szybciej. Jeden z takich akceleratorów, autorstwa Eulera, działa dobrze dla ciągów, które są sumami częściowymi szeregów naprzemiennych (tj. szeregów, których wyrazy mają naprzemienne znaki). W metodzie Eulera, jeśli Sn jest n-tym wyrazem danego ciągu sum częściowych, to wynikiem akceleracji jest ciąg o wyrazach
Sn+1 – (Sn+1 – Sn)2 / (Sn-1 – 2Sn + Sn+1)
Napisz przetwornik EulerTransform, przekształcający strumień liczb zmiennoprzecinkowych zgodnie z powyższym wzorem i dołącz go do potoku z punktu a). Zaobserwuj znaczną poprawę szybkości zbieżności.