Teoretycznie długo o monadach (Clojure gdzieś w tle)

Trochę trwało zanim poczułem się w stanie chociażby nakreślić, czym są monady i przestrzegam, że ich zrozumienie opieram na własnych lekturach bez możliwości ich skonfrontowania z istotą żywą. Zabrałem się za ten temat przez pryzmat teorii teorii kategorii (podwojenie 'teorii' zamierzone), czyli matematycznie oraz przez pryzmat zastosowań programistycznych, czyli informatycznie. W żaden sposób nie twierdzę, że zawarte w tekście tezy są w jaki sposób właściwe dla zrozumienia pojęcia monad, a mogą wręcz doprowdzić do aktów samobójczych znawców tematu :) Niech mi to wybaczą.

Zabrałem się za temat zrozumienia monad przez serię artykułów, które zebrałem w serwisie delicious w kategorii (tym razem nie w dosłownym sensie matematycznym, a jedynie jako zgrupowanie) monads. Tam też można znaleźć mój pogląd, na każdy z przeczytanych artykułów i tam też będę odkładał kolejne.

Zrozumienie działania monad chciałbym wykorzystać do wzbogacenia swojego warsztatu programistycznego w narzędzia wykorzystywane w programowaniu funkcyjnym z praktyczną realizacją z użyciem języka Clojure. Jest wirtualna maszyna Javy z całym jej dobrodziejstwem inwentarza, jest język funkcyjny, więc nic więcej mi nie trzeba. Bazując na znanym (JVM i Java) poznaję nieznane (programowanie funkcyjne z Clojure). Tyle się mówi o poznawaniu innych paradygmatów programowania, aby wzbogacić swój warsztat, więc postawiłem na zrozumienie programowania funkcyjnego i monady wydały mi się wystarczającym wyzwaniem.

Poza w/w artykułami na delicious, dzięki uprzejmości Michała Januszewskiego, miałem przyjemność przeczytać 3 rozdziały o monadach w wydaniu Haskella w książce Real World Haskell wydawnictwa O'Reilly, które nie pomogło jednak wiele, bo przykłady były w języku, którego wcale nie znam. Dodatkowo, w przeciwieństwie do Clojure, Haskell ma leniwe (ja jednak wolę określać to jako opóźnione) wykonywanie funkcji (a może nawet w ogóle nie dojść do ich wykonania!) oraz wyłącznie funkcje czyste (bez efektów ubocznych, gdzie jedynym środowiskiem działania funkcji są dane wejściowe, a wynik przekazywany w postaci zwracanej struktury). To znaczna różnica nie tylko między Javą a Clojure czy Haskell, ale nawet między reprezentantami tej samej kategorii programowania funkcyjnego - Clojure vs Haskell.

Najbardziej przysłużyło mi się nagranie Introduction to Monads - Adam Smyczek. Przesłuchałem nagrania bodaj 10 razy do 20 minuty, z czego trzykrotnie doszedłem do samego końca, co okazało się być już jednak niewielkiej wartości merytorycznej, bo właśnie pierwsze 20 minut jest kluczowe (jakimś cudem po tych 20 minutach...zasypiałem :)). Kiedy tak wsłuchiwałem się w każde słowo wypowiadane przez niego i porównywałem z już znaną mi teorią, pojęcie monady stawało się bardziej zrozumiałe. Dzisiaj kolejny raz zajrzałem do Wikipedii, w której pod pojęciem Monad (functional programming) znajduje się wyjaśnienie informatyczne monady. Mogę powiedzieć, że wysiłki ostatniego miesiąca w obszarze monad zakończyły się co najmniej zrozumieniem wstępu na Wikipedii. Mimo swojej niewielkiej ilości pod względem treści, twierdzę, że można nazwać to niewielkim, acz znaczącym sukcesem (nawet, jeśli trwało to miesiąc i po drodze nic nie szło, co możnaby nazwać porażkami, teraz suma porażek staje się sukcesem :)). I teraz, wyjaśnienie na Wikipedii ma sens i jest faktycznie kwintesencją wprowadzenia do monad dla programistów (ale tylko tych, którym dane jest myśleć poza ramami aktualnie wykorzystywanego języka programowania, co dla wielu wśród moich czytelników sprowdzi się do Javy - obym się mylił!).

Gdyby zacząć wprowadzenie do monad matematycznie, to należałoby wskazać na dobre wprowadzenie do teorii kategorii na MIMUWowym ważniaku - Teoria kategorii dla informatyków. Proponuję zacząć od wykładu Wykład 1: Teoria kategorii jako abstrakcyjna teoria funkcji, aby po nim przejść do Wykład 11: Monady. Ech, gdyby jeszcze opublikowano nagrania z wykładów, byłoby cudnie i znacznie uprościłoby zrozumienie informatyki teoretycznej (co wierzę, że miałoby ostatecznie przełożenie na nasze projekty).

Zatem, czym są monady i czy jest się czym ekscytować?

Założenia naszego rozumowania są takie, że funkcja nie ma skutków ubocznych (całe jej środowisko jest jej przekazywane w postaci parametrów wejściowych) oraz nie zawsze musi być wykonana w miejscu jej wystąpienia w kodzie źródłowym (bo i po co, kiedy nikt nie oczekuje na zwracany przez nią wynik). To może się nie mieścić w głowie osobom z praktycznym programowaniem imperatywnym, a szczególnie obiektowym, w którym o skutki uboczne się właśnie gra. Nie raz, nie dwa, działanie funkcji to zmiana parametrów wejściowych przekazywanych przez referencję, a nie wartość, więc poza zwracanymi wartościami może dojść do zmiany przekazywanych. Innymi słowy, wielokrotne wywołanie danej funkcji z tymi samymi parametrami nie musi zwracać tego samego wyniku, mimo, że pamiętamy z lekcji matematyki, że funkcja dla danej wartości zawsze tak robi i dla tych samych danych wejściowych zwraca tę samą wartość. Zysk z takiego założenia jest prosty - można zapamiętać wynik długotrwającej funkcji i raz ją wykonując dla pewnych danych wejściowych zapomnieć o niej dla nich. Wtedy i zrównoleglanie obliczeń jest łatwiejsze, bo nie trzeba niczego synchronizować, albo niewiele. I nie piszę o wsparciu przez programistę, ale przez samo środowisko uruchomieniowe!

Przy takich założeniach można postawić sobie pytanie, jak w czystym i leniwym języku można zrealizować funkcjonalność wypisywania na ekran, albo przechowywania stanu, coś na wzór stanu globalnego programu, kiedy i ekran i stan są zabronione w programowaniu funkcyjnym? Wszystko za sprawą ich nieczystości - ekran może w danej chwili prezentować coś innego niż chwilę wcześniej, więc jako funkcja jest nieczysta. Idąc tym tropem, można właśnie potraktować ekran jako funkcję, której przekazuje się, co ma być wyświetlane. To mi przypomina rekurencję za pomocą akumulatora, gdzie zapobiega się zbyt zagnieżdżonym wywołaniom przez odnotowanie aktualnego wyniku w akumulatorze i zamianę (zamiast odłożenia) aktualnego wywołania na stosie wykonywania programu.

Matematycznie monada jest trójką z funktorem i dwoma morfizmami, które spełniają pewne założenia (patrz Definicja 11.1 [monada] w Wykład 11: Monady). To wciąż dla mnie niewiele mówiąca definicja, aczkolwiek jeśli się nie mylę, chodzi o takie przekształcenie obiektu (w sensie teorii kategorii nie programowania obiektowego) na drugi (przez morfizmy), aby nie zaburzyć jej struktury, tj. praw w nim zachodzących. Innymi słowy, mamy obiekt i wzbogacamy go, ale jego właściwości się nie zmieniają (tutaj nie jestem tego dokładnie pewien, czy dobrze się wyrażam - wybaczcie puryści językowi).

Teoretyczna informatyka przedstawia monady jako...tak, tak...trójkę składającą się z abstrakcyjnego typu opisującego akcje/działania (zamiast danych jak w warstwie danych w modelu obiektowym) oraz dwóch funkcji m-return i m-bind (w notacji Clojure). Pierwsza z nich - m-return - służy do wstrzykiwania/opakowania typu wejściowego do typu monadycznego, a m-bind rozpakowuje typ monadyczny i przekazuje wynik akcji do kolejnej (wciąż będąc w ramach przestrzeni obiektów wzbogaconych). W ten sposób możemy dostarczać dodatkowych funkcjonalności do już istniejących funkcji bez wpływu na ich implementację. Widzę tutaj analogię do interceptorów czy dekoratorów, aczkolwiek pamiętam, że wielu przestrzegało mnie przed takim (imperatywnym!) myśleniem. Cóż, na razie po prostu widzę ich analogie - przywołując pierwsze zdanie we wspomnianym już wykładzie Teoria kategorii dla informatyków "dobry matematyk to taki, który potrafi znaleźć analogie pomiędzy twierdzeniami, zaś wybitny matematyk to ten, który widzi analogie pomiędzy analogiami". Niestety nie należę do żadnej z tych kategorii :]

Jeśli wyobrazimy sobie stan zewnętrzny jako dodatkowy i ukryty parametr przekazywany między funkcjami to stan programu może być odczytany w każdej chwili właśnie z owej ukrytej struktury. Czyż nie przypomina nam to w Javie dodatkowego parametru this przekazywanego do każdej funkcji instancji (niestatycznej)?! Mam wrażenie, że to bardzo podobny mechanizm, gdzie programista rozpoczynający swoje życie programistyczne w Javie wie, że ma this, ale nie wie dlaczego. Jeszcze kolejny przykład z naszego podwórka javowego, aczkolwiek niewiele mającym związku z monadami, ale z ukrywaniem informacji już tak - generowanie domyślnego, bezparametrowego konstruktora. To też nam jest dane, bo programujemy w Javie. Język programowania to środowisko, w którym poruszamy się, aby wyrazić/zamodelować pewne czynności z życia realnego i Clojure, czy programowania funkcyjne w ogólności, możemy porównać do tego. Monady są pewną konstrukcją programistyczną, którą wielu nazywa kontenerem, jak kontener EJB w serwerze aplikacyjnym. Jeśli dopasujemy swoje modelowanie do zasad rządzących w kontenerze będzie łatwiej, ale najpierw musimy zrozumieć jego zachowanie, co już łatwym zwykle nie jest. Podobnie z monadami. To kontener, gdzie mając 2 obowiązkowe funkcje m-return i m-bind z naszą implementacją wpasowujemy się w kontrakt monadyczny. Jeśli tylko tak się stanie, możemy wyczyniać znacznie więcej, mniejszym kosztem (długofalowo, bo moje miesięczne boje wcale o tym nie świadczą). To jest cel mojej podróży w świat monad i programowania funkcyjnego - dobra zabawa, która ostatecznie ma przynieść korzyści mentalne (a jeśli jeszcze i finansowe, to tym lepiej).

Dla wytrwałych, dodatkowa porcja wiedzy nt. monad z przeczytanych artykułów.

Monada jest reprezentowana przez strukturę danych, która z kolei reprezentuje wynik działania lub samo działanie. Strukturę danych będącą podwaliną monady nazywamy monadyczną strukturą danych. W językach czystofunkcyjnych jak Haskell lub mniej restrykcyjnych jak Clojure, monady wspierają tworzenie aplikacji z jawnie zmiennym stanem, którego zmiana jest jednak niemożliwa (symuluje się ją przez kopiowanie struktur). Sam algorytm mógłby wskazywać na zachodzące zmiany w programie, a dzięki monadom są one symulowane (zaczynam przedstawiać monady jak inni, jakimś bliżej niezrozumiałym językiem - przyznaję, że sam nie wiem, o czym jeszcze piszę i wychodzi jakiś bełkot :))

Monada (chociażby w Clojure) opisana jest przez 2 obowiązkowe funkcje - m-result i m-bind oraz 2 dodatkowe - m-zero i m-plus.

m-result zamienia dowolną wartość na jej reprezentację monadyczną, wyrażoną konstrukcjami owej struktury monadycznej.
m-bind przekazuje wartość monadyczną (wyrażoną strukturą monadyczną) do funkcji jednoargumentowej, która wykonuje obliczenia (po co, wyjaśni się w przykładach, które kiedyś się w końcu pojawią - przypominam, że wciąż zgłębiam tę tajemną wiedzę i liczę na wyrozumiałość z niemałą dawką cierpliwości).

Innymi, bardziej matematycznymi słowy, acz wciąż jedynie bardzo delikarnie, trójka określa monadę.

Nieobowiązkowe funkcje to:
- m-zero reprezentująca specjalną wartość monadyczną, która odpowiada działaniu bez wyniku, np. zakończonego wyjątkiem lub po prostu zwróceniem nil.
- m-plus jest złożeniem wyników dwóch lub więcej obliczeń/działań.

Zwykle istnienie jednej implikuje (prowokuje?) istnienie drugiej, ale nie jest to obowiązkowe.

Wynika stąd, że m-result, m-bind, m-zero i m-plus operują na pewnej strukturze danych, którą wszystkie muszą respektować.

W kolejnej odsłonie zaplanowałem sobie bardziej praktyczne przedstawienie monad, przez przykłady.