Programowanie funkcyjne/Programowanie imperatywne

From Studia Informatyczne

Spis treści

Wstęp

Paradygmat programowania imperatywnego opiera się na następującej analogii: Zwykle program 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ą zmiennych lub obiektów obliczeniowych, które też mogą zmieniać stany. W ten sposób upływ czasu w świecie rzeczywistym jest modelowany przez upływ czasu w programie.

Programowanie obiektowe możemy traktować jak rozwinięcie paradygmatu programowania obiektowego. W programowaniu imperatywnym podstawową operacją zmieniającą stan zmiennej jest przypisanie. W programowaniu obiektowym mamy lepiej określony zestaw metod mogących zmieniać stan obiektu. Dodatkowo hierarchia klas odzwierciedla podobieństwa między różnymi rodzajami obiektów.

Istotą programowania imperatywnego są zmienne i instrukcja przypisania. Można powiedzieć, że obliczenia imperatywne sprowadzają się do wykonania określonej sekwencji przypisań. Dlatego też w imperatywnych językach programowania mamy również rozmaite konstrukcje językowe, sterujące kolejnością wykonywanych instrukcji: sekwencyjne złożenie instrukcji, pętle, instrukcje wyboru.

Referencje

Odpowiednikiem zmiennych w funkcyjnych językach programowania są referencje. Referencja to wskaźnik do wartości, ale taki, który może ulegać zmianie. Referencja odpowiada L-wartości (tj. adresowi zmiennej) w programach imperatywnych.

Referencje tworzymy podając początkową wartość referencji i dodając słowo kluczowe ref. Każde użycie ref tworzy nową referencję.

<wyrażenie> ::= ref <wyrażenie>

Zmienne mogą występować w programach imperatwnych w dwóch różnych kontekstach, jako tzw. L-wartości i R-wartości. Odpowiada to ich występowaniu po lewej i prawej stronie przypisania. W przypadku L-wartości istotny jest adres zmiennej. W przypadku R-wartości istotna jest wartość zmiennej.

Używając referencji explicite zaznaczamy, czy chodzi nam o referencję, czy o jej wartość. Do wyłuskiwania z referencji jej wartości służy operator unarny !. Wartość, na którą wskazuje referencja, możemy zmienić za pomocą przypisania. Przypisanie zapisujemy tradycyjnie, za pomocą infiksowego operatora binarnego :=. Wynikiem przypisania, jako wyrażenia, jest () (unit).


Przykład [Użycie referencji]

let r = ref 6;;
val r : int ref = {contents = 6}

!r + 4;;
- : int = 10

r := !r * (!r + 1);;
- : unit = ()

!r;;
- : int = 42


Bloki instrukcji

Wraz z imperatywnością pojawia się potrzeba wykonywania sekwencji instrukcji. Wartością, jako wyrażenia, instrukcji imperatywnych takich jak przypisanie, w przypadku których istotne są jedynie ich efekty uboczne, jest () (unit). Istotny jest więc sam fakt ich obliczenia/wykonania. Instrukcje takie możemy łączyć w sekwencje za pomocą średników. Średnik jest infiksowym operatorem binarnym, który oblicza wartości obu swoich argumentów, ale wynikiem jest wartość tylko drugiego z nich. Pierwszy z argumentów powinien być typu unit (ale nie jest to wymóg kategoryczny). Jak łatwo zauważyć, średnik jest łączny.

let r = ref 3;;
val r : int ref = {contents = 3}

r := !r * !r; r := 4 * !r  + 6; !r;;
- : int = 42

Czasami chcemy określić, że pewien ciąg instrukcji powinien być traktowany tak, jak jedna instrukcja (blok instrukcji). Formalnie wystarczy, że taki ciąg instrukcji ujmiemy w zwykłe nawiasy. Wszak instrukcja czy ciąg instrukcji jest wyrażeniem. Jednak w przypadku dłuższych sekwencji kodu może to być nieczytelne. Dlatego też, możemy również ująć blok instrukcji w nawiasy begin-end. Formalnie, słowa kluczowe begin-end tworzą po prostu parę nawiasów. Dobry styl wymaga jednak, aby zwykłych nawiasów używać do wyrażeń niosących wartość, a begin-end do instrukcji imperatywnych.

let x = 7 
in begin
  r := !r / x; 
  r := !r - x
end;
!r;;
- : int = -1


Modyfikowalne pola rekordów

W Ocamlu referencje nie są pierwotnym mechanizmem imperatywnym. W rzeczywistości są one zaimplementowane za pomocą innego mechznizmu imperatywnego -- modyfikowalnych pól rekordów. Definiując typ rekordowy możemy zadeklarować, że określone pola rekordów bedą modyfikowalne. Robimy to, dodając słowo kluczowe mutable przed deklaracją danego pola. Oczywiście można część pól rekordu zadeklarować jako modyfikowalne, a część nie. Wartości modyfikowalnych pól rekordów możemy zmieniać za pomocą infiksowego operatora binarnego <-. Wynikiem tego operatora, jako wyrażenia, jest () (unit).

<typ>       ::= { [ mutable ] <identyfikator> : <typ> { ; [ mutable ] <identyfikator> : <typ> }* }
<wyrażenie> ::= <wyrażenie> . <identyfikator> <- <wyrażenie>


Przykład [Modyfikowalne pola rekordów]

type ulamek = { mutable licznik : int; mutable mianownik : int };; 
type ulamek = { mutable licznik : int; mutable mianownik : int; }

let uprosc u = 
  let d = nwd u.licznik u.mianownik
  in begin
    u.licznik <- u.licznik / d;
    u.mianownik <- u.mianownik / d
  end;;
val uprosc : ulamek -> unit = <fun>

let u = {licznik = 6; mianownik = 9};;
val u : ulamek = {licznik = 6; mianownik = 9}
 
uprosc u;;
- : unit = ()

u;;
- : ulamek = {licznik = 2; mianownik = 3}


Tablice

Inną bardzo użyteczną imperatywną strukturą danych są tablice. Tablice są indeksowane liczbami całkowitymi, począwszy od 0. Formalnie tablice są jednowymiarowe. Tablice o większej liczbie wymiarów są realizowane jako tablice tablic ... Rozmiar tablicy, tak jak rozmiar listy, nie wynika z jej typu, lecz jest dynamiczną cechą tablicy.

Operacje na tablicach są zaimplementowane w modul Array. Oto kilka podstawowych operacji na tablicach:

  • Nieduże tablice możemy tworzyć używając konstruktora [| ... |]. Działa on podobnie jak [ ... ] dla list. Wewnątrz nawiasów należy wymienić kolejne elementy tworzące tablicę, pooddzielane średnikami.
  • Do tworzenia większych tablic wygodniejsza jest procedura Array.make : int -> 'a -> 'a array. Jej pierwszym argumentem jest rozmiar tablicy, a drugim wartość użyta do zainicjowania elementów tablicy.
  • Procedura Array.length : 'a array -> int zwraca rozmiar tablicy. Elementy tablicy są indeksowane liczbami od 0 do rozmiar minus 1.
  • Wartości elementów tablicy możemy wydobywać z niej za pomocą procedury Array.get : 'a array -> int -> 'a. Pierwszy argument to tablica, a drugi to indeks elementu. Zamiast pisać Array.get a i możemy użyć skróconej notacji i napisać a.(i).
  • Do modyfikowania elementów tablicy służy procedura Array.set : 'a array -> int -> 'a -> unit. Pierwszy argument to tablica, drugi to indeks elementu, a trzeci to jego nowa wartość. Zamiast pisać Array.set a i x możemy użyć skróconej notacji i napisać a.(i) <- x.

Przykład [Tablice]

let a = [|1;4;3;2;5;6|];;
val a : int array = [|1; 4; 3; 2; 5; 6|]

let tmp = a.(1) 
in begin
  a.(1) <- a.(3); 
  a.(3) <- tmp
end;
a;;
- : int array = [|1; 2; 3; 4; 5; 6|]

Instrukcje warunkowe i wyboru

Instrukcje warunkowe if-then-else i instrukcje wyboru match-with mogą być również używane wobec instrukcji imperatywnych. Wystarczy pamiętać, że instrukcje imperatywne są wyrażeniami typu unit. Dla instrukcji warunkowej if-then-else istnieje również jej wersja skrócona, bez członu else. Wyrażenie postaci if w then i jest równoważne if w then i else ().

Przykład [Instrukcje warunkowe i imperatywne]

let abs r = 
  if !r < 0 then r := -(!r);;
val abs : int ref -> unit = <fun>

let x = ref (-4);;
val x : int ref = {contents = -4}

abs x;;
- : unit = ()

!x;;
- : int = 4

Pętle

Mamy dwa rodzaje pętli, znanych również z innych języków programowania: while i for.

<wyrażenie> ::= while <wyrażenie> do <wyrażenie> done  |
                for <identyfikator> = <wyrażenie> { to | downto } <wyrażenie> do <wyrażenie> done

Wyrażenie stojące po słowie kluczowym while to dozór pętli. Musi on być typu bool. Drugie wyrażenie, stojące między do i done to treść pętli while. Powinna ona być typu unit. Obliczenie pętli while polega na sprawdzaniu czy dozór jest spełniony (równy true) i jeżeli tak jest, na obliczaniu treści pętli -- tak długo, aż dozór przestanie być spełniony.

Treść pętli for to wyrażenie stojące między do i done. Powinna ona być typu unit. Identyfikator stojący po słowie kluczowym for to stała indeksująca pętlę for. Stała ta przebiega przedział liczb całkowitych, którego krańce wyznaczają wartości wyrażeń przed i po to/downto. Wartość stojąca przed słowem kluczowym to lub downto to wartość początkowa, a wartość stojąca po słowie kluczowym to lub downto to wartość końcowa. Obliczenie pętli polega na wielokrotnym obliczaniu treści pętli w środowisku przypisującym zmiennej indeksującej kolejne wartości. Jeżeli użyto słowa kluczowego to, to z każdym kolejnym krokiem pętli wartość stałej indeksującej rośnie o 1. (Jeżeli wartość końcowa jest mniejsza od początkowej, to nie jest wykonywany ani jeden krok pętli.) Jeżeli natomiast użyto słowa kluczowego downto, to z każdym kolejnym krokiem pętli wartość stałej indeksującej maleje o 1. (W tym przypadku, jeżeli wartość końcowa jest większa od początkowej, to nie jest wykonywany ani jeden krok pętli.)

Przykład [Pętla while]

let nwd a b = 
  let x = ref a 
  and y = ref b
  in begin
    while !x <> !y do 
      if !x > !y then 
        x := !x - !y
      else
        y := !y - !x
    done;
    !x
  end;;
val nwd : int -> int -> int = <fun>

nwd 24 42;;
- : int = 6

Przykład [Pętla for]

let silnia n = 
  let r = ref 1
  in begin 
    for i = 2 to n do 
      r := !r * i
    done;
    !r
  end;;
val silnia : int -> int = <fun>

silnia 7 / silnia 5;;
- : int = 42

Asercje

Asercje to mechanizm częściowego sprawdzania poprawności programów. Asercja jest wstawką w kodzie zawierającą warunek logiczny. Ilekroć sterowanie osiąga asercję, sprawdzane jest, czy podany warunek logiczny jest prawdziwy. Jeżeli nie, to zgłaszany jest błąd.

 <wyrażenie> ::= assert <wyrażenie>

Asercje należy tworzyć wraz z programem. Zdecydowanie ułatwiają one wykrywanie błędów w programach, gdyż pozwalają wykrywać je na dużo wcześniejszym etapie. Oczywiście sprawdzanie asercji zajmuje czas, jednak nie należy się tym przejmować, gdyż gdy program jest gotowy, to możemy je wyłączyć jedną opcją kompilatora (-noassert).

Przykład [Asercje]

let abs x = 
  let w = if x < 0 then -x else x
  in 
    assert (w > 0);
    w;;
val abs : int -> int = <fun>

abs (-4);;
- : int = 4

abs 0;;
Exception: Assert_failure ...

Instrukcje wejścia/wyjścia

Do instrukcji imperatywnych zaliczają się również instrukcje wejścia/wyjścia. Ocaml udostępnia kilka mechanizmów wejścia/wyjścia. Tutaj przedstawiamy najprostszy z nich. Czytelników zainteresowanych innymi mechanizmami odsyłamy np. do dokumentacji modułów Printf i Scanf.

Do wypisywania rozmaitych wartości służy zestaw procedur, których nazwy mają postać print_.... Każda z nich ma jeden argument odpowiedniego typu i wypisuje (na standardowym wyjściu) jego wartość. Są to:

  • print_int: int -> unit -- wypisuje daną liczbę całkowitą,
  • print_float: float -> unit -- wypisuje daną liczbę zmiennopozycyjną,
  • print_string: string -> unit -- wypisuje dany napis,
  • print_char: char -> unit -- wypisuje dany znak,
  • print_newline: unit -> unit -- wypisuje znak przejścia do nowego wiersza (a także wszystko co czekało na wypisanie w buforze we./wy.),
  • print_endline: string -> unit -- wypisuje dany napis oraz znak przejścia do nowego wiersza (a także wszystko co czekało na wypisanie w buforze we./wy.).
Dostępny jest też zestaw procedur wczytujących wartości określonych typów ze standardowego wejścia. Są to:
  • read_int: unit -> int -- wczytuje jeden wiersz z wejścia i interpretuje go jako liczbę całkowitą,
  • read_float: unit -> float -- wczytuje jeden wiersz z wejścia i interpretuje go jako liczbę zmiennopozycyjną,
  • read_line: unit -> string -- wczytuje jeden wiersz z wejścia i przekazuje go jako wynik.
Zwróćmy uwagę, że procedury wczytujące mają argument typu unit. Choć nie niesie on żadnej informacji, to przekazanie go jest konieczne, aby każde wywołanie procedury było niezależnie obliczane. W programach imperatywnych często można spotkać takie procedury.

Przykład [Wejście/wyjście]

let cat () = 
  let s = ref " "
  in
    while !s <> "" do
      s := read_line();
      print_endline !s
    done;;
val cat : unit -> unit = <fun>

Referencje i polimorfizm

Używanie referencji do wartości polimorficznych może sprawiać kłopoty, zwłaszcza jeśli korzystamy z kompilatora w sposób inkrementacyjny. Należy pamiętać, że referencja wskazuje na wartość przynajmniej tak ogólną jak typ referencji. Wyłuskując wskazywaną wartość polimorficzną musimy mieć gwarancję, że możemy ją zastosować do każdego typu wynikającego z typu referencji. Wynika stąd, że przypisując wartość możemy podać wartość bardziej ogólną, niż to wynika z typu referencji. Jeżeli korzystamy z kompilatora w sposób inkrementacyjny i przypiszemy referencji wartość konkretniejszą, to możemy zauważyć, że typ referencji ulegnie ukonkretnieniu!

Wynika to stąd, że kompilator, żeby poprawnie określić typ referencji, musi widzieć wszystkie jej użycia. Natomiast w trybie inkrementacyjnym nie jest to możliwe. Aktualny typ referencji odzwierciedla to, co wiadomo na podstawie do tej pory skompilowanego kodu.

Wspominamy o tym, gdyż nie jest to intuicyjne i może na początku sprawiać kłopoty.

Przykład [Referencje i polimorfizm]

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;;
val r : (int -> '_a -> int) ref = {contents = <fun>}

r := f;;
- : unit = ()

r;;
- : (int -> '_a -> int) ref = {contents = <fun>}

r := h;; 
- : unit = ()

r;;
- : (int -> int -> int) ref = {contents = <fun>}

r := i;;
This expression has type int -> bool -> int but is here used with type int -> int -> int

Cena programowania imperatywnego

Konstrukcje imperatywne mają swoją cenę. 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? A może wtedy, gdy zajmują ten sam obszar pamięci (ale wtedy model obliczeń musi być na tyle szczegółowy, żeby oddawał to gdzie co jest pamiętane --- i taki właśńie jest)? 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 równość (=,)
  • 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 tzw. równość tożsamościowa (==),
  • obiektyx i y są niezależne, jeżeli zmiana stanu jednego z nich nie powoduje żadnej zmiany stanu drugiego z nich.
Należy pamiętać, że obiekty mogą być zależne, ale nie tożsame, np. gdy stojące za nimi struktury danych mają część wspólną.

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żne wykonanie 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 Państwo sami w trakcie kursu z programowania współbieżnego i rozproszonego.

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 i stanowiła sekret implementacji.

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 lepiej stosować programowanie funkcyjne.

Nie jest to jednak wybór albo-albo. Często można łączyć oba paradygmaty wykorzystując ich mocne strony, a unikając wad (czyżby istniał francuski młotek?). Jest tak np. z techniką spamiętywania. Elegancka implementacja spamiętywania wymaga użycia przypisania, natomiast towarzyszy ona procedurom rekurencyjnym. Poniżej przedstawiono inny przykład mechanizmu, który można zaimplementować elegancko tylko wtedy, gdy jego serce będzie imperatywne.


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 wykresu f(x) do powierzchni całego fragmentu powierzchni.

Spróbujemy zaimplementować metodę Monte Carlo w stylu top-down, rozbijając problemy na podproblemy i 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ą testowaną 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. Losową liczbę z danego zakresu możemy uzyskać na podstawie losowej liczby z przedziału [0,1], a tę z kolei na podstawie losowej liczby typu int.

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;;

Natomiast generator losowych liczb całkowitych zaimplementujemy korzystając z imperatywności.

let losowy_int = 
  let stan = ref 0
  and a = 937126433
  and b = 937187
  in function () -> 
    begin
      stan := !stan * b + a;
      !stan
    end;;

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

Ćwiczenia

Ćwiczenia