Unterschied zwischen State, ST, IORef und MVar

91

Ich arbeite daran, in 48 Stunden ein Schema zu schreiben (ich bin bis zu 85 Stunden) und bin zu dem Teil über das Hinzufügen von Variablen und Zuweisungen gekommen . In diesem Kapitel gibt es einen großen konzeptionellen Sprung, und ich wünschte, es wäre in zwei Schritten mit einem guten Refactoring dazwischen gemacht worden, anstatt direkt zur endgültigen Lösung zu springen. Wie auch immer…

Ich habe mit einer Reihe von verschiedenen Klassen verloren gegangen, die den gleichen Zweck zu dienen scheinen: State, ST, IORef, und MVar. Die ersten drei werden im Text erwähnt, während die letzte die bevorzugte Antwort auf viele StackOverflow-Fragen zu den ersten drei zu sein scheint. Sie alle scheinen einen Zustand zwischen aufeinanderfolgenden Anrufungen zu haben.

Was sind diese und wie unterscheiden sie sich voneinander?


Insbesondere machen diese Sätze keinen Sinn:

Stattdessen verwenden wir eine Funktion namens Status-Threads , mit der Haskell den Gesamtstatus für uns verwalten kann. Auf diese Weise können wir veränderbare Variablen wie in jeder anderen Programmiersprache behandeln und Funktionen zum Abrufen oder Festlegen von Variablen verwenden.

und

Mit dem IORef-Modul können Sie statusbehaftete Variablen innerhalb der E / A-Monade verwenden .

All dies macht die Linie type ENV = IORef [(String, IORef LispVal)]verwirrend - warum die zweite IORef? Was wird kaputt gehen, wenn ich type ENV = State [(String, LispVal)]stattdessen schreibe ?

John F. Miller
quelle

Antworten:

119

Die Staatsmonade: ein Modell des veränderlichen Staates

Die State-Monade ist eine rein funktionale Umgebung für Programme mit State mit einer einfachen API:

  • bekommen
  • stellen

Dokumentation im mtl-Paket .

Die Statusmonade wird häufig verwendet, wenn der Status in einem einzelnen Kontrollthread benötigt wird. Bei der Implementierung wird kein veränderlicher Status verwendet. Stattdessen wird das Programm durch den Statuswert parametrisiert (dh der Status ist ein zusätzlicher Parameter für alle Berechnungen). Der Status scheint nur in einem einzelnen Thread mutiert zu sein (und kann nicht von Threads gemeinsam genutzt werden).

Die ST-Monade und STRefs

Die ST-Monade ist der eingeschränkte Cousin der IO-Monade.

Es ermöglicht einen beliebigen veränderlichen Zustand , der als tatsächlicher veränderbarer Speicher auf der Maschine implementiert ist. Die API wird in Programmen ohne Nebenwirkungen sicher gemacht, da der Parameter vom Typ Rang 2 verhindert, dass Werte, die vom veränderlichen Status abhängen, dem lokalen Bereich entgehen.

Es ermöglicht somit eine kontrollierte Veränderlichkeit in ansonsten reinen Programmen.

Wird häufig für veränderbare Arrays und andere Datenstrukturen verwendet, die mutiert und dann eingefroren werden. Es ist auch sehr effizient, da der veränderbare Zustand "hardwarebeschleunigt" ist.

Primäre API:

  • Control.Monad.ST
  • runST - Startet eine neue Berechnung des Memory-Effekts.
  • Und STRefs : Zeiger auf (lokale) veränderbare Zellen.
  • ST-basierte Arrays (wie Vektoren) sind ebenfalls üblich.

Betrachten Sie es als das weniger gefährliche Geschwister der IO-Monade. Oder IO, wo Sie nur lesen und in den Speicher schreiben können.

IORef: STRefs in IO

Dies sind STRefs (siehe oben) in der IO-Monade. Sie haben nicht die gleichen Sicherheitsgarantien wie STRefs in Bezug auf die Lokalität.

MVars: IORefs mit Sperren

Wie STRefs oder IORefs, jedoch mit angeschlossenem Schloss, für den sicheren gleichzeitigen Zugriff von mehreren Threads. IORefs und STRefs sind nur in einer Multithread-Einstellung sicher, wenn sie verwendet werden atomicModifyIORef(eine atomare Operation zum Vergleichen und Austauschen). MVars sind ein allgemeinerer Mechanismus zum sicheren Teilen des veränderlichen Zustands.

Verwenden Sie in Haskell im Allgemeinen MVars oder TVars (STM-basierte veränderbare Zellen) über STRef oder IORef.

Don Stewart
quelle
3
Was bedeutet das M in MVars und das T in TVars? Ich vermute "Mutable", "Transactional". Interessant, wie ST State Thread bedeutet.
CMCDragonkai
10
Warum MVarsollte das dem vorgezogen werden STRef? STRefgarantiert, dass nur ein Thread es mutieren kann (und dass keine anderen Arten von E / A auftreten können) - ist das sicherlich besser, wenn ich keinen gleichzeitigen Zugriff auf den veränderlichen Status benötige?
Benjamin Hodgson
@CMCDragonkai Ich habe immer angenommen, dass M für Mutex steht, aber ich kann es nirgendwo dokumentiert finden.
Andrew Thaddeus Martin
37

Ok, ich fange mit an IORef. IORefliefert einen Wert, der in der E / A-Monade veränderbar ist. Es ist nur eine Referenz auf einige Daten, und wie bei jeder Referenz gibt es Funktionen, mit denen Sie die Daten ändern können, auf die sie verweisen. In Haskell arbeiten alle diese Funktionen in IO. Sie können sich das wie eine Datenbank, eine Datei oder einen anderen externen Datenspeicher vorstellen. Sie können die darin enthaltenen Daten abrufen und festlegen. Dazu müssen Sie jedoch die E / A durchlaufen. Der Grund, warum IO überhaupt notwendig ist, ist, dass Haskell rein ist ; Der Compiler muss wissen, auf welche Daten die Referenz zu einem bestimmten Zeitpunkt verweist (lesen Sie den Blogpost von sigfpe "Sie hätten Monaden erfinden können" ).

MVars sind im Grunde dasselbe wie ein IORef, abgesehen von zwei sehr wichtigen Unterschieden. MVarist ein Parallelitätsprimitiv und daher für den Zugriff von mehreren Threads ausgelegt. Der zweite Unterschied ist, dass an MVareine Box ist, die voll oder leer sein kann. Wo also IORef Intimmer ein Int(oder unten) ist, MVar Intkann ein ein haben Intoder es kann leer sein. Wenn ein Thread versucht, einen Wert aus einem leeren Thread zu lesen MVar, wird er blockiert, bis der Wert MVargefüllt wird (von einem anderen Thread). Grundsätzlich MVar aentspricht an a einer IORef (Maybe a)zusätzlichen Semantik, die für die Parallelität nützlich ist.

Stateist eine Monade, die einen veränderlichen Zustand liefert, nicht unbedingt mit IO. In der Tat ist es besonders nützlich für reine Berechnungen. Wenn Sie einen Algorithmus haben, der den Status verwendet, aber nicht IO, ist eine StateMonade oft eine elegante Lösung.

Es gibt auch eine Monadentransformator-Version von State , StateT. Dies wird häufig verwendet, um Programmkonfigurationsdaten oder Statusarten mit "Spielweltstatus" in Anwendungen zu speichern.

STist etwas etwas anderes. Die Hauptdatenstruktur in STist die STRef, die wie eine, IORefaber mit einer anderen Monade ist. Die STMonade verwendet Tricks des Typsystems (die in den Dokumenten erwähnten "Status-Threads"), um sicherzustellen, dass veränderbare Daten der Monade nicht entkommen können. Das heißt, wenn Sie eine ST-Berechnung ausführen, erhalten Sie ein reines Ergebnis. Der Grund, warum ST interessant ist, ist, dass es sich um eine primitive Monade wie IO handelt, die es Berechnungen ermöglicht, Manipulationen auf niedriger Ebene an Bytearrays und Zeigern durchzuführen. Dies bedeutet, dass STeine reine Schnittstelle bereitgestellt werden kann, während Operationen auf niedriger Ebene für veränderbare Daten verwendet werden, was bedeutet, dass dies sehr schnell ist. Aus Sicht des Programms ist es so, als würde die STBerechnung in einem separaten Thread mit threadlokalem Speicher ausgeführt.

John L.
quelle
17

Andere haben die Kernaufgaben erledigt, aber um die direkte Frage zu beantworten:

All dies macht den Leitungstyp ENV = IORef [(String, IORef LispVal)] verwirrend. Warum das zweite IORef? Was wird kaputt gehen, wenn ich es type ENV = State [(String, LispVal)]stattdessen tue ?

Lisp ist eine funktionale Sprache mit veränderlichem Zustand und lexikalischem Umfang. Stellen Sie sich vor, Sie haben eine veränderbare Variable geschlossen. Jetzt haben Sie einen Verweis auf diese Variable, der in einer anderen Funktion herumhängt - beispielsweise (im Pseudocode im Haskell-Stil) (printIt, setIt) = let x = 5 in (\ () -> print x, \y -> set x y). Sie haben jetzt zwei Funktionen - eine druckt x und eine legt ihren Wert fest. Wenn Sie bewerten printIt, möchten Sie die Nachschlag Namen von x in der Anfangs Umgebung , in der printItfestgelegt wurde, aber Sie wollen den Lookup - Wert , dass Namen in der Umgebung , in der gebunden ist , printItwird genannt (nach setItbeliebig oft aufgerufen worden sein ).

Neben den beiden IORefs gibt es Möglichkeiten, dies zu tun, aber Sie benötigen sicherlich mehr als den von Ihnen vorgeschlagenen Typ, sodass Sie die Werte, an die Namen gebunden sind, nicht lexikalisch ändern können. Google das "Funargs-Problem" für eine ganze Menge interessanter Vorgeschichte.

sclv
quelle