Wreszcie rozumiem monady!

Pierwszy raz zetknąłem się z nimi dobrych osiem lat temu, przy okazji nauki Haskella; wtedy jednak nie starczyło mi cierpliwości, aby zaznajomić się z podstawami teoretycznymi. Sprawy nie ułatwiał fakt, że trudno o naprawdę przystępne i zrozumiałe wprowadzenie do tego tematu: wygląda na to, że każdy adept Haskella, zrozumiawszy monady, pisze na ten temat własny tutorial. Ja się powstrzymam od tego naturalnego odruchu i po prostu odeślę do niesamowicie szczegółowego, ośmioczęściowego cyklu artykułów autorstwa Mike'a Vaniera, który — wreszcie! — sprawił, że coś mi “zaskoczyło” w umyśle. Zamiast tego w tym wpisie wynotuję najważniejsze spostrzeżenia, jakie zapamiętałem, a potem pokażę dwie wersje pewnego kodu operującego na sekwencjach bitów: niemonadyczną i napisaną z użyciem monady state.

Mike zakłada znajomość Haskella, jak pisze we wstępie, na poziomie typów polimorficznych i klas typów; w praktyce jednak myślę, że do zrozumienia tekstu wystarczy pewne obycie z haskellową notacją (bardzo zresztą przypominającą zwykłą notację matematyczną), bo bardziej zaawansowane rzeczy są wyjaśniane w tekście na bieżąco. Bardzo polecam.

Oto więc moje notatki:

• Kluczowe dla zrozumienia monad jest pojęcie funkcji monadycznych; znacznie łatwiej jest je sobie intuicyjnie wyobrazić niż monadyczne wartości, zwracane przez m-return. Mike podaje pewne intuicje także dla tych drugich, ale dla mnie ważne jest, żeby myśleć o monadach w kategoriach (wzbogaconych) funkcji, a nie wartości przez nie zwracanych.
• Łatwo wydefiniować przy użyciu prostego złożenia operacji m-bind i m-return funkcję składającą ze sobą dwie funkcje monadyczne. Przy użyciu tego operatora, który Mike nazywa <=<, prawa rządzące monadami wyrażają się w elegancki i prosty do zapamiętania sposób: jest to operator łączny oraz m-return jest jego lewą i prawą jedynką.
• I bodaj najistotniejsza rzecz — nie trzeba rozumieć monad, żeby ich używać. Niby oczywiste i niby tak właśnie pisałem do tej pory kod haskellowy, radośnie używając do-notacji tak jakbym pisał kod imperatywny; ale okazuje się, że w ten sam sposób można z powodzeniem używać monady stanu i wyjaśnić, co ona robi, zupełnie w oderwaniu od całej reszty teorii monad. Wiedza na temat tego, co się dzieje “pod spodem”, jest konieczna tylko (i aż!) do zrozumienia, co poszczególne monady mają ze sobą wspólnego.

Reszta tego wpisu będzie poświęcona właśnie przykładowemu użyciu monady stanu w Clojure. Pisałem wcześniej, że nie widziałem dotąd kodu, który dałby się wyrazić przejrzyściej zapisany z użyciem monad niż bez nich — i właśnie na taki kod się natknąłem.

Wyobraźmy więc sobie, że mamy strumień bitów. Dla prostoty zdefiniujmy sobie przykładowy strumień, na którym będziemy testować nasze funkcje, jako clojurowy wektor zer i jedynek.

(def v [1 1 1 0 1 0 1 0 1 0])

Chcemy naddać naszemu strumieniowi pewne uporządkowanie: zdekodować zera i jedynki, które z niego przychodzą, według jakiegoś kodu o zmiennej długości. Najbardziej oczywistym, znanym każdemu kodem jest kod binarny: czytamy ze strumienia ileś bitów, traktujemy je jako binarną (bez znaku) reprezentację pewnej liczby i zwracamy tę liczbę. Łatwo napisać w Clojure funkcję, która to robi.

(defn read-binary [n bits]
  (loop [res 0 n n [fst & rst :as bs] bits]
    (if (zero? n)
      [res bs]
      (recur (+ res res fst) (dec n) rst))))

Spróbujmy wczytać z naszego strumienia czterobitową liczbę:

(read-binary 4 v)
;=> [14 (1 0 1 0 1 0)]

Czternaście. Ale zauważmy, że zdekodowana liczba nie jest jedyną zwracaną wartością! Żeby dało się z naszego strumienia odczytywać dalsze liczby, musimy zwrócić parę (wektor dwuelementowy): wartość odczytana plus reszta strumienia, z ktróej będziemy czytać dalej. Piszemy wszak funkcyjnie: nie zmieniamy naszych wartości w miejscu, tylko z jednych wartości produkujemy następne.

Innym rodzajem kodu jest kod unarny: czytamy po prostu ze strumienia jedynki, aż napotkamy pierwsze zero — wtedy przestajemy czytać i naszą wartością jest liczba przeczytanych bitów. W ten sposób dowolną liczbę dodatnią n da się zareprezentować na n bitach. Implementacja jest równie prosta:

(defn read-unary [bits]
  (loop [n 1 [fst & rst] bits]
    (if (zero? fst)
      [n rst]
      (recur (inc n) rst))))

Sprawdzamy:

(read-unary v)
;=> [4 (1 0 1 0 1 0)]

Trzy jedynki i zero, razem cztery skonsumowane bity, więc odczytaną liczbą jest 4. Działa.

Spróbujmy teraz skleić nasze funkcje, to znaczy odczytać ze strumienia dwie liczby: najpierw zakodowaną unarnie, a potem binarnie na sześciu bitach.

(let [[x v1] (read-unary v)
      [y v2] (read-binary 6 v1)]
  [x y])
;=> [4 42]

Wynik jest poprawny, ale kod nieelegancki: tak naprawdę nie interesują nas te wszystkie v, v1, v2, które przepychamy przez nasze funkcje; potrzebujemy tylko przeczytanych liczb, a poszczególne części strumienia są nam tylko po to, żeby mieć z czego czytać. Im więcej składanych ze sobą operacji, tym łatwiej się pomylić.

Tu wkracza monada stanu, która umożliwia ukrycie tych pośrednich wartości i bardziej eleganckie złożenie read-unary i read-binary. Monadycznie zapisalibyśmy to jakoś tak:

(domonad state-m
         [x read-unary
          y (partial read-binary 6)]
         [x y])
;=> #

Wygląda to bardzo podobnie. domonad state-m jest jak let. Tak jak chcieliśmy, nie przekazujemy naszego stanu (strumienia) explicite; zamiast tego przy x i y podajemy funkcje, które mają być zawołane na aktualnym stanie, żeby uzyskać żądaną wartość i nowy stan.

No dobrze, ale gdzie tu miejsce na nasz stan początkowy? Jak go przekazać? Proste: powyższa formuła, jak widać z mało czytelnego wyniku, zwróciła jakąś funkcję. Wystarczy ją teraz zawołać na naszym początkowym stanie, aby uzyskać wynik wraz ze stanem końcowym:

(*1 v)
;=> [[4 42] nil]

Jedyne, co wydaje się nadmiarowe w naszym złożeniu, to owo partial pojawiające się wyżej. Jest to efekt uboczny faktu, że Clojure w odróżnieniu od Haskella rozróżnia funkcje jedno- i więcejargumentowe (tak dokładniej to w Haskellu występują wyłącznie funkcje jednoargumentowe). Skoro w domonad state-m powinny na przemian pojawiać się symbole i funkcje jednoargumentowe biorące stan, to gdy nasza funkcja akceptuje coś jeszcze (tu: liczbę bitów), powinniśmy zrobić z niej funkcję jednoargumentową za pomocą partial. Alternatywnie, jeżeli chcemy trzymać się stylu monadycznego, możemy przepisać read-binary jako:

(defn read-binary [n]
  (fn [bits]
    (loop [res 0 n n [fst & rst :as bs] bits]
      (if (zero? n)
        [res bs]
        (recur (+ res res fst) (dec n) rst)))))

Teraz zamiast (partial read-binary 6) możemy napisać po prostu (read-binary 6).

Teraz, kiedy umiemy już składać operacje stanowe, zilustrujemy to przy pomocy jeszcze jednego kodu, a właściwie rodziny kodów nazywanych kodami Golomba. Po szczegółowy opis odsyłam do Wikipedii, natomiast dla potrzeb tego artykułu wystarczy nam wiedza, że te kody są parametryzowane jedną liczbą m. Liczba w kodzie Golomba jest podzielona na dwie części, z których pierwsza jest zakodowana unarnie, a druga — nie większa niż m — binarnie. W implementacji możemy więc skorzystać z naszych gotowych już funkcji read-unary i read-binary.

Bez dłuższych już komentarzy przedstawię dwie implementacje: eksplicytną i używającą monady stanu. Obie będą używać pomocniczej funkcji read-bit, czytającej po prostu jeden bit ze strumienia i używanej tak samo jak read-unary czy read-binary.

(defn read-bit [[bit & bits]]
  [bit bits])

Najpierw wersja niemonadyczna:

(defn read-golomb [m]
  (fn [bits]
    (let [k (clog2 m)
          r (- (bit-shift-left 1 k) m)
          [a bits1] (read-unary bits)
          [b bits2] ((read-binary (dec k)) bits1)
          [ir bits] (if (< b r)
                      [b bits]
                      (let [[nb bits] (read-bit bits)]
                        [(+ b b nb (- r)) bits]))]
      [(+ (* (dec a) m) ir) bits])))

A teraz używająca monad. Żeby nie przeplatać let i domonad, można po prostu zdefiniować funkcję zwracającą pewną stałą wartość i niezmieniony stan — nazwę ją m-const:

(defn m-const [x]
  (fn [state]
    [x state]))

Używając jej, możemy zaimplementować read-golomb tak:

(defn read-golomb-monadic [m]
  (domonad state-m
           [k (m-const (clog2 m))
            r (m-const (- (bit-shift-left 1 k) m))
            a read-unary
            b (read-binary (dec k))
            nb (if (< b r) (m-const nil) read-bit)]
           (+ (* (dec a) m)
              (if (< b r) b (+ b b nb (- r))))))

Czytelniej?

Rich Hickey, autor Clojure, wyrasta na Steve'a Jobsa nowoczesnych języków programowania — przynajmniej jeśli idzie o sposób prezentacji swoich dzieł. Oto kilka dni temu na grupie dyskusyjnej Clojure pojawiło się ogłoszenie, że Rich wystąpi na najbliższym spotkaniu nowojorskiej grupy użytkowników Clojure, że strumień wideo z wystąpienia będzie nadawany na żywo i że zaprezentowane zostanie “coś nowego”.

Tym czymś okazał się ClojureScript: kompilator Clojure do JavaScriptu, łączący moc pierwszego języka z powszechnością drugiego.

JavaScript bywa nazywany “czarnym koniem” języków programowania, najbardziej niedocenianym językiem minionej dekady i najważniejszym obecnej. Istotnie, silniki JavaScriptu w przeglądarkach — a także wolnostojące, jak Node.js — poczyniły w ostatnich latach kolosalne postępy, jeśli chodzi o wydajność, narzędzie to jest coraz chętniej używane do programowania coraz poważniejszych aplikacji i nie mijając się z prawdą można powiedzieć, że JavaScript jest wszędzie.

A teraz te same słowa można odnieść również do Clojure. W tegorocznym sondażu, podobnie jak rok temu, społeczność Clojure najczęściej wskazywała JavaScript jako hipotetyczną alternatywną wobec JVM platformę, ale zapewne mało kto się spodziewał, że urzeczywistni się to tak szybko. Łatwo sobie uzmysłowić możliwości, jakie daje nowa implementacja. Ten sam kod na serwerze i w przeglądarce? Programowanie aplikacji iOS w Clojure? Jak najbardziej!

W ramach dodawania łyżki dziegciu do tej beczki miodu trzeba zauważyć jednak, że dialekt ClojureScript jest okrojony i ma nieco inną semantykę niż standardowy Clojure: nie ma STM, niezmienność struktur danych nie jest wymuszana, wektory są zwykłymi JavaScriptowymi tablicami. Czy to się zmieni, pokaże przyszłość.

Jaka przyszłość czeka Clojure i ClojureScript? Spróbuję pokusić się o przepowiednię:

• Pojawienie się alternatywnej wobec JVM platformy wymusi ukształtowanie się bogatszej niż do tej pory biblioteki standardowej Clojure, wspólnej dla obu wersji. Ten proces trwa już teraz: tam, gdzie w czasach Clojure 1.0 pisało się (.toUpperCase "foo") (wychodząc z założenia where Java isn’t broken, Clojure doesn’t fix it), teraz kanoniczną formą jest (clojure.string/upper-case "foo"). W ten sposób Clojure stopniowo stanie się językiem niezabawkowym według definicji Maćka Pasternackiego.
• ClojureScript otworzy dla Clojure zupełnie nową niszę: stanie się popularny wśród programistów-frontendowców, piszących do tej pory głównie w JavaScripcie lub CoffeeScripcie.
• Równocześnie pojawienie się ClojureScript nie oznacza, że zatrzymają się prace nad “tradycyjnym” Clojure. JVM pozostanie główną platformą rozwoju języka i to tam będą pojawiać się kolejne innowacyjne cechy. Wersja 1.3 jest już w fazie beta i nadanie jej statusu final jest kwestią kilku tygodni.

Patrząc wstecz, aż trudno uwierzyć, jak dużą popularność zdobyło sobie Clojure. Gdyby ktoś mi cztery lata temu powiedział, że za cztery lata pojawi się nowy język z rodziny Lisp, który będzie znacznie bardziej elegancki niż Common Lisp, znacznie praktyczniejszy niż Scheme i używać go będą wielkie instytucje finansowe, wyśmiałbym go. A jednak: zaczynam wierzyć, że prawo Kopernika jednak nie stosuje się w informatyce.

Jest niedzielny poranek, siedzę w pociągu relacji Szczecin-Warszawa i właśnie wyciągnąłem laptopa, aby spisać wrażenia z trzeciej edycji konferencji java4people, która odbyła się wczoraj w Szczecinie, póki jeszcze nie okrzepły i nie rozmyły się.

Zanim opowiem o poszczególnych wystąpieniach, winienem oddać zasłużone gratulacje organizatorom, czyli szczecińskiemu JUG-owi. Przestronne, nowoczesne aule Zachodniopomorskiego Uniwersytetu Technologicznego, dostępne przez cały czas ciastka i herbata, obiad (załapałem się na dokładkę!), after-party, a nade wszystko ciekawe prezentacje i rozmowy kuluarowe — wszystko to stwarzało znakomitą atmosferę sprzyjającą temu, aby posłuchać o nowych językach i technologiach wokół Javy i JVM oraz “dzielić się wiedzą i pasją”, jak głosi motto konferencji. Wielkie brawa!

Jedyny niedosyt polegał na tym, że prezentacje poprowadzone były w dwóch równoległych blokach, a do tego w trzecim bloku trwały warsztaty z SWT/JFace. Momentami bardzo doskwierał mi brak możliwości bilokacji, ale trudno winić o to organizatorów.

Oficjalnego otwarcia dokonał prof. Antoni Wiliński, dziekan Wydziału Informatyki ZUT, życząc uczestnikom owocnej wymiany doświadczeń. Następnie część ludzi udała się posłuchać wystąpienia Tomka Kopacza o .NET i Javie, ja zaś zadebiutowałem w roli prelegenta na imprezie tego formatu, opowiadając o Clojure.

Trudno mi wypowiadać się o własnej prezentacji — nie jestem dobrym mówcą i to było widać. Jak się jednak okazało z rozmów ze słuchaczami, udało się zainteresować część osób tematem. Sukces jest więc połowiczny, a postaram się, aby następnym razem było lepiej. Slajdy można znaleźć tu.

Potem wybrałem się na wystąpienie Przemka Pokrywki o Scali. Scala bywa wymieniana jednym tchem z Clojure, gdy mowa o nowych językach funkcyjnych działających na JVM, więc byłem bardzo ciekaw tego wykładu. I nie zawiodłem się: z Przemka wprost emanowała pasja, znać było też dużą wiedzę i doświadczenie w temacie. Przemek ciekawie pokazał, w jaki sposób Scala łączy paradygmat funkcyjny z obiektowym — w tym drugim zakresie przypomina mi Smalltalka: tu też wszystko jest obiektem i 2 + 3 oznacza zawołanie na obiekcie 2 metody + z parametrem 3. Fajnym mechanizmem wydaje się też możliwość definiowania własnych niejawnych konwersji — to sposób na wzbogacanie już istniejących klas o nowe funkcjonalności, ale bez zmiany tych klas; przypomina to trochę Clojurowe protokoły i extend-type. Dopisuję do listy rzeczy do wypróbowania.

Po obiedzie, zachęcony tytułem, wybrałem się na prezentację “Skalowalność technologii Javowych w zastosowaniach komercyjnych” Dawida Gruszczyńskiego. Organizatorzy konferencji na samym początku rozdali ankiety, w których prosili o ocenienie każdego wystąpienia w skali od 1 (szkoda czasu) do 5 (naprawdę warto) — po tej prezentacji dały się słyszeć rozmowy, że należałoby dać jej 0 albo i -1. Ja jestem łagodniejszy w swych ocenach. Bezsprzecznie prezentacja była źle zatytułowana: tytuł obiecywał opowieść o technikach czy narzędziach projektowania skalowalnych aplikacji; tymczasem okazało się to klasycznym success story dotyczącym systemu obsługi spisu powszechnego, w tym oprogramowania działającego na terminalach używanych przez rachmistrzów.

Czy ta prezentacja była nie na miejscu na takiej konferencji? Może i tak. Mam jednak słabość do success stories i duży szacunek do ludzi, którym udaje się stworzyć działające, niezawodne oprogramowanie, nawet jeśli nie zgadzam się z wyborem technologii. To naprawdę spora rzecz. A samej prelekcji trzeba oddać, że była sprawnie przeprowadzona, slajdy zrozumiałe, a diagramy prezentujące architekturę systemu — czytelne. Wątpliwości słuchaczy budziła kwestia bezpieczeństwa transmisji danych (i samych rachmistrzów!) Ciekawostka: terminale rachmistrzowskie mają zmienne IP, ale nie powiadamiają serwera co chwila o swoim aktualnym adresie, bo wywoływałoby to zanadto duże obciążenie. Co więc robi terminal, gdy zmieni mu się adres? Otóż… wysyła SMS (!) ze swoim aktualnym adresem!

Na wystąpieniu Sebastiana Pietrowskiego o Jythonie (a także samym Pythonie i Django) nie dowiedziałem się wiele nowego, z racji wcześniejszych swoich doświadczeń z Pythonem. Ale też celem tej prezentacji było chyba nie tyle przekazanie wiedzy, co podzielenie się własnymi doświadczeniami, z subiektywnego punktu widzenia — i to udało się Sebastianowi znakomicie. Stąd slajdy zatytułowane “What I Like”, “What I Don’t Like”, “What I’d Use Python For” — bardzo pragmatyczne. Sebastian opowiadał między innymi o tym, że Jythona można fajnie wykorzystać jako narzędzie do eksploracji nowych API z REPL-a: używając pythonowej introspekcji można łatwo obejrzeć listę pól i metod udostępnianych przez dowolną klasę. W swoim wystąpieniu o tym nie opowiadałem, ale w pakiecie repl-utils w Clojure Contrib jest funkcja show, która daje bardzo podobny efekt.

Słuchając wystąpienia Bartka Kuczyńskiego o Vaadinie utwierdziłem się w przekonaniu, że nie chcę pisać aplikacji webowych tak jak okienkowe, na modłę swingową. Vaadin ma w zamierzeniu służyć właśnie do tego: to nadbudowany nad GWT modularny framework WWW. Bartek pokazywał dziejącą się pod spodem magię, wraz z protokołem, którym część kliencka kompilowana do JS komunikuje się z serwerową (UIDL — dobrze pamiętam? — i JSON z danymi do wyświetlenia, poprzedzonymi ni mniej ni więcej tylko pętlą nieskończoną for(;;);, co podobno ma jakiś sens). Psikus w tym, że ostatnio w Smyrnie zrobiłem dokładnie odwrotną rzecz, to znaczy napisałem aplikację desktopową tak jakbym pisał webową, a więc używając ajaksowego XML-RPC (odsyłam do niedawnego postu na ten temat), i wyszło na oko prościej niż w Vaadinie. Może opowiem o tym na Warszawa JUG?

Nie zdążyłem się obejrzeć, a to już koniec konferencji! Do dotychczasowych bonusów dołączył kolejny: wśród wypełniających ankiety organizatorzy rozlosowali pięć książek. Los wytypował mnie jeszcze raz i schowałem do plecaka “Domain-Specific Languages” Martina Fowlera.

Pokonferencyjne after-parties bywają bodaj ważniejszymi nawet elementami takich spotkań niż same prezentacje. To tam toczy się najwięcej rozmów, to tam zawiązują się nowe znajomości i trwają nieskrępowane, długie dyskusje. Tak bywa z pizzą na Auli, tak było i teraz. Wielkie dzięki raz jeszcze organizatorom, wszystkim, których poznałem, z którymi udało mi się porozmawiać, i tym, którzy przebrnęli przez moje wystąpienie. Do zobaczenia przy innej okazji!

Dziś chciałbym zaprezentować kolejny stworzony przeze mnie przykład wykorzystania Clojure w praktyce — program Smyrna. To proste narzędzie do przeszukiwania korpusów: umożliwia łatwe zindeksowanie zbioru dokumentów w formacie HTML, wyszukanie wystąpień interesującego nas leksemu i stworzenie listy frekwencyjnej słów.

Program zrodził się z potrzeby chwili (potrzebowałem porównać wystąpienia pewnej grupy słów w różnych zestawach danych), ale uznałem, że jest na tyle użyteczny, że może przydać się nie tylko mnie. Zwłaszcza że nie było dotąd programu na wolnej licencji, który by umożliwiał łatwe przeszukiwanie własnych zbiorów polskich tekstów. Można wykorzystać Poliqarpa, w którym też maczałem palce (a raczej nurzałem ręce), jednak używanie go z własnymi zbiorami danych wymaga ekwilibrystyki w stylu dxces i jest trudne do przeskoczenia dla nietechnicznych użytkowników. Jest więc Smyrna swoistym uzupełnieniem dla Poliqarpa — stąd zresztą nazwa.

Z technicznego punktu widzenia interesujący może być sposób, w jaki skonstruowałem interfejs użytkownika. Mimo że Smyrna jest w zasadzie aplikacją desktopową, obsługuje się ją przez przeglądarkę WWW: uruchamiany jest lokalny serwerek HTTP na porcie 8080, a następnie przeglądarka z tym adresem; cała dalsza komunikacja między JavaScriptowym kodem klienckim a Clojurowym silnikiem przeszukującym odbywa się przez JSON-RPC.

W ramach ćwiczenia, kliencki kod napisałem w nowej, alternatywnej składni dla JavaScriptu, czyli zyskującym coraz większą popularność CoffeeScripcie. Eksperyment uważam za udany: kod wychodzi czytelniejszy i zwięźlejszy niż w “zwykłym” JS.

O jednej z nowych cech Clojure 1.2 dowiedziałem się dopiero niedawno, bo jej wprowadzenie przeszło właściwie bez echa. Może dlatego, że to optymalizacja niewidoczna na zewnątrz; jednak rozwiązuje ważny problem i dlatego warto mieć świadomość jej istnienia. Chodzi o locals clearing, które tłumaczę na polski jako “czyszczenie lokalnych dowiązań”.

Wyobraźmy sobie taką sytuację: mamy do wykonania skomplikowane obliczenie. Możemy je podzielić na mniejsze kroki; na każdym etapie wyliczamy nowy pośredni wynik na podstawie tylko niewielu ostatnich kroków — jednego, może dwóch. Załóżmy jeszcze, że te pośrednie wyniki są dużych rozmiarów: powiedzmy setek megabajtów. To częsty przypadek, kiedy wykonuje się np. obliczenia na dużych, gęstych macierzach: najpierw normalizujemy każdy z wektorów naszej macierzy, potem ją transponujemy, następnie liczymy jej rozkład własny i odrzucamy część wektorów własnych.

W Javie wyglądałoby to tak:

void calculate(Matrix m) {
    Matrix m1 = step1(m);
    Matrix m2 = step2(m1);
    // i tak dalej, każdy krok odwołuje się do poprzedniego
}

Jest to jednak prosta droga do pojawienia się OutOfMemoryError, o ile nie dysponujemy wystarczającą ilością pamięci, aby pomieścić wszystkie kroki. Gdy m2 jest obliczone, wartość m1 jest już niepotrzebna i w zasadzie można by zwolnić zajmowaną przez nią pamięć. Odśmiecacz jednak tego nie zrobi, dopóki wywołanie funkcji calculate nie zakończy się, ponieważ do tej pamięci odwołuje się ramka na stosie wywołań.

Zilustrujmy to uruchamialnym przykładem:

public class foo {
    public static byte[] calculate(byte[] lastStep) {
        return new byte[10485760];
    }

    public static void main(String... args) {
        byte[] a, b, c, d;
        a = calculate(null);
        b = calculate(a);
        c = calculate(b);
        d = calculate(c);
        System.out.println("OK");
    }
}

Funkcja calculate emuluje skomplikowane obliczenia, alokując za każdym razem 10-megabajtowy blok pamięci. Jeśli skompilujemy ten program i uruchomimy go w środowisku z maksymalnym rozmiarem sterty ograniczonym do 30 MB (java -Xmx30M foo), zobaczymy błąd braku pamięci.

Inaczej jest w Clojure. Odpowiednik powyższego programu wygląda tak:

(defn calculate [last-step]
  (make-array Byte/TYPE 10485760))

(defn -main [& args]
  (let [a (calculate nil)
        b (calculate a)
        c (calculate b)
        d (calculate c)]
    (println "OK")))

W Clojure 1.2 i nowszych ten program wypisze OK, nawet gdy będzie miał do dyspozycji tylko 30 MB pamięci.

Dlaczego to działa? Okazuje się, że kompilator Clojure przeprowadza statyczną analizę każdego kawałka kodu, w którym wartości są dowiązane do nazw (czyli każdego użycia formuły let), i dla każdego dowiązania sprawdza, w którym miejscu jest ono ostatni raz używane, biorąc pod uwagę wszystkie możliwe ścieżki wykonania. Natychmiast po ostatnim użyciu emitowany jest bajtkod zerujący odpowiednią zmienną (ustawiający wskaźnik na null). Innymi słowy, efekt jest taki, jakbyśmy w przykładowym kodzie w Javie wstawili instrukcję a = null; zaraz po obliczeniu b i analogicznie dalej.

O jednej z sytuacji, w których takie czyszczenie się przydaje, już powiedziałem. Innym częstym przypadkiem jest branie za punkt wyjścia długiej (być może nawet nieskończonej) leniwej sekwencji, która jest realizowana w kolejnych krokach obliczeń. Dzięki automatycznemu czyszczeniu odśmiecacz może pozbyć się pierwszych, niepotrzebnych już elementów zrealizowanej sekwencji, co umożliwia pisanie klarownego kodu bez troszczenia się o jego poprawność pamięciową.

Jak jednak napisał mi Rich Hickey, sama alokacja pamięci w momencie wiązania nazwy nie jest uważana za użycie tej nazwy. Stąd jeśli nazwa nigdy nie zostanie użyta, to odpowiadająca jej wartość nie zostanie też odśmiecona aż do opuszczenia ciała bloku let. Dlatego też nie mogłem pominąć w powyższym przykładzie argumentu last-step funkcji calculate. Jednak taki przypadek nie pojawia się w praktyce: wszak jeśli wyliczamy jakiś wynik, to nie po to, by go do niczego nie użyć!

To jest druga część minicyklu zapoczątkowanego artykułem o zipperach. Temat ten zaprezentowałem również podczas wystąpienia na spotkaniu Warszawa JUG. Dostępne są slajdy z tej prezentacji (uwaga: slajdy mają postać oskryptowanego HTML; należy je oglądać w Firefoksie lub którejś przeglądarce WebKitowej). Można również obejrzeć nagranie wideo wystąpienia, niestety ze słabą jakością dźwięku.

Problem

Jakiś czas temu zostałem poproszony o sporządzenie kilku mapek Europy pokolorowanych w różny sposób. Dostałem kilka zestawów danych, w których każdemu krajowi UE przypisana była jakaś liczba: im większa ta wartość, tym ciemniejszym odcieniem państwo miało być zaznaczone na mapce. Przykładowa pokolorowana mapka miała wyglądać tak:

Rozpocząłem od ściągnięcia łatwo edytowalnej mapy ze stron Wikimedia Commons, obliczyłem potrzebne intensywności kolorów dla pierwszego zestawu, uruchomiłem Inkscape i zabrałem się do kolorowania. Po półgodzinie żmudnego klikania zdałem sobie sprawę, że prościej i szybciej byłoby mi napisać programik w Clojure, który wygeneruje mapkę za mnie. Okazało się to zadaniem dość prostym: reszta tego postu będzie rekonstrukcją przedsięwziętych przeze mnie kroków.

SVG

Formatem źródłowego obrazka jest SVG. Wiedziałem, że to XML-owy otwarty format grafiki wektorowej, często widywałem na Wikipedii obrazy w tym formacie — jednak jego ręczna edycja to coś, z czym nie miałem do tej pory do czynienia. Szczęśliwie okazało się, że obrazek z mapkami ma prostą strukturę. Krzywa-obwiednia każdego kraju jest opisana elementem path, wyglądającym mniej więcej tak:

<path
   id="pl"
   class="eu europe"
   d="współrzędne kolejnych węzłów krzywej (bardzo dużo)" />

Warto zwrócić uwagę na atrybut id — jest to dwuliterowy skrót ISO-3166-1-ALPHA2 nazwy kraju. Na początku kodu obrazka znajduje się zresztą komentarz, który wyjaśnia użyte konwencje nazewnicze. Dysponowanie tak porządnie przygotowanymi danymi wejściowymi znakomicie ułatwiło mi pracę.

Jak się okazuje, SVG, podobnie jak HTML, używa stylów CSS do definiowania wyglądu elementów. Wszystko, co trzeba zrobić do nadania Polsce koloru czerwonego, to nadanie odpowiedniej wartości atrybutowi stylu fill:

<path
   id="pl"
   style="fill: #ff0000;"
   class="eu europe"
   d="współrzędne kolejnych węzłów krzywej (bardzo dużo)" />

Uzbrojeni w taką wiedzę, możemy rozpocząć pracę.

XML w Clojure

Podstawowym sposobem obsługi XML w Clojure jest wykorzystanie biblioteki clojure.xml, pozwalającej na parsowanie XML-a (na zasadzie DOM, tzn. do struktury w pamięci) oraz serializację, tzn. działanie w odwrotną stronę. Uruchommy więc REPL i zacznijmy od wczytania naszej mapki i sparsowania jej:

> (use 'clojure.xml)
nil
> (def m (parse "/home/nathell/eur/Blank_map_of_Europe.svg"))
[...dłuuugie oczekiwanie...]
Unexpected end of file from server
  [Thrown class java.net.SocketException]

Zaraz! Jaki znowu SocketException? Firefox wyświetla tę mapkę poprawnie, Chromium też, WTF? W tak świetnym języku, jakim jest Clojure, wszystko powinno działać od ręki?!

Cóż, język jest tak dobry, jak dobre są jego biblioteki — a jeśli chodzi o Clojure, można to rozwinąć: biblioteki Clojure są tak dobre, jak dobre są biblioteki Javy, których używają pod spodem. W tym wypadku natrafiliśmy na cechę standardowego (z pakietu javax.xml) parsera XML w Javie. Jest on restrykcyjny i stara się odrzucać dokumenty, które nie są poprawne (w sensie valid, a nie tylko well-formed). Jeśli tylko dany plik zawiera deklarację DOCTYPE, to parser javowy, a za nim clojure.xml/parse, próbuje ściągnąć z podanego adresu schemat DTD i zwalidować dokument według tego schematu. Jest to działanie z wielu względów niepożądane, zwłaszcza z punktu widzenia World Wide Web Consortium, bo to na serwerach tej organizacji przechowywane są schematy opisujące sieciowe standardy. Łatwo sobie wyobrazić, jak duży ruch sieciowy generują nadgorliwe parsery: traktuje o tym post na blogu W3C. Zapewne wielu programistów Javy zetknęło się kiedyś z tym problemem. Jest kilka rozwiązań; użyjemy najprostszego z nich, czyli po prostu… ręcznie usuniemy przeszkadzającą deklarację DOCTYPE.

> (def m (parse "/home/nathell/eur/bm.svg"))
#'user/m
> m
[...wiele ekranów liczb...]

No, tym razem udało się wczytać. Obejrzenie sparsowanej struktury jest utrudnione z uwagi na jej wielkość (można było się tego spodziewać: plik SVG waży ponad 0,5 MB!), ale z samego początku tego, co nam wypluwa REPL, widzimy, że jest to mapa. Zobaczmy, z jakich kluczy się składa:

> (keys m)
(:tag :attrs :content)

Jest to więc mapa o trzech polach: z nazw (albo z dokumentacji) można się domyślić, co zawierają. Pole :tag to nazwa elementu XML, :attrs jest mapą atrybutów tego elementu, a content — sekwencją jego podelementów, z których każdy jest znów reprezentowany przez mapę o takiej samej strukturze (względnie przez napis, jeśli jest to element napisowy):

> (:tag m)
:svg
> (:attrs m)
{:xmlns "http://www.w3.org/2000/svg", :width "680", :height "520", :viewBox "1754 161 9938 7945", :version "1.0", :id "svg2"}
> (count (:content m))
68

Tak dla wprawki, spróbujmy zapisać sparsowaną reprezentację z powrotem jako XML. Funkcja emit powinna być w stanie to zrobić, ale wypisujekl ona XML na standardowe wyjście. Możemy użyć makra with-out-str z pakietu clojure.contrib.io, aby zrzucić XML-a do pliku:

> (use 'clojure.contrib.io)
nil
> (with-out-writer "/tmp/a.xml" (emit m))
nil

Próbujemy otworzyć wynikowy obrazek w Firefoksie i…

Błąd parsowania XML: nieprawidłowo sformowany
Obszar: file:///tmp/a.xml
Numer linii: 15, kolumna 44: Updated to reflect dissolution of Serbia & Montenegro: http://commons.wikimedia.org/wiki/User:Zirland
-------------------------------------------^

Argh! Wygląda na to, że znaleźliśmy błąd w clojure.xml: elementy zawierające ampersandy nie są poprawnie serializowane, przez co późniejsze parsowanie się nie powodzi. Zgłosimy ten błąd później, a teraz usuńmy znowu doraźnie wskazaną przez Firefoksa linijkę (możemy to bezpiecznie zrobić, bo to tylko komentarz). Jeśli teraz powtórzymy nasze dotychczasowe kroki, zobaczymy, że wygenerowany XML jest wreszcie poprawny.

Kolorujemy Polskę

Widzieliśmy wcześniej, że główny element XML w naszym pliku zawiera 68 podelementów. Zobaczmy, jakie one są — wystarczą nam tagi:

> (map :tag (:content m))
(:title :desc :defs :rect :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :path :g :path :path :g :path :path :path)

Jak dotąd jest świetnie. Wygląda na to, że wszystkie opisy krajów są bezpośrednio zawarte w głównym elemencie jako podelementy. Spróbujmy znaleźć Polskę:

> (count (filter #(and (= (:tag %) :path) 
                       (= ((:attrs %) :id) "pl")) 
                 (:content m)))
1

(Ten kawałek kodu wybiera z listy podelementów m takie, których tag to path, a wartość atrybutu id to "pl" i zwraca długość takiej podlisty). Spróbujmy teraz dodać do tego elementu atrybut style, zgodnie z tym, co powiedzieliśmy wcześniej. Ze względu na niezmienność struktur danych musimy zdefiniować nowy nadrzędny element, który będzie taki sam, jak m, z tym, że odpowiedniemu podelementowi ustawimy styl:

> (def m2 (assoc m
                :content
                (map #(if (and (= (:tag %) :path)
                               (= ((:attrs %) :id) "pl"))
                        (assoc % :attrs (assoc (:attrs %) :style "fill: #ff0000;"))
                        %)
                     (:content m))))
#'user/m2
> (with-out-writer "/tmp/a.svg" (emit m2))
nil

Otwieramy utworzony plik i widzimy mapkę z Polską zaznaczoną na czerwono. Hura!

Generalizacja

Uogólnimy trochę nasz kod. Napiszemy funkcję, która pokoloruje jedno państwo, dostając na wejściu element path (podelement svg):

(defn color-state
  [{:keys [tag attrs] :as element} colorize-fn]
  (let [state (:id attrs)]
    (if-let [color (colorize-fn state)]
      (assoc element :attrs (assoc attrs :style (str "fill:" color)))
      element)))

Jest to funkcja bardzo podobna do tej anonimowej, użytej powyżej w wywołaniu map, ale różni się w kilku szczegółach. Po pierwsze, bierze dwa argumenty. Jednym jest, jak powiedzieliśmy, element XML-owy (od razu rozbity na tag i attrs: więcej o takiej notacji, zwanej destructuring (“dzielenie struktury”) można przeczytać w odpowiedniej części dokumentacji Clojure), a drugim… funkcja, która dostanie jako argument dwuliterowy kod państwa i zwróci HTML-owy opis jego koloru (lub nil, jeśli kolor dla tego państwa nie jest określony — color-state poradzi sobie z tym i zwróci element w stanie nienaruszonym).

Mając color-state, możemy łatwo napisać funkcję wyższego poziomu, która w jednym kroku przetworzy i zapisze XML:

(defn save-color-map
  [svg colorize-fn outfile]
  (let [colored-map (assoc svg :content (map #(color-state % colorize-fn) (:content svg)))]
    (with-out-writer out
      (emit colored-map))))

Testujemy:

> (save-color-map m {"pl" "#00ff00"} "/tmp/a.svg")
nil

Tym razem Polska jest zielona (jako argumentu color-state użyliśmy mapy kraj→kolor, bo mapy są w Clojure wołalne jak funkcje). Spróbujmy dorzucić niebieskie Niemcy:

> (save-color-map m {"pl" "#00ff00", "de" "#0000ff"} "/tmp/a.svg")
nil

Działa!

Problem z Wielką Brytanią

Zachęceni sukcesem, próbujemy kolorować różne kraje. Dla większości działa, ale Wielka Brytania jak była szara, tak jest, niezależnie od tego, czy podamy jej kod jako “uk”, czy jako “gb”. Zaglądamy jeszcze raz do źródła naszego obrazka. Komentarze na początku jak zwykle okazują się pomocne:

Certain countries are further subdivided the United Kingdom has gb-gbn for Great Britain and gb-nir for Northern Ireland. Russia is divided into ru-kgd for the Kaliningrad Oblast and ru-main for the Main body of Russia. There is the additional grouping #xb for the “British Islands” (the UK with its Crown Dependencies – Jersey, Guernsey and the Isle of Man)

Może więc trzeba podać “gb-gbn” i “gb-nir”, zamiast samego “gb”? Próbujemy i… też nie działa. Po chwili namysłu: no jasne! Nasze początkowe założenie, że wszystkie definicje krajów są bezpośrednimi podelementami path, okazuje się fałszywe. Trzeba to naprawić.

Dotychczas robiliśmy “płaską” transformację drzewa SVG: zamienialiśmy wszystkie podelementy elementu głównego i nic głębiej. Trzeba by zmienić wszystkie elementy path (i g, jeśli chcemy kolorować grupy takie jak Wielka Brytania), niezależnie od tego, jak głęboko siedzą w drzewie. Z pomocą przychodzi funkcja map-zipper z poprzedniego odcinka.

Zważywszy, że funkcja clojure.xml/zip-xml zwraca zipper działający na drzewach XML-owych, przepisujemy save-color-map jako:

(defn save-color-map
  [svg colorize-fn outfile]
  (let [colored-map (map-zipper #(color-state % colorize-fn) (fn [x] (#{:g :path} (:tag x))) (zip/xml-zip svg))]
    (with-out-writer out
      (emit colored-map))))

Tym razem Wielka Brytania już daje się pomalować.

Koloryzatory

Mamy już zautomatyzowany sam proces kolorowania, ale tłumaczenie konkretnych wartości liczbowych na RGB jest żmudne. W ostatniej części tego artykułu zobaczymy, jak je ułatwić: stworzymy funkcję zwracającą koloryzator, czyli funkcję nadającą się do przekazania jako argument do color-state i save-color-map (dotąd używaliśmy w tym celu map).

Zaczniemy od napisania funkcji tłumaczącej trójkę liczb na HTML-owy zapis RGB, będzie nam bowiem łatwiej pracować z liczbami całkowitymi niż napisami:

(defn htmlize-color
  [[r g b]]
  (format "#%02x%02x%02x" r g b))

Wstawmy jeszcze wywołanie htmlize-color w odpowiednim miejscu w color-state:

(defn color-state
  [{:keys [tag attrs] :as element} colorize-fn]
  (let [state (:id attrs)]
    (if-let [color (colorize-fn state)]
      (assoc element :attrs (assoc attrs :style (str "fill:" (htmlize-color color))))
      element)))

Wyobraźmy sobie teraz, że mamy tabelkę z wartościami liczbowymi dla państw, np. taką:

Państwo   Wartość
------------------
Polska    20
Niemcy    15
Holandia  30

Chcemy mieć funkcję, która przypisze każdemu krajowi kolor tym intensywniejszy, im większa wartość, przy czym intensywność ma być proporcjonalna do wartości. Dla większej ogólności załóżmy, że mamy daną parę kolorów, c1 i c2, i dla każdej ze składowych R, G i B danemu państwu przypisujemy taką wartość tej składowej, jaka jest odległość rozważanej wartości od najmniejszej wartości w naszym zestawie danych (oczywiście znormalizowana biorąc pod uwagę długości odpowiednich przedziałów).

Brzmi to zagmatwanie, ale mam nadzieję, że na przykładzie będzie widać lepiej. Tak wygląda implementacja clojurowa powyższej funkcji:

(defn make-colorizer
  [dataset ranges]
  (let [minv (apply min (vals dataset))
        maxv (apply max (vals dataset))
        progress (map (fn [[min-col max-col]] (/ (- max-col min-col) (- maxv minv))) ranges)]
    (into {}
          (map (fn [[k v]] [(.toLowerCase k) (map (fn [progress [min-color _]] (int (+ min-color (* (- v minv) progress)))) progress ranges)])
               dataset))))

Zobaczmy, jak działa na naszych przykładowych danych:

> (make-colorizer {"pl" 20, "de" 15, "nl" 30} [[0 255] [0 0] [0 0]]) 
{"pl" (85 0 0), "de" (0 0 0), "nl" (255 0 0)}

Drugi argument oznacza, że składowa czerwona koloru ma się zmieniać od 0 do 255, a zielona i niebieska mają pozostać stałe (na poziomie 0).

Tak jak żądaliśmy, Niemcy wychodzą najciemniejsze (bo mają najmniejszą wartość), Holandia najjaśniejsza (bo ma największą wartość), a Polska jest w 1/3 jasności między Niemcami a Holandią (bo 20 jest w 1/3 drogi między 15 a 30).

Podsumowanie

Aplikację stworzoną w tym artykule można dalej rozwijać w wielu kierunkach. Można stworzyć jej wersję sieciową (jak się do tego zabrać — opowiedziałem w skrócie na spotkaniu Warszawa JUG). Można pisać różne koloryzatory, np. dyskretny (stałe wartości dla różnych podprzedziałów wejściowego przedziału danych) albo “temperaturowy” (płynnie przechodzący od błękitu do czerwieni przez biel: trzeba w tym celu przejść przez przestrzeń kolorów HSV).

A jaki Wy macie pomysł na rozwinięcie przykładu? Zapraszam do komentowania i eksperymentowania! Dla tych, którym się nie chce przeklejać kodu do REPL, kompletne źródło działające z Leiningenem umieszczam na GitHub. Forki będą bardzo mile widziane.

Lubię rozwiązywać problemy przy użyciu narzędzi, których dotychczas nie znałem albo znałem tylko teoretycznie, na zasadzie “wiem, że istnieje coś takiego i do czego z grubsza służy”. Jeszcze przyjemniej jest, kiedy uzyskane rozwiązanie okazuje się czytelniejsze, zrozumialsze, szybsze albo pod innymi względami lepsze niż wersja używająca tylko dotychczasowego “arsenału”. W tych dniach zdarzyło mi się tego doświadczyć dwukrotnie, gdy pracowałem nad Fablo.

Fablo to napisany w Clojure silnik wyszukiwarki dla polskich sklepów internetowych: zna odmianę polskich wyrazów, obsługuje literówki i błędy ortograficzne. Radzi sobie też z wyrazami wpisanymi bez polskich znaków, a więc wie, że “papryka zolta” to to samo, co “papryka żółta”. Działa to na ogół zupełnie dobrze, ale wciąż ulepszamy wyszukiwarkę i eliminujemy błędy polegające na tym, że na jakieś zapytanie nie wyszukują się niektóre produkty, choć powinny. Tym razem błąd brzmiał: zapytanie “sledzie” zwraca inne wyniki niż “śledzie”.

Analiza problemu ujawniła, że algorytm odpowiedzialny za “polszczenie” zapytania powinien być stosowany szerzej. Mamy dwie implementacje pewnej struktury danych używanej w tym algorytmie: jedna z nich jest czysto funkcyjna i zbudowana z rdzennie clojurowego tworzywa — map i wektorów; druga zaś jest ukryta za fasadą używanej przez nas biblioteki Javowej o prostym interfejsie, a więc explicite do tej pory z niej nie korzystaliśmy. Algorytm polszczenia był uruchamiany tylko na pierwszej implementacji (co wystarczy w wielu przypadkach, ale nie zawsze), a powinien być na obu.

Koncepcyjnie te dwie implementacje są podobne, ale mają zupełnie różne API — zrazu wydawało mi się więc, że będę musiał pisać drugą wersję funkcji realizującej “polszczenie”. To jednak nie byłoby optymalne: duplikacja kodu oznacza dwa razy więcej okazji do popełnienia błędu i konieczność pamiętania o wprowadzeniu zmian każdorazowo w obu miejscach. Z pomocą przyszły protokoły — nowy element języka wprowadzony w Clojure 1.2.

Protokół jest czymś bardzo zbliżonym do znanego z Javy interfejsu: to zestaw deklaracji nazwanych funkcji i ich argumentów, jednak bez implementacji. Implementacje definiuje się dla konkretnych typów. Mogą to być zarówno typy definiowane w Clojure (przy użyciu konstrukcji deftype), jak i istniejące klasy Javowe. Można więc zadeklarować w protokole jakąś operację (nazwijmy ją blabalizacją), po czym zdefiniować, co oznacza blabalizowanie liczb, a co napisów. Efekt jest taki, jak gdybyśmy w Javie jakoś zmusili klasy java.lang.Integer i java.lang.String do implementowania interfejsu Blabalize; możemy wołać odpowiednią funkcję bezpośrednio na obiektach odpowiednich klas, bez żadnych wrapperów!

Zacząłem więc od zdefiniowania protokołu, opisującego dwie operacje, jakich można dokonywać na mojej strukturze danych. Potem przerobiłem implementację algorytmu “polszczącego” zapytania tak, aby korzystała tylko z tych dwóch operacji, co uniezależniło ją od implementacji “pod spodem”. Napisanie Clojurowej implementacji protokołu było proste; trudniejsze okazało się odpowiednie skorzystanie z biblioteki Javowej, ale i to udało się zrobić w miarę szybko.

Efekt: brak duplikacji kodu i tylko nieznacznie zmodyfikowana dotychczasowa wersja. A przy tym udało się nagiąć bibliotekę Javową do robienia rzeczy, do których nie była zaprojektowana, bez ingerencji w jej kod. Clojure nie przestaje mnie zadziwiać.

Innym razem zauważyłem, że od kilku commitów przy próbie uruchomienia testów jednostkowych i regresji w logach testowania pojawia się komunikat, którego zdecydowanie nie powinno tam być. Mógłbym zabrać się do tego testując okolice pojawienia się komunikatu w REPL, ale tym razem postanowiłem zrobić to inaczej. Ponieważ używamy Git do kontroli wersji, wykorzystałem narzędzie git-bisect, aby znaleźć commit wprowadzający komunikat. Potrzebuje ono do działania trzech rzeczy: identyfikatorów commitu “dobrego” i “złego” oraz skryptu, który odpowiada na pytanie, czy dany commit jest “dobry” czy “zły” (zwracającego kod wyjścia odpowiednio 0 albo 1). Skrypt wyglądał mniej więcej następująco:

#!/bin/bash
cake clean
cake deps
cake proto
sleep 10
cake release
rm *.log
make test
if grep -q "PODEJRZANY_KOMUNIKAT" fablo*log; then
  exit 1
else
  exit 0
fi

(Cake jest narzędziem, którego używamy do budowania oprogramowania; 10-sekundowa przerwa między cake proto a cake release jest remedium na błąd w cake.)

Potem wystarczyło tylko:

$ git bisect start HEAD dobry_commit --
$ git bisect run check.sh

i już wiedziałem, w którym miejscu się zepsuło, a stąd było już niedaleko do znalezienia przyczyny problemu.

Niniejszy artykuł jest pierwszym z dwuczęściowego minicyklu, stanowiącego demonstrację wykorzystania Clojure w praktyce do prostego, acz nietrywialnego zadania, na które natknąłem się w codziennej pracy. Dzisiejsza część może wydać się mało interesująca i mocno teoretyczna, ale mam nadzieję, że następny odcinek pokaże, jak można ją ciekawie wykorzystać (na razie nie zdradzę, jakie to wykorzystanie).

Planuję, że takie artykuły lub cykle zdominują Clojurową część tego bloga — będę się tu dzielił rozwiązaniami praktycznych problemów, na jakie natrafiam. Nie będzie tu artykułów w stylu “hej, jaki fajny nowy framework XYZ, napiszmy w nim Hello World przy wykorzystaniu technologii ABC!”, chyba że XYZ lub ABC będą przydatnymi narzędziami do rozwiązania problemu z życia wziętego. Bo takie rozwiązywanie w Clojure daje dużo radości: nie przypadkiem taki właśnie jest tytuł książki M. Fogusa i C. Housera.

A dziś opowiem o ciekawej strukturze danych, jaką są zippery. (Mierzi mnie trochę używanie angielskiej nazwy, ale nie potrafię wymyślić dobrego polskiego odpowiednika tego słowa; będę szczęśliwy widząc propozycje w komentarzach!) Cóż to takiego?

Zipper jest strukturą danych, dającą iluzję imperatywności przy manipulowaniu drzewami. Pamiętamy, że Clojurowe natywne struktury danych są niezmienne (immutable): jeśli mamy listę składającą się z liczb 2 i 5, to nie możemy jej w żaden sposób zmienić (np. dodać elementu) — możemy co najwyżej stworzyć na jej podstawie nową listę, która będzie zawierać wszystkie elementy listy wyjściowej i jeszcze jakiś.

Niezmienność jest bardzo przydatna (o filozoficznych podstawach takiego podejścia, które zadecydowały o jego wykorzystaniu w Clojure, można poczytać w artykule “On State and Identity”), ale wymusza myślenie w innych kategoriach. To jest to, co czasami nazywa się “myśleniem funkcyjnym”: zamiast zastanawiać się, w jaki sposób zmienić wartość naszej zmiennej, aby doprowadzić ją do pożądanego stanu, pytamy o to, jak z jednych wartości robić inne. Przy tym nigdzie nie jest powiedziane, że taki sposób myślenia jest koniecznie lepszy od imperatywnego, do którego przyzwyczajeni są programiści języków takich jak Java. Jest po prostu inny. Warto się go nauczyć, bo okazuje się, że wiele problemów się upraszcza, gdy już umysł się przestawi na taki modus operandi. Bywa jednak i tak, że o danym problemie imperatywnie myśli się wygodniej niż funkcyjnie. Tu właśnie wkraczają zippery.

Wyobraźmy sobie, że chcemy dodać liczbę 4 do konkretnego drzewa BST, tak jak na rysunku powyżej. Załóżmy chwilowo, że nie interesuje nas ogólna funkcja dodająca do BST, a tylko chcemy wstawić czwórkę w konkretne miejsce. Jak to zrobić imperatywnie?

• Zejdź dwa razy w dół w prawo (“dobierz się” do węzła 6).
• Wstaw czwórkę na lewo od bieżącego węzła.

I już. A teraz funkcyjnie — pamiętamy, że z drzewa robimy nowe drzewo:

• Nowym drzewem jest drzewo, którego korzeniem jest korzeń drzewa wyjściowego, lewym poddrzewem — lewe poddrzewo drzewa wyjściowego, a prawym poddrzewem drzewo, którego korzeniem jest korzeń prawego poddrzewa drzewa wyjściowego, lewym poddrzewem — drzewo składające się z tylko jednego węzła 4, a prawym poddrzewem — prawe poddrzewo prawego poddrzewa drzewa wyjściowego.

Pierwsze podejście jest łatwiejsze, prawda? Zipper pozwala nam zachować je prawie niezmienione, nie rezygnując przy tym z zalet niezmienności. Oto jak można by opisać dodawanie do drzewa z zipperem:

• Stwórz zipper na podstawie drzewa wyjściowego.
• Wykonaj na tym zipperze operację “zejdź w dół”, otrzymując nowy zipper.
• Wykonaj na tym zipperze operację “przejdź w prawo”, otrzymując nowy zipper.
• Wykonaj na tym zipperze operację “zejdź w dół”, otrzymując nowy zipper.
• Wykonaj na tym zipperze operację “wstaw 4 przed bieżącym elementem”, otrzymując nowy zipper.
• Wykonaj na tym zipperze operację “daj drzewo wynikowe”, otrzymując pożądane drzewo.

Clojure zawiera implementację zipperów w bibliotece standardowej (w przestrzeni nazw clojure.zip). Oto jak można by zapisać powyższy przykład w Clojure:

(def nowe-drzewo 
  (let [z1 (zip drzewo)
        z2 (down z1)
        z3 (right z2)
        z4 (down z3)
        z5 (insert-left z4 4)]
    (root z5)))

(tu explicite nazywam kolejne kroki obliczeń). Albo tak, używając makra ->:

(def nowe-drzewo 
  (-> drzewo 
      zip
      down
      right
      down
      (insert-left 4)
      root)))

Proste i wygodne. Pod spodem zipper to po prostu oryginalne drzewo plus informacja o tym, w którym miejscu drzewa w tej chwili jesteśmy, plus lista “zmian”, jakie do tej pory zostały na nim wykonane.

Rozwiązując mój problem (na razie nie zdradzam, jaki), natknąłem się na potrzebę posiadania funkcji, która działałaby jak map, ale na drzewach, a nie listach. To znaczy, przekształcałaby każdy element, niezależnie od tego, jak głęboko w drzewie siedzi, aplikując do niego jakąś funkcję, i zwracała w wyniku nowe drzewo. Co więcej, chciałem móc dodatkowo kontrolować, które węzły są zmieniane: funkcja ma dostawać dodatkowy predykat i tylko kiedy zwróci on true na wartości danego węzła, zmieniać tę wartość. Nie ma chyba takiej funkcji w standardowej bibliotece, ale dzięki zipperom można ją łatwo napisać.

Tak się szczęśliwie składa, że Clojurowe zippery mają funkcję next, która spaceruje po drzewie “w głąb”. Mając je, mogłem pomyśleć tak o swojej implementacji:

Jeśli zipper jest na końcu drzewa, to wynikiem transformacji jest wynikowe drzewo dla tego zippera, w przeciwnym razie wynikiem jest ta sama transformacja wywołana rekurencyjnie dla zippera uzyskanego przez wykonanie operacji “edit” (edycji bieżącego węzła w razie potrzeby) i “next”.

Tłumacząc to na Clojure, dostajemy:

(defn map-zipper [f pred z]
  (if (zip/end? z)
    (zip/root z)
    (recur f pred (-> z (zip/edit #(if (pred %) (f %) %)) zip/next)))))

I testujemy:

> (map-zipper inc integer? 
    (zip/vector-zip [1 [2 [3 4]] [5] [6 [[7 8 9]]]]))
[2 [3 [4 5]] [6] [7 [[8 9 10]]]]

Trzeba podać predykat integer?, bo zipper działający na zagnieżdżonych wektorach działa na poszczególnych poddrzewach, a nie tylko na liściach (które tu są liczbami). Możemy łatwo zobaczyć, jakie poddrzewa odwiedza map-zipper:

(map-zipper #(do (println %) %) 
            (constantly true) 
            (zip/vector-zip [1 [2 [3 4]] [5] [6 [[7 8 9]]]]))
[1 [2 [3 4]] [5] [6 [[7 8 9]]]]
1
[2 [3 4]]
2
[3 4]
3
4
[5]
5
[6 [[7 8 9]]]
6
[[7 8 9]]
[7 8 9]
7
8
9
[1 [2 [3 4]] [5] [6 [[7 8 9]]]]

Jacek Laskowski podaje ciekawy przykład wykorzystania monad w Clojure — aplikowanie kolejnych funkcji do wyrażenia, dopóki ma ono wartość nie będącą nil. Przykład mi się podoba, bo jest prosty, ale nie trywialny — wykorzystuje monadę maybe do eleganckiego rozwiązania rzeczywistego problemu. Jest to w dodatku problem, z którym borykają się czasem programiści piszący w Javie, co widać choćby w tym wątku.

Nie mogę powiedzieć, że rozumiem monady. Owszem, znam definicję i potrafię napisać program w Haskellu wykorzystujący monadę IO, ale każdy monadyczny kod, jaki dotychczas widziałem, dawał się zapisać równie zwięźle bez użycia monad w językach, które mniej religijnie podchodzą do niewpływania funkcji na stan świata zewnętrznego. Tak jest również w tym przypadku.

Jacek tak postawił oryginalny problem:

Napisać metodę, która zwraca walutę, dla pracownika z danego departamentu międzynarodowej korporacji. Pracownik jest przypisany do departamentu (np. poprzez mapę – >pracownik-departament), departament do kraju, a kraj do waluty. Funkcja na wejściu dostaje nazwę, identyfikator, lub cokolwiek jednoznacznie reprezentującego pracownika, a na wyjściu symbol waluty, np. dla “Jacek” powinno być “PLN”, a dla “John” “USD”, a “Tomek” i “Mateusz” dawaliby “CHF”.

Moje pierwotne rozwiązanie jest po prostu złożeniem trzech funkcji:

(defn pracownik->waluta [p] 
  (-> p pracownik->departament departament->kraj kraj->waluta))

O ile wszystkie z nich są mapami (pamiętamy, że w Clojure mapy implementują interfejs IFn, można je więc uważać za funkcje i wołać jak funkcje), to dla żadnej wartości wejściowej nie zostanie rzucony NullPointerException, ponieważ wywołanie mapy dla nieistniejącego klucza zwraca nil.

Jacek słusznie zauważa jednak, że wykonujemy w ten sposób więcej pracy niż trzeba. Jeżeli już w mapie pracownik->departament nie ma departamentu dla danego pracownika, to otrzymany nil zostanie “przepchnięty” przez pozostałe dwie mapy, zanim będzie zwrócony. Można kontrargumentować, że taka implementacja pracownik->waluta jest bardzo czytelna i mała strata wydajności jest niewielką ceną do zapłacenia za tę czytelność. Co jednak, gdy nie możemy lub nie chcemy zgodzić się na taką stratę, a jednocześnie nie chcemy stracić czytelności?

Odpowiedzią jest makro, które nazwałem and->. Działa ono tak samo, jak ->, z tą różnicą, że kolejne wartości oblicza tylko jeśli po drodze nie pojawiło się false lub nil, podobnie jak and (stąd nazwa). Oto ono:

(defmacro and-> 
  ([x] x)
  ([x form] `(when-let [y# ~x] (~form y#)))
  ([x form & more] `(when-let [y# (and-> ~x ~form)] 
                      (and-> y# ~@more))))

Implementacja jest bardzo zbliżona do zwykłego ->, którego kod w Clojure 1.2 wygląda tak. W stosunku do -> moje makro jest dla większej poglądowości trochę uproszczone i nie obsługuje konstrukcji typu (and-> mapa (get :klucz)), które normalnie rozwijane są do (get mapa :klucz).

Warto zwrócić uwagę na to, że argument makra nigdy nie jest wyliczany w jego rozwinięciu więcej niż raz; zawsze jest wiązany do lokalnego symbolu o unikatowej nazwie za pomocą when-let. Jest to jedna z reguł pozwalających unikać błędów w makrach. Szerszy opis tego problemu, występującego też w Common Lispie, można znaleźć w rozdziale 8 książki “Practical Common Lisp”.

Aktualizacja [7.12.2010]

Jak się okazuje, clojure-contrib zawiera już takie makro! Nazywa się -?> i można je znaleźć w przestrzeni nazw clojure.contrib.core. To już któryś raz, kiedy okazuje się, że jakieś użyteczne makro lub funkcja już jest w contrib i nie trzeba jej było pisać.