Programowanie funkcyjne/Techniki uleniwiania i spamiętywania

Uleniwianie i odroczone wartości

Ocaml, jak większość popularnych języków programowania, charakteryzuje się gorliwym obliczaniem wartości. Oznacza to, że argumenty procedur są obliczane przed rozpoczęciem obliczania procedury, bez względu na to, czy są one faktycznie potrzebne, czy nie. Uleniwianie polega na odroczeniu momentu obliczenia wartości. W szczególności, jeśli taka odroczona wartość nie jest używana, to nie jest obliczana.

W momencie, gdy rozpoczyna się obliczenie treści procedury, zamiast wartości argumentu mamy "obietnicę jej obliczenia". Jest to procedura, której wynikiem 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. Taką procedurę nazywamy wartością odroczoną lub uleniwioną.

Potrzebujemy dwóch mechanizmów: "uleniwiacza" i "poganiacza". "Uleniwiacz" powinien przekształcać dane wyrażenie w odroczoną wartość, czyli "obietnicę" obliczenia wartości wyrażenia. "Poganiacz" natomiast powinien zmuszać odroczoną wartość do obliczenia konkretnej swojej wartości. 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 ();;

Przykład [Uleniwianie]

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ść odroczona 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 wykonywania tych samych obliczeń. Technikę tę przedstawiamy poniżej.

Obiekty i stany

Jeżeli chcemy, aby odroczone wyrażenie mogło zapamiętywać swoją wartość przy pierwszym jej obliczeniu, to taka odroczona 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      

Pokazana konstrukcja jest formą enkapsulacji, podobną do tej jaką oferuje programowanie obiektowe. Jednak zwykle obiekty w programowaniu obiektowym oferują więcej niż jedną metodę dostępu. Poniższy przykład ilustruje jak tworzyć obiekty obliczeniowe, do których ma dostęp więcej niż jedna procedura.

Uwaga

Prezentowanej tu techniki programowania nie należy mylić z programowaniem obiektowym. Ocaml zawiera również konstrukcje programowania obiektowego. Nie należy to jednak do zakresu tego kursu.

Przykład [Konto bankowe]

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

Uleniwianie ze spamiętywaniem

Chcąc dodać do uleniwiania spamiętywanie, tak aby odroczona wartość była obliczana co najwyżej raz, musimy z uleniwionej wartości uczynić obiekt obliczeniowy. Do takiego obiektu powinna mieć dostęp tylko jedna procedura, wymuszająca obliczenie wartości lub odtworzenie zapamiętanej wartości. Należy zwrócić uwagę na to, że obliczenie odroczonego wyrażenia może zakończyć się podniesieniem wyjątku. W takim przypadku każde wydobycie z odroczonego wyrażenia jego wartości będzie powodować podniesienie wyjątku.

type 'a delayed = unit -> 'a;;
type 'a delayed = unit -> 'a;;

type 'a value = NoValue | Exception of exn | Value of 'a;;
type 'a value = NoValue | Exception of exn | Value of 'a

let memoize f =
  let
    v = ref NoValue
  in
    function () ->
      match !v with
        Value y -> y |
        Exception e -> raise e |
        NoValue ->
          let
            y = try f ()
              with e -> begin
                v := Exception e;
                raise e
              end
          in
            v := Value y;
            y;;
val memoize : (unit -> 'a) -> unit -> 'a = <fun>
 
lazy w   $\equiv$   memoize (fun () -> w)
 
let force x = x ();;
val force : (unit -> 'a) -> 'a = <fun>

Uleniwianie ze spamiętywaniem jest zaimplementowane w module Lazy.

Przykład [Uleniwianie ze spamiętywaniem]

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;;
- : int = 42

Zastosowania techniki spamiętywania

Technika spamiętywania jest dosyć uniwersalna. Ma ona szersze zastosowanie, niż tylko odraczanie obliczeń. Przy jej użyciu możemy zrealizować algorytmy dynamiczne, zachowując rekurencyjną formę procedur.

Rozwiązując problem rekurencyjnie tworzymy zwykle procedurę rekurencyjną, której każde wywołanie rozwiązuje jedną instancję (pod-)problemu. Naszym celem jest wyeliminowanie wielokrotnego obliczania wyników dla tych samych instancji podproblemów. Przy każdym wywołaniu rekurencyjnym procedury rozwiązującej problem, sprawdzamy, czy już nie miało miejsca wywołanie dla takich samych wartości argumentów. Jeżeli tak, to pobieramy obliczony wcześniej wynik. Jeżeli nie, to przeprowadzamy obliczenia, a wynik przed przekazaniem zapamiętujemy.

Możemy zaimplementować rodzaj "otoczki", która filtruje wywołania procedur i zapewnia spamiętywanie. Do spamiętywania wyników będziemy używać słownikowej struktury danych zwanej mapą (por. moduł Map). Udostępnia ona następujące operacje:

• empty -- pusty słownik,
• mem k m -- predykat sprawdzający czy w słowniku m jest element o kluczu k,
• find k m -- zwraca wartość związaną w mapie m z kluczem k,
• add k v m -- zwraca słownik powstały przez wstawienie do m wartości v związanej z kluczem k.

Rozważmy najpierw prosty przykład, procedurę obliczającą liczby Fibonacciego:

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

Chcielibyśmy zachować ten zwięzły i prosty zapis, a jednocześnie polepszyć złożoność do liniowej, charakterystycznej dla rozwiązania dynamicznego. Użyjemy procedury memoize dodającej do procedury będącej jej argumentemmechanizm spamiętywania. Z przyczyn technicznych, procedura będąca argumentem memoize musi być procedurą jednoargumentową. (Jest to szczegół techniczny, gdyż ten jedyny argument może być $n$-tką.)

let memoize f = 
  let tab = ref empty
  in function x -> 
    if mem x !tab then 
      find x !tab 
    else
      let wynik = f x 
      in begin
        tab := add x wynik !tab;
        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)
  );;