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.