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