Monada Stanu

Nie miałem w tym tygodniu czasu na opisanie kolejnej części mojego interpretera, ponieważ go pisałem i napisałem już tak dużo, że w większości przypadków działa. Aby to uczcić w celach testowych napisałem w moim własnym języku monadę stanu, o której opowiem poniżej.

Jeśli potrzebujesz nieco informacji czym w ogóle jest monada, to zachęcam do przeczytania pierwszych dwóch sekcji mojego blogposta o monadach.

Czym jest monada stanu? Jest to monada, która wraz z obliczeniami przenosi pewien stan. Może to być przydatne w pisaniu bardziej imperatywnych programów w języku funkcyjnym.

Moja monada będzie miała wbudowaną obsługę błędów, więc zacznę od zadeklarowania typu danych rozróżniającego sukces od błędu

data Result<e, a> =
    | Just of a
    | Error of e

Następnie zadeklaruję typ danych będący sercem monady

data MonadState<a, e, s> = State of (s -> (Result<e,a> * s))

Czyli nasza monada jako wewnętrzny stan ma funkcję, która przyjmuje stan s, robi obliczenia i zwraca wynik (lub błąd) oraz nowy stan.

Następnie zadeklarujemy kilka głównych funkcji tej monady.

Pomocnicze funkcje do wyciągania funkcji z konstruktora State oraz uruchomienia jej z pewnym stanem

let stateFun m =
    match m with
    | State(f) -> f

let runState m s = stateFun(m)(s)
let evalState m s = let (a,ss) = runState(m,s) in a
let evalOnlyState m s = let (a,ss) = runState(m,s) in ss

Funkcje return i bind opisałem mniej więcej w poprzednim blogpoście o monadach. W skrócie: return zwraca wartość nie zmieniając stanu, bind wykonuje monadę m i jej wynik przekazuje do funkcji k, która zwraca nową monadę i tą też wykonujemy. No i mamy dodatkowo fail który jest jak return tylko dla zgłaszania błędów.

let return x = State(\s -> (Just(x),s))

let fail e = State(\s -> (Error(e), s))

@bind :: MonadState<a,e,s> -> (a -> MonadState<b,e,s>) -> MonadState<b,e,s>
let bind m k =
    let cont s =
        let (a, ss) = runState(m, s)
        match a with
        | Just(x) -> runState(k(x), ss)
        | Error(e) -> (Error(e), ss)
    State(cont)

Następnie mamy dwie monady do zarządzania stanem, czyli get i put

let get = State(\s -> (Just(s),s))
let put s = State(\_ -> (Just(()),s))

A żeby łatwo się tych monad używało to dołożymy sobie jeszcze operatory

let bindDo m k = bind(m, (\_ -> k))

let (>>=) = bind
let (>>) = bindDo

let null = return(())

A teraz czas na funkcję main, która przetestuje działanie monady

let main args =
    let sum x = get >>= (\s -> return(s+x)) >>= put
    let sums = fold(\prev x -> prev >> sum(x), null, [1..10])
    
    do printStr("Suma [1..10] od zera:")
    do print(evalOnlyState(sums,0))     //55
    
    do printStr("Suma [1..10] od 8:")
    do print(evalOnlyState(sums,8))     //63

    do printStr("")

    let divide x =
        let div s =
            if x == 0 then fail("Division by zero") 
            else return(s/x)
        get >>= div >>= put
    let division = fold(\prev x -> prev >> divide(x), null)
    
    do printStr("Podzielenie 8 przez [2,2,2]:")
    do print(evalOnlyState(division([2,2,2]), 8))   //1.0

    do printStr("Podzielenie 8 przez [2,0,2] (+stan w momencie błędu):")
    do print(runState(division([2,0,2]), 8))        //(Error("Division by zero"), 4.0)
    0

Ogólne działanie jest takie: weź liczbę ze stanu, zadziałaj na niej działaniem (najpierw +, potem /) i odłóż z powortem do stanu. Taką monadę uruchamiamy z pewnym stanem początkowym i otrzymujemy wynik.

Tutaj widzimy dosyć proste zastosowanie monady stanu, ale mogą one być dużo bardziej złożone. Ja w moim interpreterze też korzystam z monady stanu podczas sprawdzania typów, ale jest to bardziej zaawansowana sprawa. Wykorzystuję Haskellowe transformatory monad, mianowicie StateT wewnątrz którego działa monada IO. Ale to jest Haskell.

data InferenceState = InferenceState {
        subst_ :: Substitution,
        counter :: Int,
        recordStack :: [Assumption],
        types_ :: [(Ident, Type)],
        viewTypes_ :: [Ident]
    } deriving (Eq, Show)

type TI = StateT InferenceState IO

Za jakieś dwa tygodnie powinienem być już w stanie wrzucić mój interpreter na GitHub.

Podziel się: