Programowanie funkcyjne/Techniki uleniwiania i spamiętywania

Uleniwianie

[Uwaga: Ta sekcja musi być przed procedurami dużo wyższych rzędów, bo jest potrzebna do zaimplementowania leniwego if-a]

Model obliczeniowy Ocamla charakteryzuje się zachłannym obliczaniem wartości --- argumenty funkcji są obliczane bez względu na to, czy są potrzebne. Uleniwianie polega na zabezpieczeniu wartości przed obliczeniem, jeżeli nie jest to potrzebne. Zamiast wartości mamy "obietnicę jej obliczenia", czyli procedurę bezargumentową, której wartością jest dana wartość. W momencie gdy wartość jest nam potrzebna, obliczamy ją. Żeby nie obliczać tej wartości wielokrotnie, stosujemy spamiętywanie. W Ocamlu dostępna jest forma specjalna lazy i procedura force. Lazy powoduje odroczenie (ze spamiętywaniem) obliczenia wyrażenia. Chcąc obliczyć wartość wykonujemy na wyniku lazy operację force. Na potrzeby tego wykładu zaimplementujemy uproszczoną wersję uleniwiania, bez spamiętywania. Do zaimplementowania spamiętywania potrzebowalibyśmy operacji imperatywnych, o których nie było jeszcze mowy.

type 'a delayed = unit -> 'a;;
lazy w ≡ function () -> w
let force x = x ();;
let a = delay 4;;
force a;;

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: Ta sekcja musi być przed strumieniami, bo tam jest używane spamiętywanie.]

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