Programowanie funkcyjne/Techniki uleniwiania i spamiętywania

From Studia Informatyczne

Spis treści

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 argumentem, mechanizm 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 tab f 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, możemy napisać:

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

Ten trochę skomplikowany zapis wynika z dwóch powodów:

  • Ocaml wymaga, aby definicja procedury rekurencyjnej miała w nagłówku argumenty lub zaczynała się od \lambda-abstrakcji,
  • każe wywołanie memoize powinno korzystać z tej samej mapy.

Kontynuacje

Technika uleniwiania (bez spamiętywania) jest stosowana do zaimplementowania kontynuacji. Intuicyjnie, kontynuacja, to obliczenia, które należy wykonać (po aktualnie rozpatrywanym fragmencie programu), w celu uzyskania wyniku. Kontynuacje są stosowane przy definiowaniu semantyki denotacyjnej jezyków programowania, gdzie pozwalają na denotacyjny opis semantyki skoków. Pokażemy, jak za pomocą kontynuacji można uzyskać efekt równoważny skokom oraz jak każdą rekurencję można zamienić na rekurencję ogonową. Zacznijmy od prostego przykładu ilustrującego czym jest kontynuacja.

Przykład [Przerwanie iteracji]

Powiedzmy, że chcemy obliczyć iloczyn listy liczb całkowitych. Powiedzmy, że dodatkowo chcemy użyc do tego procedury fold_left lub fold_right. W pierwszym podejściu możemy zrobić to tak:

let iloczyn l = fold_left ( * ) 1 l;;
val iloczyn : int list -> int = <fun>

Jeżeli w ciągu tym napotkamy 0, to dalsze obliczenia możemy przerwać. Jak jednak wyskoczyć z iteracji realizowanej przez fold? Zamiast wyznaczać bezpośrednio iloczyn, możemy wyznaczać kontynuacje, które na podstawie iloczynu początkowego fragmentu listy l obliczają iloczyn całej listy. Inaczej mówiąc, każda taka kontynuacja przekształca liczbę x w iloczyn x oraz pewnego końcowego fragmentu l. Kontynucają dla pustego fragmentu listy jest funkcja identycznościowa. Mając kontynuację dla całej listy, wystarczy, że podamy jej jako parametr 1, a uzyskamy wynik. Konstruując kontynuacje, jeżeli napotkamy 0, to wiemy, że wynikiem jest 0, bez względu na to, co dalej występuje na liście.

let iloczyn l = 
  fold_right 
    (fun x cont -> if x = 0 then (fun a -> 0) else (fun a -> cont (a * x)))
    l id 1;;
val iloczyn : int list -> int = <fun>

Oczywiście, żeby skonstruować wszystkie kontynuacje i tak trzeba przejrzeć całą listę. Jeśli jednak przyjrzymy się mnożeniom, to pierwsze zero na liście przerywa dalsze mnożenie.

Kontynuacji możemy również użyć do przekształcenia rekurencji w ogonową. Zobaczmy to najpierw na przykładzie procedury obliczającej silnię.

Przykład [Silnia ogonowo z kontynuacjami]

Spójrzmy na najprostszą rekurencyjną definicję procedury obliczającej silnię:

let rec silnia n = 
  if n <= 1 then 1 else n * silnia (n-1);;
val silnia : int -> int = <fun>

Oczywiście każdy z Czytelników potrafi przerobić tę deinicję na ogonową. Spróbujmy jednak użyć do tego kontynuacji. Dodajemy parametr będący kontynuacją -- procedurą, której należy przekazać obliczony wynik.

let silnia n = 
  let rec sil n cont = 
    if n <= 1 then cont 1 else sil (n-1) (fun x -> cont (x * n))
  in sil n id;;
val silnia : int -> int = <fun>


Technikę tę można również zastosować do rozgałęziających się wywołań rekurencyjnych.

Przykład [Liczby Fibonacciego ogonowo z kontynuacjami]

Spójrzmy na najprostszą rekurencyjną definicję procedury obliczającej liczby Fibonacciego:

let rec fib n = 
  if n < 2 then n else fib (n-1) + fib (n-2);;
val fib : int -> int = <fun>

Podobnie jak poprzednio, definicję rekurencyjną możemy przerobić na ogonową, dodając jako parametr kontynuację reprezentującą dalsze obliczenia. Zwróćmy uwagę, że kontynuacja dla pierwszego wywołania rekurencyjnego zawiera drugie wywołanie rekurencyjne.

let fib n = 
  let rec fibo n cont = 
    if n < 2 then cont n else fibo (n-1) (fun x -> fibo (n-2) (fun y -> cont (x+y)))
  in fibo n id;;
val fib : int -> int = <fun>

Oczywiście taka "rekurencja ogonowa" nie pozwala na zoptymalizowanie wywołań rekurencyjnych, gdyż przekazywana kontynuacja musi mieć dostęp do ramki danego wywołania.

Ćwiczenia

Ćwiczenia