Programowanie funkcyjne/Techniki uleniwiania i spamiętywania

Uleniwianie

Ocaml, jak większość popularnych języków programowania, charakteryzuje się zachłannym obliczaniem wartości --- argumenty procedur są obliczane przed rozpoczęciem obliczania procedury, bez względu na to, czy są one faktycznie potrzebne, czy nie. Uleniwianie polega na zabezpieczeniu wartości przed ich obliczeniem, jeżeli to nie jest konieczne.

W momencie, gdy rozpoczyna się obliczenie treści procedury, zamiast wartości argumentu mamy "obietnicę jej obliczenia". Jest to procedura, której wartością jest dana wartość. Procedura taka ma jeden argument typu unit. Tak więc argument ten nie niesie żadnej informacji, a jego podanie i wywołanie procedury jedynie wyzwala obliczenie wartości.

Potrzebujemy dwóch mechanizmów: "uleniwiacza" i "poganiacza". "Uleniwiacz" powinien przekształcać dane wyrażenie w jego uleniwioną wartość, czyli "obietnicę" obliczenia wartości wyrażenia. "Poganiacz" natomiast powinien zmuszać "obietnicę" obliczenia wartości do jej spełnienia. Zauważmy przy tym, że uleniwiacz nie może być procedurą, gdyż wykorzystuje on nie wartość wyrażenia, ale jego treść. Musi to więc być forma specjalna. Można ją zrealizować jako prostą makrodefinicję. Oto prosta definicja uleniwiania:

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

let a = lazy 54;;
val a : unit -> int = <fun>

force a;;
- : int = 54

let x = lazy (
  let a = 6 
  and b = 9
  in begin
    print_int a;
    print_string " * ";
    print_int b;
    print_string " = ";
    a * b / 13 * 10 + a * b mod 13
  end
);;
val x : unit -> int = <fun>

force x;;
6 * 9 = - : int = 42

force x;;
6 * 9 = - : int = 42

Zauważmy, że jeżeli wartość uleniwiona nie jest nam potrzebna, to nie jest obliczana, ale jeżeli jest potrzebna kilkukrotnie, to jest również kilkukrotnie obliczana. Dlatego też uleniwianiu zwykle towarzyszy spamiętywanie. Spamiętywanie pozwala na zapamiętanie wartości przy pierwszym jej obliczeniu i uniknięcie wielokrotnego obliczania. Technikę tę przedstawiamy poniżej. Uleniwianie ze spamiętywaniem jest zaimplementowane w module Lazy.

Obiekty i stany

Jeżeli chcemy, aby uleniwione wyrażenie mogło zapamiętywać swoją wartość przy pierwszym jej obliczeniu, to taka uleniwiona wartość musi zawierać szczyptę imperatywności. Musi posiadać stan, który może zmieniać się w czasie. Zanim pokażemy technikę spamiętywania, pokażemy jak można tworzyć obiekty obliczeniowe obdarzone stanem, który może się zmieniać w czasie.

Nośnikiem stanu obiektów mogą być np. referencje. Jeśli jednak nie chcemy, aby były one ogólnodostępne, to muszą być widoczne tylko lokalnie, wewnątrz obiektów obliczeniowych. Widzieliśmy to już przykład takiego obiektu, był to generator liczb losowych użyty w metodzie Monte Carlo. Obiekt obliczeniowy może być procedurą, wraz z wartościami lokalnymi widocznymi tylko dla niej. Oto przykład generatora takich obiektów:

let generator s = 
  let r = ref s 
  in
    fun x -> begin
      r := !r + x;
      !r
    end;;
val generator : int -> int -> int = <fun>

Zauważmy, że każde wywołanie procedury generator wiąże się z powstaniem osobnej ramki zawierającej referencję do wartości argumentu s. Wynikiem każdego takiego wywołania jest procedura, która może zmieniać wartość zapamiętaną jako ref s. Za razem jest to jedyna procedura, która ma dostęp do tej referencji.

let o = generator 0;;
val o : int -> int = <fun>

o 22;;
- : int = 22

o 20;;
- : int = 42      

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