Atom to typ referencyjny przeznaczony do obsługi danych przetwarzanych współbieżnie, do których wymagany jest niekoordynowany, synchroniczny dostęp. Możemy dzięki niemu tworzyć współdzielone obiekty wyrażające zmieniające się stany, gdy zależy nam na tym, aby podczas zmiany wartości bieżącej uwzględniona była jej poprzednia wartość, chociaż dopuszczamy drobne zmiany w kolejności operacji, gdy więcej niż jedna aktualizacja zostanie zlecona w podobnym czasie.

Współbieżność

Wykonywanie współbieżne (ang. concurrent) to cecha systemów i programów komputerowych, w których te same obliczenia dokonywane są jednocześnie (w tym samym czasie) przez więcej niż jeden komponent, przy opcjonalnej komunikacji między komponentami.

Więcej o współbieżności w Clojure można przeczytać w odcinku 15.

Atomy

Atom (pisany wielką literą) to w Clojure coś innego niż lispowy atom, rozumiany jako S-wyrażenie, które nie jest listą. Znane z Lispu atomy są pewną kategorią wyrażeń i w tym znaczeniu nazywanie ich atomami ma sens. Jednak w Clojure znajdziemy również typ danych Atom (bazujący na klasie clojure.lang.Atom), służący do zarządzania współdzielonym, synchronicznym i niekoordynowanym stanem.

Współdzielenie oznacza, że żądanie dostępu do obiektu pamięciowego realizowane może być w tym samym czasie przez więcej niż jeden uruchomiony wątek, natomiast synchroniczność, że wątek, który zapoczątkował operację na obiekcie, zablokuje innym wątkom dostęp do niego podczas jej trwania, a sam nie będzie wykonywał dalszych czynności do zakończenia ustawiania nowej wartości.

Atom, podobnie jak Var, jest typem referencyjnym i przechowuje odniesienia do wartości, które mogą być zmieniane z użyciem odpowiednich funkcji. Operacje zmian powiązań referencji z wartościami zachodzą w sposób atomowy – mogą w całości udać się lub nie. To znaczy, że nie wystąpi sytuacja częściowej modyfikacji kontrolowanej Atomem struktury lub przesłonięcia modyfikacji dokonanej w tym samym czasie przez inny wątek. Jeżeli zmiana z jakichś przyczyn się nie powiedzie, operacja będzie ponawiana do skutku, za każdym razem uwzględniając najbardziej aktualną wartość bieżącą.

Gdy obiekt typu Atom zmienia wartość bieżącą, dochodzi do podmiany (ang. swap) wartości, na którą Atom wskazuje. Nowa zazwyczaj będzie bazowała na poprzedniej (będzie efektem zastosowania na niej wskazanej funkcji), chociaż można też powiązać obiekt referencyjny z podaną wartością stałą, ignorując zastaną.

W praktyce operacja synchronicznej aktualizacji jest w Atomach zoptymalizowana, tzn. najpierw obliczana jest nowa wartość bieżąca, a dopiero później zakładana jest blokada, podczas której sprawdzane jest tylko, czy wartość bieżąca z chwili rozpoczęcia obliczeń nowej jest taka sama jak wartość bieżąca po założeniu blokady. Gdy są równe, dochodzi do aktualizacji. Gdy nie są równe, cała operacja jest powtarzana, włączając w to wyliczanie nowej wartości.

Korzystanie z Atomów polega na utworzeniu odpowiedniego obiektu, a następnie aktualizowaniu jego powiązania z wartością z użyciem przekazywanej funkcji. Zazwyczaj obiekt typu Atom będzie dodatkowo w sposób stały utożsamiany z symbolem określonym pewną zmienną globalną lub powiązaniem leksykalnym. W ten sposób możliwym stanie się posługiwanie się nim z użyciem nazwy widocznej w odpowiednich obszarach programu.

Warto zaznaczyć, że – w przeciwieństwie do omawianego w dalszej części Agenta – podczas zmiany wartości bieżącej Atomu przekazywana funkcja aktualizująca będzie wywoływana do skutku, tzn. dopóki z powodzeniem uda się ustawić nową wartość. Przyczyną ponownego wywołania może być nałożenie się żądań zmian w podobnym oknie czasowym i dezaktualizacja wartości bieżącej w trakcie ustawiania nowej. Nie powinniśmy więc zakładać, że zawarte w funkcji uaktualniającej wyrażenia będą przeliczane tylko raz.

Tworzenie

Tworzenie obiektów typu Atom, atom

Do tworzenia obiektów typu Atom służy funkcja atom. Przyjmuje ona jeden obowiązkowy argument – wartość początkową (wskazywaną następnie przez referencję) i nieobowiązkowe argumenty opcji wyrażane w sposób nazwany, czyli w postaci par klucz–wartość.

Funkcja zwraca obiekt typu Atom.

Użycie:

• (atom wartość-początkowa & opcje).

Możliwe opcje to:

• :meta mapa-metadanowa,
• :validator funkcja.

Mapa metadanowa po słowie kluczowym :meta powinna być mapą wyrażoną z użyciem powiązanego z nią symbolu lub osadzoną w kodzie jako tzw. mapowe S-wyrażenie. Podane asocjacje staną się metadanymi tworzonego obiektu referencyjnego.

Funkcja podawana po słowie kluczowym :validator powinna być jednoargumentowym obiektem funkcyjnym, który podczas wywołania nie generuje efektów ubocznych, albo wartością nil. Przekazana funkcja będzie wywoływana za każdym razem, gdy dojdzie do zmiany stanu obiektu referencyjnego i przekazywana jej będzie nowo ustawiana wartość. Powinna ona zwracać false lub zgłaszać wyjątek, gdy wartość ta jest nieakceptowalna. Operację taką nazywamy walidacją, a wyrażającą ją funkcję walidatorem. Do pierwszego wywołania walidatora dojdzie podczas ustawiania wartości początkowej.

1
2
3

(atom              0)  ; => #<[email protected]: 0>
(atom 0 :meta {:a 1})  ; => #<[email protected]: 0>
(atom        [1 2 3])  ; => #<[email protected]: [1 2 3]>

Wyrażenie z linii nr 1 tworzy obiekt referencyjny typu Atom, który odnosi się do wartości 0. Zauważmy, że 0 nazwiemy lispowym atomem, ale nie Atomem z Clojure!

Wyrażenie drugie (z linii nr 2) działa tak samo, lecz dodatkowo ustawia metadaną.

Ostatnie wyrażenie przykładu ustawia wartość początkową na wektor utworzony z wykorzystaniem wektorowego S-wyrażenia.

Identyfikowanie Atomów

Atomy są obiektami, z którymi, podobnie jak z innymi pamięciowymi wartościami, można powiązać symboliczne identyfikatory. Możemy więc stwarzać odnoszące się do obiektów typu Atom globalne zmienne, jak również korzystać z innych rodzajów powiązań (np. leksykalnych).

1
2

(def nasz-atom (atom 0))        ; zmienna globalna
(let [atomek (atom 0)] atomek)  ; powiązanie leksykalne

Mogą również zdarzyć się sytuacje, w których powiązanie leksykalne będzie widoczne wewnątrz definiowanej funkcji anonimowej stanowiącej domknięcie. Jest to sposób na obsługę współdzielonego, lecz ograniczonego leksykalnie stanu.

Pobieranie wartości

Odczytywanie wartości Atomów, deref

Żeby odczytać wartość bieżącą Atomu możemy użyć funkcji deref. Przyjmuje ona jeden argument, którym powinien być obiekt typu Atom, a zwraca wartość bieżącą.

Użycie:

• (deref atom).

1
2
3

(def nasz-atom (atom 0))
(deref nasz-atom)
; => 0

Dereferencja Atomów, makro @

Makro czytnika @ (znak małpki) umieszczone przed wyrażeniem sprawia, że jeżeli reprezentowany nim obiekt jest typem referencyjnym, wywołana zostanie na nim funkcja odpowiedzialna za odczyt wskazywanej wartości bieżącej. W przypadku Atomów będzie to omówiona wyżej funkcja deref.

Użycie:

• @atom.

1
2
3

(def nasz-atom (atom 0))
@nasz-atom
; => 0

Zmiany wartości

Aktualizowanie wartości, swap!

Zmiana stanu obiektu typu Atom, czyli aktualizacja odniesienia, aby wskazywało inną wartość, możliwa jest z zastosowaniem funkcji swap!.

Pierwszym przyjmowanym argumentem powinien być obiekt typu Atom. Drugim funkcja, która jako pierwszy argument przyjmie wartość bieżącą Atomu i na jej podstawie obliczy nową wartość. Zostanie ona użyta do zastąpienia poprzedniego referencyjnego odniesienia w Atomie. Opcjonalnie możemy podać dodatkowe argumenty, które zostaną przekazane jako kolejne argumenty wywoływanej funkcji.

Gdyby któryś z kroków pośrednich (między odczytem a aktualizacją referencji) nie powiódł się, cała operacja będzie ponowiona. Dlatego istotne jest, aby przekazywana funkcja nie miała niezamierzonych efektów ubocznych – należy zakładać, że będzie ona wywołana więcej niż raz, jeżeli wartość bieżąca ulegnie w międzyczasie dezaktualizacji, ponieważ inny wątek szybciej dokonał zmian.

Gdy wywołujemy swap!, uruchamiana jest przekazana przez nas funkcja aktualizująca, która wylicza nową wartość na bazie istniejącej, a następnie wzywana jest wewnętrznie funkcja compare-and-set!. Właśnie ta ostatnia odpowiedzialna jest za atomową aktualizację referencji wewnątrz Atomu. Dokonuje ona zablokowania obiektu na czas pracy, a następnie porównuje, czy wartość użyta wcześniej jako bieżąca (stanowiąca podstawę obliczeń nowej wartości) nadal jest wartością bieżącą. Jeżeli naprawdę tak jest, dochodzi do podmiany odniesienia. W przeciwnym przypadku blokada jest znoszona, następuje wyjście z compare-and-set!, a obliczanie wartości bieżącej przez dostarczoną przez nas funkcję zaczyna się ponownie. W taki właśnie sposób Atomy gwarantują, że zmiany będą synchroniczne, a aktualizacje będą korzystały z najbardziej aktualnej wartości bieżącej.

Wartością zwracaną przez funkcję swap! jest nowa wartość bieżąca referencji.

Użycie:

• (swap! atom funkcja & argument…).

1
2
3
4
5

(def nasz-atom (atom 0))

@nasz-atom             ; => 0
(swap! nasz-atom inc)  ; => 1
@nasz-atom             ; => 1

Warto zauważyć, że w niektórych przypadkach funkcja swap! może nie być wystarczająco efektywna do ustawiania nowej wartości, właśnie z uwagi na połączenie operacji podmiany referencji (compare-and-set!) z operacją wyliczania nowej wartości (przekazywaną jako argument). Mogą bowiem zdarzyć się sytuacje, w których będziemy chcieli podjąć decyzję o tym, czy w ogóle przeprowadzać porównywanie wartości (i ew. jej podmianę) na podstawie wartości bieżącej Atomu, szczególnie jeżeli wyliczanie wartości jest czasochłonne, a jego powtarzanie nie ma sensu w pewnych warunkach. Innym przypadkiem będzie założenie o konieczności zwracania ostatnio dodanego do struktury kontrolowanej Atomem elementu, zamiast całej złożonej wartości (np. zagnieżdżonych map).

Ustawianie wartości, reset!

Funkcja reset! pozwala podmienić obiekt, do którego odnosi się Atom, ale bez obliczania nowej wartości na bazie aktualnej. Przyjmuje ona dwa argumenty: obiekt typu Atom i nową wartość.

Wartością zwracaną jest nowa wartość bieżąca referencji.

Użycie:

• (reset! atom wartość).

1
2
3
4

(def nasz-atom (atom 0))
@nasz-atom              ; => 0
(reset! nasz-atom "A")  ; => "A"
@nasz-atom              ; => "A"

Ustawianie warunkowe, compare-and-set!

Funkcja compare-and-set! pozwala podmienić obiekt, do którego odnosi się Atom, pod warunkiem, że jego wartość bieżąca jest równa podanej wartości. Pierwszym argumentem wywołania funkcji powinien być obiekt typu Atom, drugim wartość, która zostanie porównana z wartością bieżącą wskazywaną przez Atom, a ostatnim nowa wartość – zostanie ona powiązana z Atomem, jeżeli wspomniany warunek o równości będzie spełniony.

Funkcja zwraca true, jeżeli doszło do podmiany wartości bieżącej, a false w przeciwnym razie.

Użycie:

• (compare-and-set! atom poprzednia-wartość nowa-wartość).

1
2
3
4
5
6
7
8

(def atomek (atom 0))
@atomek                        ; => 0

(compare-and-set! atomek 2 5)  ; => false
@atomek                        ; => 0

(compare-and-set! atomek 0 5)  ; => true
@atomek                        ; => 5

Funkcja compare-and-set! jest wewnętrznie używana do ustawiania nowej wartości bieżącej, gdy wywołujemy np. swap!. Działa to w ten sposób, że tworzona jest pętla wykonywania, w której przekazana funkcja obliczająca nową wartość wylicza ją na podstawie zastanej wartości bieżącej, a potem wzywana jest compare-and-set! z trzema wartościami: obiektem typu Atom, poprzednią wartością bieżącą (z chwili obliczeń) i nową wartością bieżącą.

Jeżeli porównywanie aktualnej wartości bieżącej z poprzednią wartością bieżącą się powiedzie, zmiana zostanie dokonana i nastąpi powrót do funkcji swap! z wartością true. Stanie się tak, ponieważ będzie to oznaczało, że zmieniana będzie najbardziej aktualna bieżąca wartość, a więc nowa, wyliczona na jej podstawie, będzie zależała od najświeższych danych.

Jeżeli wartością zwróconą przez compare-and-set! będzie false, funkcja swap! dostanie informację, że w międzyczasie inny wątek dokonał już zmiany stanu Atomu i jego poprzednia wartość bieżąca (używana w obecnym wątku jako baza dla obliczania nowej) już się zdezaktualizowała. W takiej sytuacji obliczanie nowej wartości zostanie ponowione z użyciem nowszej wartości bieżącej Atomu.

Wyobraźmy sobie sytuację, w której Atom kontroluje dostęp do mapy, gdzie przechowywana jest lista użytych identyfikatorów dodawanych elementów, aby zachować ich unikatowy charakter. Zakładamy, że utworzenie nowego elementu jest czasochłonne.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

(def atomek (atom {:identyfikatory #{} :elementy []}))

(defn nowy-element
  [m id]
  (let [nowy-element (str "element " id)
        identyfikatory (get m :identyfikatory)]
    (println "Dodaję" nowy-element)
    (Thread/sleep 500)
    (if (contains? identyfikatory id)
    m
    (-> m
        (assoc :identyfikatory (conj identyfikatory id)
               :elementy (conj (get m :elementy) nowy-element))))))

(swap! atomek nowy-element :pierwszy)
(swap! atomek nowy-element :drugi)
(swap! atomek nowy-element :pierwszy)

; >> Dodaję element :pierwszy
; >> Dodaję element :drugi
; >> Dodaję element :pierwszy

@atomek
; => {:identyfikatory #{:drugi :pierwszy},
; =>  :elementy ["element :pierwszy" "element :drugi"]}

Wszystko wydaje się działać w porządku. Funkcja nowy-element zwiększa licznik o 1, a także aktualizuje mapę pod kluczem :elementy. Całość kontrolowana jest przez Atom, więc zmiany powinny być synchroniczne. Widzimy jednak, że dodawanie powielonego elementu sprawia, iż realizowany jest kod funkcji nowy-element, która z założenia jest czasochłonna.

Idealnie byłoby sprawdzać, czy identyfikator istnieje zanim dokonamy czasochłonnego generowania. Jeżeli możemy zmienić kod funkcji, to dobrze, lecz gdy nie możemy tego zrobić z pomocą przychodzi właśnie compare-and-set!:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

(def atomek (atom {:identyfikatory #{} :elementy []}))

(defn nowy-element
  [m id]
  (let [nowy-element (str "element " id)
        identyfikatory (get m :identyfikatory)]
    (println "Dodaję" nowy-element)
    (Thread/sleep 500)
    (if (contains? identyfikatory id)
    m
    (-> m
        (assoc :identyfikatory (conj identyfikatory id)
               :elementy (conj (get m :elementy) nowy-element))))))

(defn dodaj-element!
  [a id]
  (loop []
    (let [old @a]
      (if (contains? (get old :identyfikatory) id)
        old
        (let [new (nowy-element old id)]
          (if (compare-and-set! a old new)
            new
            (recur)))))))

(dodaj-element! atomek :pierwszy)
(dodaj-element! atomek :drugi)
(dodaj-element! atomek :pierwszy)

; >> Dodaję element :pierwszy
; >> Dodaję element :drugi

Widzimy, że w tym przypadku element pierwszy nie spowodował wywołania funkcji generującej i dodającej element do struktury, ponieważ podany identyfikator już istniał.

W podobny sposób poradzimy sobie też z sytuacją, gdzie w przypadku pomyślnej lub niepomyślnej aktualizacji ma powstać efekt uboczny, np. komunikat diagnostyczny w stylu „taki ID już istnieje” bądź zwrócone ma być pole obiektu Javy, a nie cała struktura. Testując wartość bieżącą przed wywołaniem swap! ryzykujemy wysłanie fałszywego komunikatu (w przypadku pierwszego wspomnianego zastosowania), jeżeli między testem a wywołaniem inny wątek zmieni strukturę. Z kolei umieszczając test wewnątrz funkcji przekazywanej do swap! ryzykujemy wielokrotne wyświetlanie komunikatu, gdyby została ona wywołana kilkukrotnie.

Tworząc własną implementację swap! z użyciem compare-and-set! jesteśmy również w stanie zwracać inną niż zaktualizowana wartość (np. wyliczony identyfikator, a nie całą strukturę, w której on się znalazł). Może to pomóc optymalizować programy pod kątem wydajnościowym, ponieważ nie wystąpi potrzeba dodatkowego przeszukiwania zagnieżdżonych struktur zwracanych przez swap!.

Walidatory

Atomy można opcjonalnie wyposażyć w mechanizmy testujące poprawność ustawianych wartości bieżących. Służą do tego funkcje set-validator! i get-validator.

Walidator (ang. validator) to w tym przypadku czysta (wolna od efektów ubocznych), jednoargumentowa funkcja, która przyjmuje wartość poddawaną sprawdzaniu. Jeżeli jest ona niedopuszczalna, funkcja powinna zwrócić wartość false lub wygenerować wyjątek.

Zarządzanie walidatorami, set-validator!

Funkcja set-validator! umożliwia ustawianie lub usuwanie walidatora dla podanego jako pierwszy argument obiektu typu Atom.

Jako drugi argument należy podać funkcję, która powinna przyjmować jeden argument i nie generować efektów ubocznych. Będzie ona wywoływana za każdym razem, gdy dojdzie do zmiany stanu referencji i jako argument przekazywana będzie jej wartość, z którą zażądano powiązania. Funkcja ta powinna zwracać wartość false lub zgłaszać wyjątek, gdy przyjmowana wartość jest nieakceptowalna.

Pierwsze sprawdzenie stanu jest dokonywane już w momencie ustawiania walidatora. Bieżąca wartość wskazywana referencją musi więc już wtedy być odpowiednia.

Jeżeli zamiast obiektu funkcyjnego podamy wartość nil, walidator zostanie odłączony od podanego obiektu typu Atom.

Funkcja set-validator! zwraca wartość nieustaloną nil, jeżeli udało się ustawić walidator.

1
2
3
4
5
6
7
8

(def atomek (atom 0))
(set-validator! atomek #(integer? %))  ; akceptujemy tylko liczby całkowite

(reset! atomek 1)
; => 1

(reset! atomek "napis")
; >> java.lang.IllegalStateException: Invalid reference state

Pobieranie walidatora, get-validator

Mając obiekt typu Atom, możemy pobrać funkcyjny obiekt przypisanego mu walidatora z użyciem get-validator. Funkcja ta przyjmuje jeden argument typu Atom, a zwraca obiekt funkcji lub wartość nieustaloną nil, gdy walidatora nie ustawiono.

Użycie:

• (get-validator atom).

1
2
3
4
5
6
7
8

(def atomek (atom 0))
(def nasz-walidator #(< % 5))

(set-validator! atomek nasz-walidator)
; => nil

(get-validator atomek)
; => #<user$nasz_walidator [email protected]>

Podpięcia

Obiekty typu Atom można wyposażać w podpięcia (ang. hooks) w postaci tzw. funkcji nadzorczych (ang. watch functions). Są one wywoływane, gdy zmienia się stan referencji (wyrażany wartością bieżącą), a służą do wykonywania dodatkowych, niezależnych operacji w reakcji na te zmiany.

Dodawanie obserwatorów, add-watch

Do obiektu typu Atom możemy dodawać funkcję nadzorczą z użyciem add-watch. Funkcja ta przyjmuje trzy argumenty. Pierwszym powinien być Atom, do którego chcemy podłączyć funkcję, drugim unikatowy klucz identyfikujący podpięcie, a ostatnim wspomniana funkcja. Unikatowość powinna być zachowana w obrębie pojedynczego, nadzorowanego obiektu.

Funkcja add-watch zwraca obiekt typu Atom, do którego podpięto funkcję nadzorczą.

Funkcja nadzorcza powinna przyjmować 4 argumenty: klucz, obiekt typu Atom, a także poprzednią wartość oraz nową wartość bieżącą Atomu. Zostanie ona wywołana w sposób asynchroniczny za każdym razem, gdy dojdzie do zmiany stanu Atomu, przy czym może się to zdarzyć również w czasie jej wywoływania. W związku z tym należy polegać na przekazanych jako dwa ostatnie argumenty wartościach, a nie dokonywać dereferencji obiektu typu Atom w ciele funkcji.

Możemy zarejestrować wiele funkcji nadzorczych, a w przypadku korzystania z tego samego funkcyjnego obiektu jesteśmy w stanie rozróżniać wywołania, korzystając z przekazywanego jako argument klucza.

Wywołanie add-watch z takim samym kluczem, jak wcześniej podany, zastępuje poprzednią funkcję obserwującą.

Użycie:

• (add-watch atom klucz funkcja).

1
2
3
4
5
6

(def atomek (atom 0))
(add-watch atomek :debug #(println (apply str (interpose ", " %&))))

(swap! atomek inc)  ; >> :debug, [email protected], 0, 1
(swap! atomek inc)  ; >> :debug, [email protected], 1, 2
(swap! atomek inc)  ; >> :debug, [email protected], 2, 3

Usuwanie obserwatorów, remove-watch

Funkcja remove-watch pozwala usunąć funkcję nadzorczą przypisaną do obiektu typu Atom. Przyjmuje ona dwa obowiązkowe argumenty: Atom i unikatowy klucz identyfikujący podpięcie.

Wartością zwracaną jest obiekt typu Atom, od którego odłączono funkcję nadzorczą.

Użycie:

• (remove-watch atom klucz).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

(def atomek (atom 0))
(defn reporter [& args] (println (first args)))
(add-watch atomek :debug reporter)
(add-watch atomek :inna  reporter)

(swap! atomek inc)
; >> :debug
; >> :inna

(remove-watch atomek :inna)
(swap! atomek inc)
; >> :debug

Przykłady zastosowań

Globalne tożsamości

Korzystając ze zmiennych globalnych, jesteśmy w stanie tworzyć w przestrzeniach nazw globalne identyfikatory dla wyrażających zmieniające się stany obiektów typu Atom. W ten sposób możemy w całym programie odwoływać się do konkretnego Atomu z użyciem nadanej mu symbolicznej nazwy o zasięgu nieograniczonym. Będziemy mieli więc dwa typy referencyjne: Var identyfikowany symbolem w przestrzeni nazw i Atom wskazywany wartością bieżącą tego pierwszego.

Spróbujmy zaimplementować przykładowy licznik w postaci funkcji, która za każdym wywołaniem będzie zwiększała jego wartość o jeden i zwracała ją, a jeżeli podamy argument, dokonane zostanie przypisanie konkretnej wartości początkowej:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

(defonce atom-licznika (atom -1))

(defn licznik
  ([x] (reset! atom-licznika (int x)))
  ([]  (swap!  atom-licznika inc)))

(licznik)      ; => 0
(licznik)      ; => 1
(licznik)      ; => 2

(licznik 100)  ; => 100
(licznik)      ; => 101
(licznik)      ; => 102

W pierwszej linii przykładu widzimy wywołanie makra defonce. Służy ono do jednokrotnego ustawiania powiązania głównego podanej zmiennej globalnej. W tym przypadku symbol atom-licznika zostanie powiązany z obiektem typu Atom stworzonym z użyciem funkcji atom. Wartością początkową będzie -1.

W linii nr 3 mamy definicję funkcji wieloczłonowej, czyli takiej, która ma warianty dla różnych zestawów przyjmowanych argumentów.

• Pierwsze ciało (linia nr 4) przyjmuje jeden argument i służy do ustawiania wartości licznika, jednocześnie zwracając tą wartość.

• Ciało drugie (linia nr 5) nie przyjmuje argumentów, a wartościowanie jego wyrażenia sprawia, że jako efekt uboczny wywoływana jest funkcja, która zwiększa wartość licznika o jeden, zaś po tej operacji emitowana jest przez funkcję nowa wartość.

Domknięcia

Ciekawym i znajdującym praktyczne zastosowanie sposobem korzystania z Atomów jest użycie domknięć.

Stwórzmy zmienną globalną, powiązaną z anonimową funkcją, która dokonuje zwiększenia o jeden wartości wskazywanej przez obiekt typu Atom (identyfikowany powiązaniem leksykalnym w ciele obejmującej konstrukcji let):

1
2
3
4
5
6
7

(defonce licznik
  (let [a (atom -1)]
    #(swap! a inc)))

(licznik)  ;=> 0
(licznik)  ;=> 1
(licznik)  ;=> 2

W powyższym przykładzie anonimowa funkcja z linii nr 3 zamyka w sobie powiązanie symbolu a z obiektem typu Atom, które jest widoczne w obejmującym kontekście leksykalnym. Funkcja ta zostaje w linii nr 1 nazwana z użyciem zmiennej globalnej. Możemy więc korzystać z symbolu licznik do tworzenia formy wywołania funkcji, która uruchomi podprogram realizujący operację zwiększenia o jeden wartości bieżącej utworzonego Atomu.

Spróbujmy podobnej implementacji licznika, lecz zrealizowanej z użyciem funkcji generującej obiekt typu Atom o ustalonej wartości początkowej:

1
2
3
4
5
6
7
8
9

(defn utwórz-licznik [wartość]
  (let [a (atom (dec wartość))]
    #(swap! a inc)))

(defonce licznik (utwórz-licznik 0))

(licznik)  ; => 0
(licznik)  ; => 1
(licznik)  ; => 2

Implementacja spamiętywania

Spamiętywanie (ang. memoization) to sposób optymalizacji programów komputerowych przez zapisywanie rezultatów wywołań czasochłonnych operacji, aby przy kolejnych ich wywołaniach korzystać z zapamiętanych wartości dla takich samych warunków wejściowych (np. argumentów).

W Clojure istnieje gotowa funkcja wyższego rzędu, memoize, która służy do buforowania wywołań innych funkcji z wykorzystaniem asocjacyjnej struktury, której kluczami są wartości przekazywanych argumentów. Nie zawsze jednak będziemy chcieli polegać wyłącznie na argumentach i zapisywać tylko zwracaną przez funkcję wartość (np. w przypadku obliczeń rekurencyjnych, gdzie przydałoby się zapamiętywanie rezultatów pośrednich). W takich przypadkach możemy pokusić się o stworzenie własnej funkcji spamiętującej.

Implementując mechanizmy spamiętywania, możemy skorzystać z Atomów, aby bezpiecznie synchronizować zmiany współdzielonych buforów.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

(defn !
  ([n] (! n 1))
  ([n acc] (if (zero? n) acc (recur (dec n) (*' acc n)))))

(defn spamiętaj [f]
  (let [a (atom {})]
    (fn [& args]
      (if-let [wynik (find @a args)]
        (val wynik)
        (let [r (apply f args)]
          (swap! a assoc args r)
          r)))))

(def ! (spamiętaj !))

(time (do (! 8000) nil))  ; >> "Elapsed time: 260.910553 msecs"
(time (do (! 8000) nil))  ; >> "Elapsed time: 0.085696 msecs"
(time (do (! 7999) nil))  ; >> "Elapsed time: 168.098467 msecs"

Zamiast definiować funkcję spamiętaj możemy też posłużyć się wspomnianą, wbudowaną funkcją memoize, która też korzysta z Atomów.

Widzimy, że w linii nr 17 rezultat nie był przeliczany, lecz serwowany z podręcznej mapy, do której dostępem zarządza referencyjny obiekt typu Atom. W związku z tym czas wykonywania był nieporównywalnie mniejszy.

Optymizm kończy się jednak w linii nr 18, gdzie możemy zaobserwować, że niezależnie od tego, czy posłużymy się memoize, czy własną funkcją spamiętaj, nie będziemy mieli do czynienia z wykorzystaniem rezultatów pośrednich rekurencyjnych wywołań, ponieważ zapisywane są tylko ostateczne wyniki obliczeń zwracane przez funkcję. Jeżeli wywołamy ją dla argumentu o wartości 8000, a potem dla 7999, to rekurencyjne operacje mnożenia dla przeliczanego już wcześniej ciągu rezultatów (od 1 do 7999) będą wykonywane ponownie. Spróbujmy więc przerobić nieco nasz kod, aby było inaczej:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

(def !                              ; definicja zmiennej globalnej
  (let [mem (atom [1 2 6 24])]      ; Atom z buforem rezultatów
    (fn f                           ; funkcja anonimowa
      ([n]                          ; pierwsze ciało (jeden argument):
       (let [mem-cnt (count @mem)]  ; ostatnio zapamiętany wynik
         (if (<= n mem-cnt)         ; czy zapamiętano?
           (nth @mem (dec n))       ; · tak: zwróć zapamiętany rezultat
           (f n                     ; · nie: zacznij od pamiętanego
              (inc mem-cnt)
              (nth @mem (dec mem-cnt))))))
      ([n cur acc]                  ; drugie ciało (trzy argumenty):
       (let [new-cur (inc cur)      ; nowy nr kolejny
             new-acc (*' acc cur)   ; nowy rezultat
             cur-idx (dec cur)]     ; bieżący indeks wektora podręcznego
         (swap! mem assoc           ; zapamiętaj rezultat
                cur-idx new-acc)
         (if (= n cur)                      ; warunek zakończenia
           new-acc                          ; · przypadek bazowy
           (recur n new-cur new-acc)))))))  ; · przypadek rekursywny

(time (do (! 8000) nil))  ; >> "Elapsed time: 180.090641 msecs"
(time (do (! 8001) nil))  ; >> "Elapsed time: 0.108044 msecs"
(time (do (! 7999) nil))  ; >> "Elapsed time: 0.185428 msecs"
(time (do (! 7999) nil))  ; >> "Elapsed time: 0.048888 msecs"

Zamiast definiować funkcję nazwaną z użyciem defn skorzystaliśmy tu z funkcji anonimowej (fn), którą potem nazwaliśmy, tworząc zmienną globalną (def). Dzięki temu funkcja może korzystać z powiązanego z obiektem typu Atom symbolu mem (linia nr 2). Mamy do czynienia z domknięciem, ponieważ powiązanie jest utworzone i widoczne w obejmującym definicję funkcji zasięgu leksykalnym.

Korzystamy tu z funkcji wieloczłonowej, czyli takiej, która może mieć kilka wariantów, różniących się zestawami przyjmowanych argumentów. W naszym przypadku mamy dwa ciała:

• pierwsze jednoargumentowe (linie od 4 do 10),
• drugie trójargumentowe (linie od 11 do końca).

Zadaniem pierwszego jest przygotowanie liczników przekazywanych jako argumenty i sprawdzenie, czy można kontynuować obliczenia z wykorzystaniem zapisanych w pamięci podręcznej wyników, a następnie wywołanie wariantu trójargumentowego dla określonych wartości początkowych. Ciało drugie to właściwa funkcja obliczeniowa.

W powyższym kodzie zmieniliśmy nieco algorytm wyliczania silni: zamiast zmniejszać licznik o 1 przy każdym rekursywnym wywołaniu i dążyć do zera, rozpoczynamy od 1 i sprawdzamy, czy już przemnożyliśmy wszystkie kolejne rezultaty pośrednie. Dzięki temu jesteśmy w stanie umieszczać je w pamięci podręcznej, a przy tym wciąż korzystać z optymalizacji w postaci rekurencji ogonowej. Rezultaty pośrednie (wartości silni dla kolejnych liczb całkowitych) przekazywane są jako ostatni argument wywołania funkcji wyliczającej (parametr acc), a jako jej drugi argument (parametr cur) przekazywana jest bieżąca pozycja wyniku w ciągu. Pierwszy parametr (n) zawiera wartość używaną do określenia warunku zakończenia rekurencji.

Zamiast korzystać z zewnętrznej funkcji spamiętującej, buforowanie rezultatów zostało ściśle zintegrowane z implementacją algorytmu. Dzięki temu w buforze nie są zapisywane wyłącznie rezultaty dla konkretnych argumentów, ale również wyniki pośrednie, które w przypadku obliczeń silni nadają się do ponownego użycia w kolejnych wywołaniach.

Efekty możemy zauważyć, badając czasy wykonania: obliczenia dla liczb większych niż wcześniej zapamiętane są rozpoczynane od ostatnio zapisanych wyników, a nie od początku, co skutkuje znacznie krótszymi czasami realizacji algorytmu.

Do przechowywania rezultatów używamy wektora, który jest strukturą danych dobrze pasującą do problemu: jego kluczami są kolejne liczby całkowite, a dostęp do elementu o wskazanej pozycji odbywa się w stałym czasie.

Warto nadmienić, że podobny efekt (buforowania rezultatów pośrednich) możemy uzyskać również wtedy, gdy wyrazimy dany algorytm z użyciem leniwej sekwencji.

Na koniec możemy pokusić się o modyfikację naszej funkcji w taki sposób, aby była bardziej hermetyczna (nie pozwalała na bezpośrednie wywoływanie wariantu wieloargumentowego) i zwięźlej wyrażona.

Zamiast tworzyć dodatkowe ciało skorzystamy z konstrukcji loop. Dzięki temu uda się też uniknąć przekazywania przez argument wartości używanej w warunku zakończenia rekurencji (parametr n). Poza tym dodamy obsługę przypadku, gdy argumentem jest zero, a zamiast akumulować poprzednio obliczone wyniki w parametrze wywołania, będziemy je pobierali z bufora rezultatów, do którego wcześniej trafiają:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

(def !                           ; definicja zmiennej globalnej
  (let [m (atom [1 1 2 6 24])]   ; Atom z buforem rezultatów
    (fn [n]                      ; funkcja:
      (let [m-count (count @m)]  ; nr ostatnio zapamiętanego wyniku
        (if (< n m-count)        ; czy zapamiętano dla bieżącego?
          (nth @m n)             ; · tak: zwróć zapamiętany rezultat
          (loop [cur m-count]    ; · nie: wywołaj konstrukcję liczącą
            (let [r (*' (nth @m (dec cur)) cur)] ; nowy rezultat
              (swap! m assoc cur r)              ; zapamiętaj rezultat
              (if (= n cur)                      ; warunek zakończenia
                r                                ; · przypadek bazowy
                (recur (inc cur))))))))))        ; · przypadek rekursywny

(time (do (! 8000) nil))  ; >> "Elapsed time: 154.966845 msecs"
(time (do (! 8001) nil))  ; >> "Elapsed time: 0.104064 msecs"
(time (do (! 7999) nil))  ; >> "Elapsed time: 0.092260 msecs"
(time (do (! 7999) nil))  ; >> "Elapsed time: 0.064882 msecs"