Różnica między stanem, ST, IORef i MVar

92

Pracuję nad napisaniem sobie schematu w 48 godzin (mam do około 85 godzin) i dotarłem do części dotyczącej dodawania zmiennych i przypisań . W tym rozdziale jest duży skok koncepcyjny i żałuję, że nie wykonano go w dwóch krokach z dobrą refaktoryzacją pomiędzy, a nie przeskakiwaniem od razu do ostatecznego rozwiązania. Tak czy inaczej…

Stałam utracone z wielu różnych klas, które wydają się służyć temu samemu celowi: State, ST, IORef, i MVar. Pierwsze trzy są wymienione w tekście, a ostatnia wydaje się być preferowaną odpowiedzią na wiele pytań StackOverflow dotyczących pierwszych trzech. Wszystkie wydają się nosić stan między kolejnymi inwokacjami.

Co to jest i czym się od siebie różnią?


W szczególności te zdania nie mają sensu:

Zamiast tego używamy funkcji zwanej wątkami stanu , pozwalając Haskellowi zarządzać za nas stanem zagregowanym. To pozwala nam traktować zmienne zmienne tak jak w każdym innym języku programowania, używając funkcji do pobierania lub ustawiania zmiennych.

i

Moduł IORef pozwala na używanie zmiennych stanowych w monadzie IO .

Wszystko to sprawia, że ​​linia jest type ENV = IORef [(String, IORef LispVal)]zagmatwana - dlaczego druga IORef? Co się zepsuje, jeśli type ENV = State [(String, LispVal)]zamiast tego napiszę ?

John F. Miller
źródło

Odpowiedzi:

120

Monada stanu: model stanu zmiennego

Monada stanu to czysto funkcjonalne środowisko dla programów ze stanem, z prostym interfejsem API:

  • otrzymać
  • położyć

Dokumentacja w pakiecie mtl .

Monada stanu jest powszechnie używana, gdy potrzebny jest stan w pojedynczym wątku sterowania. W swojej implementacji nie używa w rzeczywistości stanu mutowalnego. Zamiast tego program jest parametryzowany przez wartość stanu (tj. Stan jest dodatkowym parametrem do wszystkich obliczeń). Stan wydaje się być zmutowany tylko w jednym wątku (i nie może być współużytkowany między wątkami).

Monada ST i STRefs

Monada ST jest ograniczonym kuzynem monady IO.

Pozwala na dowolny zmienny stan , zaimplementowany jako rzeczywista zmienna pamięć na maszynie. Interfejs API jest bezpieczny w programach pozbawionych efektów ubocznych, ponieważ parametr typu rank-2 zapobiega ucieczce wartości zależnych od stanu mutowalnego przed zakresem lokalnym.

Pozwala to na kontrolowaną zmienność w czystych programach.

Powszechnie używane w przypadku tablic mutowalnych i innych struktur danych, które są zmutowane, a następnie zamrożone. Jest również bardzo wydajny, ponieważ stan mutowalny jest „przyspieszany sprzętowo”.

Podstawowy interfejs API:

  • Control.Monad.ST
  • runST - rozpocznij nowe obliczenia efektu pamięci.
  • I STRefs : wskaźniki do (lokalnych) mutowalnych komórek.
  • Tablice oparte na ST (takie jak wektor) są również powszechne.

Pomyśl o tym jako o mniej niebezpiecznym rodzeństwie monady IO. Lub IO, gdzie możesz tylko czytać i zapisywać w pamięci.

IORef: STRefs w IO

Są to STRefs (patrz wyżej) w monadzie IO. Nie mają takich samych gwarancji bezpieczeństwa jak STRefs odnośnie lokalizacji.

MVars: IORefs z blokadami

Podobnie jak STRefs lub IORefs, ale z dołączoną blokadą, dla bezpiecznego jednoczesnego dostępu z wielu wątków. IORefs i STRefs są bezpieczne tylko w ustawieniach wielowątkowych podczas używania atomicModifyIORef(atomowa operacja porównania i zamiany). MVars to bardziej ogólny mechanizm bezpiecznego udostępniania stanu mutowalnego.

Generalnie w Haskell należy używać MVars lub TVars (komórki mutowalne oparte na STM), ponad STRef lub IORef.

Don Stewart
źródło
3
Co oznacza M w MVars i T w TVars? Zgaduję "Mutable", "Transactional". Ciekawe, jak ST oznacza stan wątku.
CMCDragonkai
10
Dlaczego mówisz, że MVarpowinno to być preferowane STRef? STRefgwarantuje, że tylko jeden wątek może go mutować (i że nie mogą wystąpić inne typy IO) - na pewno lepiej, jeśli nie potrzebuję jednoczesnego dostępu do stanu mutowalnego?
Benjamin Hodgson
@CMCDragonkai Zawsze zakładałem, że M oznacza mutex, ale nie mogę go nigdzie znaleźć udokumentowanego.
Andrew Thaddeus Martin
37

Ok, zacznę od IORef. IORefzapewnia wartość, która jest zmienna w monadzie IO. To tylko odniesienie do niektórych danych i jak każde odniesienie, istnieją funkcje, które pozwalają zmienić dane, do których się odnoszą. W Haskell wszystkie te funkcje działają w IO. Możesz myśleć o tym jak o bazie danych, pliku lub innym zewnętrznym magazynie danych - możesz pobrać i ustawić w nim dane, ale wymaga to przejścia przez IO. Powodem, dla którego IO jest w ogóle konieczne, jest to, że Haskell jest czysty ; kompilator potrzebuje sposobu, aby wiedzieć, do których danych odwołuje się w danym momencie (przeczytaj wpis na blogu sigfpe „You could have wynaleziono monady” ).

MVars są w zasadzie tym samym, co IORef, z wyjątkiem dwóch bardzo ważnych różnic. MVarjest prymitywem współbieżności, więc jest przeznaczony do dostępu z wielu wątków. Druga różnica polega na tym, że MVarjest to pudełko, które może być pełne lub puste. Więc jeśli IORef Intzawsze ma Int(lub jest na dole), MVar Intmoże mieć Intlub może być puste. Jeśli wątek spróbuje odczytać wartość z pustego MVar, będzie blokować, dopóki nie MVarzostanie wypełniony (przez inny wątek). Zasadniczo an MVar ajest odpowiednikiem an IORef (Maybe a)z dodatkową semantyką, która jest przydatna do współbieżności.

Statejest monadą, która zapewnia zmienny stan, niekoniecznie z IO. W rzeczywistości jest to szczególnie przydatne do czystych obliczeń. Jeśli masz algorytm, który używa stanu, ale go nie ma IO, Statemonada jest często eleganckim rozwiązaniem.

Istnieje również wersja State, z transformatorem monadowym StateT. Jest to często używane do przechowywania danych konfiguracyjnych programu lub stanów „stanu świata gry” w aplikacjach.

STjest czymś nieco innym. Główną strukturą danych w programie STjest STRef, który jest podobny do IORefmonady, ale z inną monadą. STOszustwo system wykorzystuje Monad typ (dalej „nici państwowe” docs wspominając) w celu zapewnienia, że dane Zmienne nie może uciec monady; to znaczy, kiedy wykonujesz obliczenia ST, otrzymujesz czysty wynik. Powodem, dla którego ST jest interesujący, jest to, że jest to prymitywna monada, taka jak IO, pozwalająca obliczeniom na wykonywanie niskopoziomowych manipulacji na tablicach i wskaźnikach. Oznacza to, że STmoże zapewnić czysty interfejs podczas wykonywania operacji niskiego poziomu na danych modyfikowalnych, co oznacza, że ​​jest bardzo szybki. Z perspektywy programu wygląda to tak, jakby STobliczenia przebiegały w oddzielnym wątku z magazynem lokalnym.

John L.
źródło
17

Inni zrobili podstawowe rzeczy, ale odpowiadając na bezpośrednie pytanie:

Wszystko to sprawia, że ​​rodzaj linii jest ENV = IORef [(String, IORef LispVal)] zagmatwany. Dlaczego druga IORef? Co się zepsuje, jeśli to zrobię type ENV = State [(String, LispVal)]?

Lisp to język funkcjonalny ze zmiennym stanem i zakresem leksykalnym. Wyobraź sobie, że zamknąłeś zmienną zmienną. Teraz masz odniesienie do tej zmiennej, które kręci się wewnątrz innej funkcji - powiedzmy (w pseudokodzie w stylu haskell) (printIt, setIt) = let x = 5 in (\ () -> print x, \y -> set x y). Masz teraz dwie funkcje - jedna wypisuje x, a druga ustawia jego wartość. Podczas oceny printIt, chcesz odnośnika nazwę X w początkowym środowisku, w którym printItzostała zdefiniowana, ale chcesz odnośnika wartość ta nazwa jest związany w środowisku, w którym printItjest nazywany (po setItmogły być nazywane dowolną liczbę razy ).

Poza dwoma IORefs są na to sposoby, ale z pewnością potrzebujesz czegoś więcej niż ten drugi typ, który zaproponowałeś, co nie pozwala na zmianę wartości, do których nazwy są przypisane w sposób leksykalny. Wygoogluj "problem funargów" dla wielu interesujących prehistorii.

sclv
źródło