OCaml/Lazy

Język OCaml, podobnie jak większość języków imperatywnych, stosuje gorliwą metodę obliczania wartości wyrażeń. Oznacza to, że ustalana jest wartość wyrażeń tak szybko jak pojawiają się w kodzie programu, a nie dopiero wtedy gdy jest ta wartość potrzebna.

Pewnym wyjątkiem może być konstrukcja specjalna if-then-else, której składowe są obliczane dopiero po ustaleniu wartości warunku:

if a > 2 then
  calc a
else
  calc (a * 2)

W w/w przypadku funkcja "calc" zostanie wywołana oczywiście tylko raz.

Czasami może zajść potrzeba odroczenia chwili obliczenia wyrażenia do momentu kiedy ta wartość będzie w istocie potrzebna. Ponadto, zakładając, że funkcja, którą obliczamy wartość nie ma efektów ubocznych możemy połączyć to "uleniwianie/zawieszanie" ze spamiętywaniem wyniku. Dzięki temu możemy np. nie rezygnując z rekurencyjnej definicji funkcji fib:

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

Sprawić, że będzie obliczana w czasie liniowym O(n). Takie podejście nazywa się programowaniem dynamicznym.


Elementy które będą nam potrzebne do zrealizowania tego modelu to przede wszystkim:

  • zawieszacz - a więc coś co odroczy obliczanie wyrażenia, może być połączony z...
  • spamiętywacz - nie tylko zawiesi obliczenie wartości, ale i spamięta wynik podczas wymuszenia.
  • poganiacz - coś co wymusi na wyrażeniu obliczenie jego wartości.

OCaml implementuje te elementy za pomocą słowa kluczowego lazy oraz za pomocą funkcji z modułu Lazy. Programista jakby chciał napisać je sam będzie miał pewien mały problem. Zawieszacz nie może być zwykłą funkcją, bo operuje na "kodzie" swojego argumentu a nie na jego wartości. Jest to po prostu makro, które zamienia podany argument na funkcję, która bierze argument unit (lazy a: unit -> a). Poganiacz wywołuje tak powstałą funkcję i zwraca jej wartość.

# let calc = lazy (                
    Printf.printf "Wynik 89 * 55 = %d\n" (89 * 55); 
  );;
val calc : unit lazy_t = <lazy>

# Lazy.force calc;;
Wynik 89 * 55 = 4895
- : unit = ()


Spróbujmy wyobrazić sobie jak może wyglądać definicja "spamiętywacza". Będziemy się musieli na pewno wesprzeć na imperatywnej komórce pamięci:

# let generate () =
    let value = ref 0 in
    let add x = value := !value + x
    and del x = value := !value - x
    and get () = !value
    in (add, del, get);;
val generate : unit -> (int -> unit) * (int -> unit) * (unit -> int) = <fun>

# let add0, del0, get0 = generate ();;
val add0 : int -> unit = <fun>
val del0 : int -> unit = <fun>
val get0 : unit -> int = <fun>

# add0 30;;
- : unit = ()
# del0 5;;
- : unit = ()
# get0 ();;
- : int = 25

Powyższa konstrukcja przypomina trochę programowanie obiektowe. Stworzyliśmy trzy funkcje, które jako jedyne mają dostęp do komórki pamięci na której operują. Na podobnej zasadzie działa spamiętywanie zaimplementowane w module Lazy.