Programowanie funkcyjne/Programowanie imperatywne

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ą zmiannych 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|]

Pętle

...

Reference i polimorfizm

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:

• 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 ...
     

Technika spamiętywania

[UWAGA: Uniwersalny spamiętywacz wymaga odwołania się do operatora punktu stałego. PRZEROBIĆ! ....]

Schemat spamiętywania jest dosyć uniwersalny: W implementacji rekurencyjnej, ilekroć chcemy wywołać rekurencyjnie procedurę rozwiązującą podproblem, sprawdzamy, czy już takie wywołanie nie miało miejsca, a jeżeli tak, to pobieramy obliczony wcześniej wynik. Możemy zaimplementować coś w rodzaju "otoczki", która filtruje wywołania procedur.

Rozważmy najpierw prosty przypadek, procedurę obliczającą liczby Fibonacciego.

let rec fib n = 
  if n <= 1 then 
    n 
  else 
    fib (n-1) + fib (n-2);;
      

Procedura memoize dodaje do procedury będącej jej argumentemmechanizm spamiętywania.

let memoize f = 
  let tab = ref empty_map
  in function x -> 
    if dom !tab x then 
      apply !tab x 
    else
      let wynik = f x 
      in begin
        tab := update !tab x wynik;
        wynik
      end;;
      

Chcąc dodać spamiętywanie do rekurencyjnej definicji procedury fib piszemy:

let rec fib = 
  memoize (function n -> 
    if n <= 1 then 
      n 
    else 
      fib (n-1) + fib (n-2)
  );;
         

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