Co to jest wzorzec „Free Monad + Interpreter”?

95

Widziałem ludzi rozmawiających o darmowej monadzie z tłumaczem , szczególnie w kontekście dostępu do danych. Co to za wzór? Kiedy mogę z niego skorzystać? Jak to działa i jak miałbym to wdrożyć?

Rozumiem (z postów takich jak ten ), że chodzi o oddzielenie modelu od dostępu do danych. Czym różni się od znanego wzorca repozytorium? Wydaje się, że mają taką samą motywację.

Benjamin Hodgson
źródło

Odpowiedzi:

138

Rzeczywisty wzorzec jest w rzeczywistości znacznie bardziej ogólny niż tylko dostęp do danych. Jest to lekki sposób na stworzenie języka specyficznego dla domeny, który daje AST, a następnie posiadanie jednego lub więcej tłumaczy, którzy „wykonają” AST w dowolny sposób.

Darmowa część monady jest po prostu poręcznym sposobem na uzyskanie AST, który można złożyć za pomocą standardowych funkcji monady Haskella (takich jak notacja) bez konieczności pisania dużej ilości niestandardowego kodu. Zapewnia to również, że twoja DSL jest możliwa do skomponowania : możesz zdefiniować ją w częściach, a następnie złożyć części w uporządkowany sposób, co pozwoli ci skorzystać z normalnych abstrakcji Haskella, takich jak funkcje.

Korzystanie z darmowej monady daje strukturę składanej DSL; wszystko, co musisz zrobić, to podać elementy. Po prostu piszesz typ danych, który obejmuje wszystkie działania w Twojej DSL. Te działania mogą robić wszystko, nie tylko dostęp do danych. Jeśli jednak podasz wszystkie dane dostępowe jako działania, otrzymasz AST, która określa wszystkie zapytania i polecenia do magazynu danych. Następnie możesz zinterpretować to w dowolny sposób: uruchom go na bazie danych na żywo, uruchom na próbce, po prostu zarejestruj polecenia do debugowania lub nawet spróbuj zoptymalizować zapytania.

Spójrzmy na bardzo prosty przykład, powiedzmy, magazynu kluczowych wartości. Na razie będziemy traktować zarówno klucze, jak i wartości jako ciągi, ale możesz dodawać typy przy odrobinie wysiłku.

data DSL next = Get String (String -> next)
              | Set String String next
              | End

Ten nextparametr pozwala nam łączyć działania. Możemy użyć tego, aby napisać program, który dostaje „foo” i ustawia „bar” z tą wartością:

p1 = Get "foo" $ \ foo -> Set "bar" foo End

Niestety to nie wystarczy, aby mieć sensowny DSL. Ponieważ użyliśmy nextdo komponowania, typ p1jest tej samej długości co nasz program (tj. 3 polecenia):

p1 :: DSL (DSL (DSL next))

W tym konkretnym przykładzie użycie nexttego typu wydaje się trochę dziwne, ale ważne jest, jeśli chcemy, aby nasze działania miały zmienne innego typu. Może chcemy wpisane geti set, na przykład.

Zauważ, że nextpole różni się dla każdej akcji. Wskazuje to, że możemy go użyć do utworzenia DSLfunktora:

instance Functor DSL where
  fmap f (Get name k)          = Get name (f . k)
  fmap f (Set name value next) = Set name value (f next)
  fmap f End                   = End

W rzeczywistości jest to jedyny prawidłowy sposób, aby uczynić go Functorem, więc możemy użyć derivinggo do automatycznego utworzenia instancji poprzez włączenie DeriveFunctorrozszerzenia.

Następnym krokiem jest Freesam typ. Właśnie tego używamy do reprezentowania naszej struktury AST , zbudowanej na szczycie tego DSLtypu. Możesz myśleć o tym jak o liście na poziomie typu , gdzie „minusy” po prostu zagnieżdżają funktor taki jak DSL:

-- compare the two types:
data Free f a = Free (f (Free f a)) | Return a
data List a   = Cons a (List a)     | Nil

Możemy więc wykorzystać Free DSL nextprogramy o różnych rozmiarach tego samego typu:

p2 = Free (Get "foo" $ \ foo -> Free (Set "bar" foo (Free End)))

Który ma o wiele ładniejszy typ:

p2 :: Free DSL a

Jednak faktyczne wyrażenie wszystkich jego konstruktorów jest nadal bardzo niewygodne w użyciu! W tym miejscu pojawia się część monady. Jak sugeruje nazwa „wolna monada”, Freejest to monada - o ile f(w tym przypadku DSL) jest funktorem:

instance Functor f => Monad (Free f) where
  return         = Return
  Free a >>= f   = Free (fmap (>>= f) a)
  Return a >>= f = f a

Teraz do czegoś dochodzimy: możemy użyć donotacji, aby nasze wyrażenia DSL były ładniejsze. Jedyne pytanie brzmi: po co next? Chodzi o to, aby użyć Freestruktury do kompozycji, więc po prostu wstawimy Returndla każdego następnego pola i pozwolimy, aby notacja zrobiła całą hydraulikę:

p3 = do foo <- Free (Get "foo" Return)
        Free (Set "bar" foo (Return ()))
        Free End

To jest lepsze, ale wciąż jest trochę niezręczne. Mamy Freei Returnwszędzie. Na szczęście istnieje wzorzec, który możemy wykorzystać: sposób, w jaki „podnosimy” akcję DSL Freejest zawsze taki sam - owijamy ją Freei ubiegamy się Returno next:

liftFree :: Functor f => f a -> Free f a
liftFree action = Free (fmap Return action)

Teraz, korzystając z tego, możemy napisać ładne wersje każdego z naszych poleceń i mieć pełną DSL:

get key       = liftFree (Get key id)
set key value = liftFree (Set key value ())
end           = liftFree End

Korzystając z tego, oto jak możemy napisać nasz program:

p4 :: Free DSL a
p4 = do foo <- get "foo"
        set "bar" foo
        end

Ciekawą sztuczką jest to, że chociaż p4wygląda jak mały imperatywny program, w rzeczywistości jest to wyrażenie o wartości

Free (Get "foo" $ \ foo -> Free (Set "bar" foo (Free End)))

Tak więc część wolnej monady wzorca otrzymała DSL, która produkuje drzewa składniowe z niezłą składnią. Możemy również pisać poddrzewy składane, nie używając End; na przykład możemy mieć, followktóry pobiera klucz, pobiera jego wartość, a następnie używa go jako klucza:

follow :: String -> Free DSL String
follow key = do key' <- get key
                get key'

Teraz followmożna go używać w naszych programach tak jak getlub set:

p5 = do foo <- follow "foo"
        set "bar" foo
        end

Dostajemy więc również niezłą kompozycję i abstrakcję do naszej DSL.

Teraz, gdy mamy drzewo, dochodzimy do drugiej połowy wzoru: tłumacza. Możemy zinterpretować drzewo, jednak lubimy po prostu dopasowywać do niego wzory. Pozwoliłoby nam to napisać kod na prawdziwym magazynie danych IO, a także na inne rzeczy. Oto przykład przeciwko hipotetycznemu magazynowi danych:

runIO :: Free DSL a -> IO ()
runIO (Free (Get key k)) =
  do res <- getKey key
     runIO $ k res
runIO (Free (Set key value next)) =
  do setKey key value
     runIO next
runIO (Free End) = close
runIO (Return _) = return ()

To z przyjemnością oceni każdy DSLfragment, nawet taki, który się nie kończy end. Na szczęście możemy stworzyć „bezpieczną” wersję funkcji, która akceptuje tylko programy zamknięte end, ustawiając podpis typu wejścia na (forall a. Free DSL a) -> IO (). Choć stary podpis przyjmuje wartości Free DSL adla dowolnego a (jak Free DSL String, Free DSL Inti tak dalej), ta wersja akceptuje jedynie Free DSL a, że działa dla każdej możliwej a-co możemy tworzyć tylko end. Gwarantuje to, że nie zapomnimy zamknąć połączenia, gdy skończymy.

safeRunIO :: (forall a. Free DSL a) -> IO ()
safeRunIO = runIO

(Nie możemy zacząć od podania runIOtego typu, ponieważ nie zadziała to poprawnie w przypadku naszego wywołania rekurencyjnego. Możemy jednak przenieść definicję runIOdo wherebloku safeRunIOi uzyskać ten sam efekt bez ujawniania obu wersji funkcji.)

Uruchomienie naszego kodu IOnie jest jedyną rzeczą, którą możemy zrobić. Do testów możemy chcieć uruchomić go State Mapzamiast czystego . Napisanie tego kodu jest dobrym ćwiczeniem.

Więc to jest darmowy wzorzec monady + interpretera. Wykonujemy DSL, wykorzystując swobodną strukturę monad do wykonywania wszystkich prac hydraulicznych. Możemy używać do notacji i standardowych funkcji monad z naszą DSL. Następnie, aby faktycznie z niego skorzystać, musimy jakoś to zinterpretować; ponieważ drzewo jest ostatecznie tylko strukturą danych, możemy je interpretować w dowolny sposób do różnych celów.

Kiedy używamy tego do zarządzania dostępem do zewnętrznego magazynu danych, jest on rzeczywiście podobny do wzorca repozytorium. Pośredniczy między naszym magazynem danych a naszym kodem, oddzielając je od siebie. Pod pewnymi względami jest jednak bardziej szczegółowa: „repozytorium” jest zawsze DSL z wyraźnym AST, z którego możemy następnie korzystać w dowolny sposób.

Jednak sam wzorzec jest bardziej ogólny. Może być używany do wielu rzeczy, które niekoniecznie wymagają zewnętrznych baz danych lub pamięci. Ma to sens wszędzie tam, gdzie chcesz precyzyjnej kontroli efektów lub wielu celów dla DSL.

Tikhon Jelvis
źródło
6
Dlaczego nazywa się to „wolną” monadą?
Benjamin Hodgson
14
Nazwa „darmowa” pochodzi od teorii kategorii: ncatlab.org/nlab/show/free+object, ale w pewnym sensie oznacza, że ​​jest to „minimalna” monada - że tylko prawidłowe operacje na niej są operacjami monad, ponieważ ma „ zapomniane „cała to inna struktura.
Boyd Stephen Smith Jr.
3
@BenjaminHodgson: Boyd ma całkowitą rację. Nie martwiłbym się tym zbytnio, chyba że jesteś po prostu ciekawy. Dan Piponi wygłosił świetną mowę na temat tego, co oznacza „bezpłatny” w BayHac, co warto zobaczyć. Spróbuj śledzić wraz z jego slajdami, ponieważ grafika na filmie jest całkowicie bezużyteczna.
Tikhon Jelvis
3
Nitpick: „Darmowa część monady to po prostu [mój nacisk] wygodny sposób na uzyskanie AST, który można złożyć za pomocą standardowych funkcji monady Haskella (takich jak notacja) bez konieczności pisania dużej ilości niestandardowego kodu”. To coś więcej niż „tylko” to (jak jestem pewien, że wiesz). Wolne monady są również znormalizowaną reprezentacją programu, która uniemożliwia interpreterowi rozróżnienie programów, których donotacja jest inna, ale w rzeczywistości „oznacza to samo”.
sacundim
5
@sacundim: Czy mógłbyś rozwinąć swój komentarz? Zwłaszcza zdanie „Wolne monady to także znormalizowana reprezentacja programu, która uniemożliwia interpreterowi rozróżnienie programów, których notacja jest inna, ale w rzeczywistości„ znaczy to samo ”.
Giorgio
15

Wolna monada jest w zasadzie monadą, która buduje strukturę danych w tym samym „kształcie” co obliczenia, zamiast robić coś bardziej skomplikowanego. ( Istnieją przykłady, które można znaleźć w Internecie. ) Ta struktura danych jest następnie przekazywana do fragmentu kodu, który zużywa ją i wykonuje operacje. * Nie jestem do końca zaznajomiony z wzorcem repozytorium, ale z tego, co przeczytałem , wydaje się być architekturą wyższego poziomu, a do jej wdrożenia można by użyć darmowego interpretera monady +. Z drugiej strony, darmowy interpreter monada + może być również wykorzystany do implementacji zupełnie innych rzeczy, takich jak parsery.

* Warto zauważyć, że ten wzór nie jest wyłączny dla monad i faktycznie może produkować bardziej wydajny kod dzięki darmowym aplikacjom lub darmowym strzałkom . ( Parsery są kolejnym tego przykładem ).

Dan
źródło
Przepraszam, powinienem był jaśniej powiedzieć o Repozytorium. (Zapomniałem, że nie wszyscy mają doświadczenie w systemach biznesowych / OO / DDD!). Repozytorium zasadniczo zapewnia dostęp do danych i nawadnia obiekty domeny dla Ciebie. Jest często używany razem z Dependency Inversion - możesz „podłączyć” różne implementacje Repo (przydatne do testowania lub jeśli potrzebujesz zmienić bazę danych lub ORM). Kod domeny po prostu wywołuje, repository.Get()nie wiedząc, skąd bierze obiekt domeny.
Benjamin Hodgson