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

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