Programowanie funkcyjne/Programowanie imperatywne

Wstęp

Paradygmat programowania imperatywnego opiera się na następującej analogii: Zwykle system obliczeniowy modeluje pewien fragment istniejącego świata rzeczywistego. W świecie rzeczywistym mamy do czynienia z obiektami, które w miarę upływu czasu zmieniają swoje stany. W systemie obliczeniowym możemy je modelować za pomocą obiektów obliczeniowych, które też mogą zmieniać stany.

Referencje

Programy imperatywne można pisać wykorzystując referencje:

• referencje, let r = ref x;;,
• wyłuskanie wartości, !r,
• dynamiczna zmiana wartości, r := 5

Kłopoty z polimorfizmem. Referencja wskazuje na wartość przynajmniej tak ogólną jak typ referencji. Wyłuskując wskazywaną wartość polimorficzną możemy ją ukonkretnić. Przypisując wartość możemy podać wartość bardziej ogólną. Przypisując wartość konkretniejszą powodujemy ukonkretnienie typu referencji!

let f x y = x;;
val f : 'a -> 'b -> 'a = <fun>
let g x y = x + 1;;
val g : int -> 'a -> int = <fun>
let h x y = x + y;;
val h : int -> int -> int = <fun>
let i x y = if y then x else 2 * x;;
val i : int -> bool -> int = <fun>
let r = ref g;;
r := f;;
r := h;; --- zmienia się typ r!
r := i;; --- błąd
     

Konstrukcje imperatywne

W momencie, gdy mamy operacje imperatywne, istotne stają się ich efekty uboczne (a nie koniecznie wartość) oraz kolejność wykonania. Przydatne stają się następujące konstrukcje:

• średnik ;,
• tablice [| ... |], Array.create długość wart.pocz.,
• a.(i) <- w,
• pętla for: for v = wyr to wyr do ... done,
• pętla while: while wyr do ... done,
• wypisywanie: print_...,
• wczytywanie: read_....

Obiekty i stany

W jaki sposób możemy tworzyć obiekty obliczeniowe zdolne do zmiany stanu? Obiektami takimi są referencje. Można jednak tworzyć obiekty lokalne, dostępne tylko wybranym procedurom. Widzieliśmy to już na przykładzie techniki spamiętywania. Obiekt może być procedurą, wraz z wartościami lokalnymi widocznymi tylko dla niej. Może ona zmieniać te wartości za pomocą set! (przypisanie).

let generator s = 
  let r = ref s 
  in
    function x -> begin
      r := !r + x;
      !r
    end;;
      

Zauważmy, że każde wywołanie procedury generator wiąże sięz powstaniem osobnej ramki zawierającej argument s.Wynikiem każdego takiego wywołania jest procedura, która może zmieniać wartość zapamiętaną jako s.

let o = generator 0;;
o 22;;
- : int = 22o 20;;
- : int = 42      

Rozrysować ramki.

Przykład: konto bankowe

Stan obiektu jest wyznaczony przez zawarte w nim zmienne stanowe.Dobrym zwyczajem jest wprowadzenie bariery abstrakcji oddzielającej zmienne stanowe obiektu od "`świata zewnętrznego. Obiekt powinien natomiast udostępniać metody umożliwiające zmianę jego stanu. Ustalamy więc interfejs obiektu złożony z metod zmianystanu obiektu. Ukrywamy natomiast implementację stanu obiektu za pomocąjego zmiennych stanowych.

Możemy tutaj zastosować technikę przesyłania komunikatów --- to obiekt sam zmieniaswój stan na skutek otrzymania komunikatu opisującego zdarzenie powodujące zmianę.

Ponieważ zwykle operujemy na wielu obiektach, powinniśmy zastosować technikę hermetyzacji.Każdy obiekt powinniśmy zamknąć w osobnym "pudełku". Jedynie metody udostępniane przez obiekt mogą mieć dostęp do wnętrza obiektu. Dodatkowo mamy konstruktor --- procedurę tworzącą nowe obiekty.

let konto pocz = 
  let saldo = ref pocz
  in
    let wplata kwota = 
      if kwota > 0 then begin
        saldo := !saldo + kwota;
        !saldo
      end else failwith "Ujemna kwota"
    and wyplata kwota = 
      if kwota > 0 then 
        if kwota <= !saldo then begin
          saldo := !saldo - kwota;
          !saldo
        end else failwith "Brak środków na koncie"
      else failwith "Ujemna kwota"
    in
      (wplata, wyplata);;
  
let (wplac, wyplac) = konto 0;;
  
wplac 50;;
wyplac 8;;
      

Co by się stało gdyby definicja konto nie miała argumentusaldo, lecz zaczynała się tak:

let konto = 
  let saldo = ref 0
  in ...
     

Cena programowania imperatywnego

Konstrukcje imperatywne mają swoją cenę. To programowanie imperatywne wymusza np. wprowadzenie środowiskowego modelu obliczeń w takiej postaci, w jakiej został wcześniej przedstawiony. Ale na tym nie koniec.

Konstrukcje imperatywne powodują kłopoty z pojęciem tożsamości. Kiedy $x$ i $y$ to to samo? Czy wtedy, kiedy wartość $x$ i $y$ jest taka sama? Ale przecież wartości obiektów mogą się zmieniać. To może wtedy, gdy każda zmiana wartości $x$ powoduje analogiczną zmianę $y$? To nie są łatwe pytania.

Musimy wypracować jakiś język do opisu tożsamości obiektów obliczeniowych. Będziemy mówić, że:

• (w danej chwili) $x$ i $y$ są równe, jeżeli ich wartości są równe, sprawdza to predykat =,
• obiekty $x$ i $y$ są tożsame, jeżeli są sobie równe i zmiana wartości jednego powoduje analogiczną zmianę drugiego; tożsamość sprowadza się do tego, że oba obiekty znajdują się w tym samym miejscu w pamięci, sprawdza to predykat ==,
• obiekty $x$ i $y$ są niezależne, jeżeli zmiana stanu jednego z nich nie powoduje żadnej zmiany stanu drugiego z nich.

Cena imperatywności obejmuje też weryfikację programów imperatywnych i ich pielęgnację. Analiza programów imperatywnych jest bardzo trudna, ze względu na konieczność śledzenia zależności wynikających z kolejności wykonywania instrukcji --- "czy ta instrukcja powinna być najpierw, czy tamta?" Ponadto, modyfikowanie programów imperatywnych, dodawanie nowych instrukcji, zmiana kolejności instrukcji, jest źródłem wielu błędów w programach, gdyż łatwo przeoczyć niektóre z zależności. Błędy te nie występują w programach funkcyjnych.

Cena ta rośnie jeszcze bardziej jeżeli dopuścimy współbieżnewykonanie kilku procedur operujących na tych samych obiektach. Wówczas bardzo trudno jest przewidzieć wszystkie możliwe scenariusze ich wykonania i przewidzieć wszystkie możliwe przeploty modyfikacji stanów obiektów. Przekonacie się o tym sami na programowaniu współbieżnym,che che ...

Funkcyjnie, czy imperatywnie?

Kiedy programować funkcyjnie, a kiedy imperatywnie? To że programowanie imperatywne ma swoją cenę nie oznacza, że wszystko i zawsze należy programować funkcyjnie. Tak jak dobry mechanik powinien znać wszystkie narzędzia i stosować je zgodnie z przeznaczeniem, tak samo dobry programista powinien znać wszystkie techniki programistyczne i paradygmaty programowania i wybierać te, które najlepiej nadają się do rozwiązania danego zadania. Nie wbijamy gwoździ kluczem francuskim i nie dokręcamy cieknącego kranu młotkiem!

Niektóre algorytmy (np. dynamiczne) dużo łatwiej jest zapisać z użyciem imperatywnych struktur danych, np. tablic. Nie przeszkadza to jednak takiemu ich zdefiniowaniu, aby cała imperatywność była ukryta przed użytkownikiem, stanowiła sekret implementacji.

Podobnie jest z techniką spamiętywania. Elegancka implementacja spamiętywania wymaga użycia przypisania. Poniżej przedstawiono kolejny przykład mechanizmu, który można zaimplementować elegancko tylko wtedy, gdy jego serce będzie imperatywne.

Niektóre z kolei algorytmy łatwiej jest zapisać funkcyjnie. Dotyczy to zwłaszcza algorytmów operujących na procedurach wyższego rzędu, wszelkiego rodzaju drzewach i algorytmów rekurencyjnych. W takich przypadkach należy stosować programowanie funkcyjne.

Przykład: metoda Monte Carlo

Metoda Monte Carlo jest to metoda przybliżania pewnych wartości. Polega ona na wielokrotnym losowaniu danych z pewnego zbioru i sprawdzaniu, czy dane te mają określoną własność. W ten sposób przybliżamy prawdopodobieństwo, z jakim dane ze zbioru mają daną własność. Na podstawie przybliżonego prawdopodobieństwa można, z kolei, przybliżyć szukaną wartość.

Oryginalnie metoda Monte Carlo powstała jako metoda przybliżania całek oznaczonych funkcji. Badana funkcja na zadanym przedziale musi przyjmować wartości z określonego przedziału. Losujemy punkty na płaszczyźnie, należące do danego przedziału $x$ i $y$, i badamy z jakim prawdopodobieństwem $y\le f(x)$. Prawdopodobieństwo tego zdarzenia jest równe stosunkowi powierzchni badanego fragmentu płaszczyzny leżącego poniżej $f(x)$, do powierzchni całego fragmentu powierzchni.

Spróbujemy zaimplementować metodę Monte Carlo zgodnie z poznanymi zasadami, top-down, rozbijając problemy na podproblemy, stosując bariery abstrakcji, wybierając między programowaniem funkcyjnym i imperatywnym.

Parametry metody to: generator danych, sprawdzana własność i liczba prób. Wynikiem jest przybliżenie prawdopodobieństwa, z jakim dane mają własność.

let montecarlo dane wlasnosc liczba_prob = 
  let rec montecarlo_rec a n = 
    if n = 0 then 
      a
    else
      if wlasnosc (dane ()) then 
        montecarlo_rec (a+1) (n-1)
      else
        montecarlo_rec a (n-1)
  in
    float (montecarlo_rec 0 liczba_prob) /. float (liczba_prob);;
      

Spróbujmy za pomocą metody Monte Carlo przybliżyć wartość $\pi$. Liczba ta jest równa powierzchni koła jednostkowego.

let square x = x *. x;;
let kolo (x, y) = square x +. square y <= 1.0;;
let kwadrat () = (losowa_od_do (-1.0) 1.0, losowa_od_do (-1.0) 1.0);;
let pi = 4.0 *. (montecarlo kwadrat kolo 1000);;
      

Pozostał do zaprogramowania generator liczb losowych.

let losowa_od_do od doo = losowa () *. (doo -. od) +. od;;
  
let losowa () = 
  let duzo = 1000
  in
    let l = float (losowy_int () mod (duzo + 1)) /. float (duzo)
    in 
      if l < 0.0 then (-. l) else l;;
  
let losowy_int = 
  let stan = ref 0
  and a = 937126433
  and b = 937187
  in function () -> 
    (
      stan := !stan * b + a;
      !stan
    );;
     

W tym przykładzie użyliśmy niewiele imperatywności, ale miała ona duży wpływ na strukturę programu. W przeciwnym przypadku musielibyśmy przekazywać stan generatora liczb losowych i to w wielu procedurach, przekraczając granice abstrakcji chroniące generator liczb losowych.

Laboratoria i ćwiczenia

Laboratoria i ćwiczenia do wykładu