OCaml/Lazy

Z Wikibooks, biblioteki wolnych podręczników.
Przejdź do nawigacji Przejdź do wyszukiwania

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.