Pytanie Symulacja interakcji obiektów stanowych w Haskell


Obecnie piszę program Haskell, który obejmuje symulację abstrakcyjnej maszyny, która ma stan wewnętrzny, pobiera dane wejściowe i podaje wyniki. Wiem, jak zaimplementować to przy użyciu monady stanu, co skutkuje znacznie czystszym i łatwiejszym w zarządzaniu kodem.

Moim problemem jest to, że nie wiem, jak wyciągnąć tę samą sztuczkę, gdy mam dwa (lub więcej) obiektów stanowych wchodzących w interakcje ze sobą. Poniżej przedstawiam bardzo uproszczoną wersję problemu i przedstawię, co mam do tej pory.

Dla tego pytania załóżmy, że wewnętrzny stan maszyny składa się z pojedynczego rejestru liczb całkowitych, więc jego typem danych jest

data Machine = Register Int
        deriving (Show)

(Rzeczywista maszyna może mieć wiele rejestrów, wskaźnik programu, stos wywołań itp., Ale na razie nie martwmy się.) Po poprzednie pytanie Wiem, jak zaimplementować maszynę za pomocą monady stanu, aby nie musiałem jawnie przekazywać jej stanu wewnętrznego. W tym uproszczonym przykładzie implementacja wygląda tak, po zaimportowaniu Control.Monad.State.Lazy:

addToState :: Int -> State Machine ()
addToState i = do
        (Register x) <- get
        put $ Register (x + i)

getValue :: State Machine Int
getValue = do
        (Register i) <- get
        return i

To pozwala mi pisać takie rzeczy jak

program :: State Machine Int
program = do
        addToState 6
        addToState (-4)
        getValue

runProgram = evalState program (Register 0)

To dodaje 6 do rejestru, a następnie odejmuje 4, a następnie zwraca wynik. Monada stanu śledzi wewnętrzny stan urządzenia, aby kod "programu" nie musiał go jawnie śledzić.

W stylu zorientowanym obiektowo w imperatywnym języku, ten "program" może wyglądać jak kod

def runProgram(machine):
    machine.addToState(6)
    machine.addToState(-4)
    return machine.getValue()

W takim przypadku, jeśli chcę symulować współdziałanie dwóch komputerów, mogę napisać

def doInteraction(machine1, machine2):
    a = machine1.getValue()
    machine1.addToState(-a)
    machine2.addToState(a)
    return machine2.getValue()

który ustawia machine1do stanu 0, dodając wartość do machine2jest stan i zwraca wynik.

Moje pytanie brzmi po prostu, jaki jest paradygmatyczny sposób pisania tego rodzaju imperatywnego kodu w Haskell? Początkowo myślałem, że potrzebuję połączyć dwie monady stanów, ale po podpowiedzi Benjamina Hodgsona w komentarzach zdałem sobie sprawę, że powinienem był to zrobić z monadą pojedynczego stanu, w której stan jest krotką zawierającą obie maszyny.

Problem polega na tym, że nie wiem jak to wdrożyć w ładnym, czystym stylu imperatywu. Obecnie mam następujące, które działa, ale jest nieeleganckie i kruche:

interaction :: State (Machine, Machine) Int
interaction = do
        (m1, m2) <- get
        let a = evalState (getValue) m1
        let m1' = execState (addToState (-a)) m1
        let m2' = execState (addToState a) m2
        let result = evalState (getValue) m2'
        put $ (m1',m2')
        return result

doInteraction = runState interaction (Register 3, Register 5)

Podpis typu interaction :: State (Machine, Machine) Int jest miłym bezpośrednim tłumaczeniem deklaracji funkcji Pythona def doInteraction(machine1, machine2):, ale kod jest niestabilny, ponieważ korzystałem z funkcji wątku poprzez funkcje z użyciem jawnego let wiązania. Wymaga to wprowadzenia nowej nazwy za każdym razem, gdy chcę zmienić stan jednego z komputerów, co z kolei oznacza, że ​​muszę ręcznie śledzić, która zmienna reprezentuje najbardziej aktualny stan. W przypadku dłuższych interakcji może to spowodować, że kod będzie podatny na błędy i trudny do edycji.

Spodziewam się, że wynik będzie miał coś wspólnego z soczewkami. Problem polega na tym, że nie wiem, jak uruchomić monadyczną akcję tylko na jednej z dwóch maszyn. Obiektywy mają operatora <<~ którego dokumentacja mówi "Uruchom monadyczną akcję i ustaw cel obiektywu na jego wynik", ale ta akcja zostanie uruchomiona w bieżącej monadzie, gdzie stan jest typu (Machine, Machine)zamiast Machine.

Więc w tym momencie moje pytanie brzmi: jak mogę zaimplementować interaction funkcja powyżej w bardziej imperatywnym / obiektowym stylu, przy użyciu stanowych monad (lub jakiejś innej sztuczki), aby pośrednio śledzić wewnętrzne stany tych dwóch maszyn, bez konieczności wyraźnego przekazywania stanów wokół?

Wreszcie zdaję sobie sprawę, że chęć napisania kodu obiektowo zorientowanego w czysto funkcjonalnym języku może być znakiem, że robię coś złego, więc jestem bardzo otwarty na to, że pokazany jest inny sposób myślenia o problemie symulacji wielu interakcji stanowych ze sobą. Zasadniczo po prostu chcę poznać "właściwą drogę", aby podejść do tego rodzaju problemu w Haskell.


14
2017-10-02 03:50


pochodzenie


znalazłem tę stronę Gabriel Gonzales która ma inne podejście niż wyobrażałem sobie. Używa monady jednego stanu, gdzie stan jest "wszechświatem" zawierającym wszystkie obiekty i używa soczewek do wybierania i modyfikowania obiektów z wnętrza tego wszechświata. Ten pomysł wydaje się ma sens dla mojej aplikacji, więc myślę, że przejdę przez to, jeśli nie otrzymam tutaj żadnej odpowiedzi. - Nathaniel
Tak, metoda Gonzalesa jest sposobem na zrobienie tego. Jest to również najbardziej bezpośrednie tłumaczenie Twojego Pythona. def doInteraction(machine1, machine2) staje się doInteraction :: State (Machine, Machine) Int - Benjamin Hodgson♦
@BenjaminHodgson dziękuję za bardzo przydatny komentarz - z jakiegoś powodu nie myślałem o umieszczeniu ich w krotce i wyobrażałem sobie coś znacznie bardziej skomplikowanego. Ten mały szturchańca ustawia mnie we właściwym kierunku. - Nathaniel
@BenjaminHodgson powiedział to, zdałem sobie sprawę, że nie wiem jak wdrożyć ciało tej funkcji w imperatywnym stylu. Jeśli chcesz dalej pomagać, zobacz edycję na końcu mojego pytania. - Nathaniel
Za pomocą leniwy  State Symulacja abstrakcyjnej maszyny wydaje mi się bardzo dziwna. Czy na pewno nie chcesz używać zwykłego "ścisłego" State? Stawiam tam przerażające cytaty, ponieważ ich ścisłość wynika po prostu z analizy scen na parach, zamiast robić coś dziwnego. Leniwy State jest dziwny. - dfeuer


Odpowiedzi:


Myślę, że dobra praktyka podpowiadałaby, że powinieneś zrobić System typ danych do zawijania dwóch maszyn, a następnie równie dobrze można z nich korzystać lens.

{-# LANGUAGE TemplateHaskell, FlexibleContexts #-}

import Control.Lens
import Control.Monad.State.Lazy

-- With these records, it will be very easy to add extra machines or registers
-- without having to refactor any of the code that follows
data Machine = Machine { _register :: Int } deriving (Show)
data System = System { _machine1, _machine2 :: Machine } deriving (Show)

-- This is some TemplateHaskell magic that makes special `register`, `machine1`,
-- and `machine2` functions.
makeLenses ''Machine
makeLenses ''System


doInteraction :: MonadState System m => m Int
doInteraction = do
    a <- use (machine1.register)
    machine1.register -= a
    machine2.register += a
    use (machine2.register)

Ponadto, aby przetestować ten kod, możemy sprawdzić w GHCi, że robi to, co chcemy:

ghci> runState doInteraction (System (Machine 3) (Machine 4))
(7,System {_machine1 = Machine {_register = 0}, _machine2 = Machine {_register = 7}})

Zalety:

  • Korzystając z rekordów i lens, nie będzie refaktoryzacji, jeśli zdecyduję się dodać dodatkowe pola. Na przykład powiedz "chcę" trzeci maszyna, to wszystko, co robię, to zmienić System:

    data System = System
      { _machine1, _machine2, _machine3 :: Machine } deriving (Show)
    

    Ale nic w moim istniejącym kodzie się nie zmieni - teraz będę mógł go użyć machine3 jak używam machine1 i machine2.

  • Używając lensMogę łatwiej skalować do struktur zagnieżdżonych. Zauważ, że właśnie uniknąłem bardzo prostego addToState i getValue działa całkowicie. Ponieważ Lens jest właściwie tylko funkcją, machine1.register jest zwykłym składem funkcji. Na przykład powiedzmy, że chcę, aby maszyna miała teraz szyk rejestrów, a następnie uzyskanie lub ustawienie poszczególnych rejestrów jest nadal proste. Po prostu modyfikujemy Machine i doInteraction:

    import Data.Array.Unboxed (UArray)
    data Machine = Machine { _registers :: UArray Int Int } deriving (Show)
    
    -- code snipped
    
    doInteraction2 :: MonadState System m => m Int
    doInteraction2 = do
        Just a <- preuse (machine1.registers.ix 2) -- get 3rd reg on machine1
        machine1.registers.ix 2 -= a               -- modify 3rd reg on machine1
        machine2.registers.ix 1 += a               -- modify 2nd reg on machine2
        Just b <- preuse (machine2.registers.ix 1) -- get 2nd reg on machine2
        return b
    

    Zauważ, że jest to równoważne funkcji podobnej do następującej w Pythonie:

    def doInteraction2(machine1,machine2):
      a = machine1.registers[2]
      machine1.registers[2] -= a
      machine2.registers[1] += a
      b = machine2.registers[1]
      return b
    

    Możesz ponownie przetestować to w GHCi:

    ghci> import Data.Array.IArray (listArray)
    ghci> let regs1 = listArray (0,3) [0,0,6,0]
    ghci> let regs2 = listArray (0,3) [0,7,3,0]
    ghci> runState doInteraction (System (Machine regs1) (Machine regs2))
    (13,System {_machine1 = Machine {_registers = array (0,3) [(0,0),(1,0),(2,0),(3,0)]}, _machine2 = Machine {_registers = array (0,3) [(0,0),(1,13),(2,3),(3,0)]}})
    

EDYTOWAĆ

PO określił, że chciałby mieć sposób na osadzenie State Machine a do a State System a. lens, jak zawsze, ma taką funkcję, jeśli zaczniesz wystarczająco głęboko kopać. zoom (i jego rodzeństwo magnify) zapewniają udogodnienia umożliwiające "powiększanie" na zewnątrz / w dół State/Reader (To ma sens tylko pomniejszyć State i powiększyć do Reader).

Następnie, jeśli chcemy wdrożyć doInteraction zachowując się jak czarne skrzynki getValue i addToState, otrzymujemy

getValue :: State Machine Int
addToState :: Int -> State Machine ()

doInteraction3 :: State System Int
doInteraction3 = do
  a <- zoom machine1 getValue     -- call `getValue` with state `machine1`
  zoom machine1 (addToState (-a)) -- call `addToState (-a)` with state `machine1` 
  zoom machine2 (addToState a)    -- call `addToState a` with state `machine2`
  zoom machine2 getValue          -- call `getValue` with state `machine2`

Zauważ jednak, że jeśli to zrobimy, naprawdę musimy zaangażować się w konkretny transformator Monady (w przeciwieństwie do generycznego MonadState), ponieważ nie wszystkie sposoby przechowywania stanu będą musiały być koniecznie "powiększane" w ten sposób. To mówi, RWST jest kolejnym transformatorem typu Monad obsługiwanym przez zoom.


14
2017-10-04 16:46



Dzięki, jest blisko tego, co chcę zrobić. Uczę się soczewek i mam już prawie tak daleko. Miejsce, w którym utknąłem, to miejsce, w którym piszesz machine2.register += a, Chcę napisać coś w stylu machine2 ~. addToState a, gdzie ~. w zasadzie to zrobię runState addToState [value pointed at by the lens], następnie zastąp wartość wskazywaną przez obiektyw nowym stanem i zwróć wynikową wartość. Powodem jest to, że w rzeczywistości nie chcę dodawać i odejmować od rejestrów, ale wykonywać skomplikowane działania, które zmieniają stan Maszyny i zwracają wartość. - Nathaniel
@ Nataniel robi <~ robić, co chcesz, przez przypadek? Możesz wtedy zrobić coś takiego machine1.register <~ randomIO.... Jeśli nie o to ci chodzi, czy mógłbyś podać dokładniejszy przykład? - Alec
Nie poniewaź <~uruchamia akcję w obecnej monadzie, a więc spodziewa się addToState mieć typ State System Int zamiast State Machine Int. Chcę móc zadzwonić addToState, zrealizowane jak w moim pytaniu, z wnętrza doInteraction i zaktualizuj tylko jedną z dwóch Maszyn. Zastanowię się, jak zaktualizować pytanie, aby wyjaśnić to dokładniej, a dam ci znać, kiedy to zrobię. - Nathaniel
Może to mniej mylący sposób na wyrażenie tego: wyobraź sobie, że chciałem zadzwonić runProgram na jednej z Maszyn w Systemie i chciałem nie tylko tego uaktualnić stan Maszyny, ale także chciałem uzyskać wynik, że program wróci. Jak to zrobić? - Nathaniel
@ Nataniel Edytowałem swoją odpowiedź na to, czego szukam. Jestem ciekaw, czy ktokolwiek ma prostszy sposób ... - Alec


Jedną z opcji jest przekształcenie przekształceń stanu w czyste funkcje Machine wartości:

getValue :: Machine -> Int
getValue (Register x) = x

addToState :: Int -> Machine -> Machine
addToState i (Register x) = Register (x + i)

Wtedy możesz je podnieść State w razie potrzeby, pisanie State działania na wielu komputerach takich jak:

doInteraction :: State (Machine, Machine) Int
doInteraction = do
  a <- gets $ getValue . fst
  modify $ first $ addToState (-a)
  modify $ second $ addToState a
  gets $ getValue . snd

Gdzie first (resp. second) jest funkcją z Control.Arrow, używane tutaj z typem:

(a -> b) -> (a, c) -> (b, c)

Oznacza to, że modyfikuje on pierwszy element krotki.

Następnie runState doInteraction (Register 3, Register 5) produkuje (8, (Register 0, Register 8))zgodnie z oczekiwaniami.

(Ogólnie rzecz biorąc, myślę, że można by zrobić takie "powiększanie" na wartościach podrzędnych za pomocą soczewek, ale nie jestem na tyle znajomy, aby podać przykład).


5
2017-10-04 04:14





Możesz także użyć biblioteki "Gabiony Gabriela Gonzalesa" dla przypadku, który zilustrowałeś. Samouczek do biblioteki jest jednym z najlepszych fragmentów dokumentacji Haskella.

Poniżej przedstawiono prosty przykład (nietestowany).

-- machine 1 adds its input to current state
machine1 :: (MonadIO m) => Pipe i o m ()
machine1 = flip evalStateT 0 $ forever $ do
               -- gets pipe input
               a <- lift await
               -- get current local state
               s <- get
               -- <whatever>
               let r = a + s
               -- update state
               put r
               -- fire down pipeline
               yield r

-- machine 2 multiplies its input by current state
machine2 :: (MonadIO m) => Pipe i o m ()
machine2 = flip evalStateT 0 $ forever $ do
               -- gets pipe input
               a <- lift await
               -- get current local state
               s <- get
               -- <whatever>
               let r = a * s
               -- update state
               put r
               -- fire down pipeline
               yield r

Możesz następnie połączyć za pomocą operatora> ->. Przykładem byłoby biec

run :: IO ()
run :: runEffect $ P.stdinLn >-> machine1 >-> machine2 >-> P.stdoutLn

Zauważ, że jest to możliwe, chociaż trochę bardziej zaangażowane w dwukierunkowe rury, co zapewnia komunikację między obydwoma maszynami. Korzystając z niektórych innych ekosystemów rur, możesz także mieć asynchroniczne przewody do modelowania niedeterministycznej lub równoległej pracy maszyn.

Wierzę, że to samo można osiągnąć dzięki bibliotece przewodników, ale nie mam z nią zbyt dużego doświadczenia.


4
2017-10-10 10:49



To wygląda bardzo ładnie. Wydaje się, że bardziej odpowiada to programistom niż modelom opartym na obiektach, które miałem na myśli. (Z grubsza rzecz biorąc, różnica polega na tym, że w coroutine jest to wybór obiektu stanowego, co należy zrobić dalej, podczas gdy w OOP wybór dokonywany jest przez funkcję wywołującą.) Coroutines są bardzo użyteczną funkcją, której brakuje w większości imperatywnych języków, więc "Bardzo się cieszę, że wiem, że to istnieje w Haskell. - Nathaniel
Tak, jest to inny model. Pozwala na samodzielne zapisywanie zachowań maszyn i modelowanie ich interakcji poprzez ich łączenie, zamiast pisania programu na najwyższym poziomie. Być może nie jest to oczywiście to, o co prosiłeś, ale jest przyjemne. Uważam, że jest to przydatne do robienia stanowych potoków DSP, ponieważ pozwala skupić się tylko na jednym algorytmie na raz. - OllieB