The difference between the state, ST, IORef and MVar

Question

I work through. Write yourself a chart in 48 hours (I'm up to about 85 hours), and I got the part about adding variables and assignments . There is a big conceptual leap in this chapter, and I would like it to be done in two stages with good refactoring between them, and not with a direct exit to the final solution. Anyway...

I got lost with several different classes that seem to fulfill the same goal: State , ST , IORef and MVar . The first three are mentioned in the text, while the latter seems to be the preferred answer to many of StackOverflow's questions about the first three. It seems that they all carry a state between successive calls.

What are each of them and how do they differ from each other?

---

In particular, these sentences do not make sense:

Instead, we use a function called state flows, allowing Haskell to manage aggregate state for us. This allows us to consider variable variables, as in any other programming language, using functions to get or set variables.

and

The IORef module allows the use of state variables inside the IO monad .

All this makes the string type ENV = IORef [(String, IORef LispVal)] confusing - why the second IORef ? What will break if I write type ENV = State [(String, LispVal)] instead?

Answer 1

State Monad: a model of a volatile state

The state monad is a purely functional environment for state programs with a simple API:

• receive
• to place

Documentation in the mtl package .

State monad is usually used when it requires a state in a single control flow. It actually does not use a volatile state in its implementation. Instead, the program is parameterized with a state value (i.e., State is an additional parameter for all calculations). The state only seems to be mutated in one thread (and cannot be shared between threads).

Convent ST and STRefs

The ST monad is a limited cousin of the IO monad.

It allows an arbitrary mutable state implemented as an actual mutable memory on a machine. The API becomes safe in programs without side effects, since a rank-2 parameter prohibits values ​​that depend on the changing state from shielding the local area.

Thus, it allows you to control the variability in other clean programs.

Commonly used for mutable arrays and other data structures that are mutated and then frozen. It is also very effective, since the volatile state is "hardware acceleration."

Primary API:

• Control.Monad.ST
• runST - start a new calculation of the memory effect.
• And STRefs : pointers to (local) mutable cells.
• ST-based arrays (such as a vector) are also widespread.

Think of it as a less dangerous brother from the IO monad. Or IO, where you can only read and write to memory.

IORef: STRIF in IO

This is STREF (see above) in the IO monad. They do not have the same security guarantees, such as STRef on locality.

MVars: IORef with locks

Like STRefs or IORefs, but with an attached lock for secure simultaneous access from multiple threads. IORefs and STRef are safe only with multi-threaded configuration when using atomicModifyIORef (comparison and replacement operation). MVars is a more general mechanism for the secure exchange of mutable state.

Typically, in Haskell, use MVars or TVars (STM mutable cells), on top of STRef or IORef.

Answer 2

Ok, I'll start with IORef . IORef provides a value that is mutable in the IO monad. This is just a link to some data, and like any link, there are functions that let you change the data that it refers to. In Haskell, all these functions work in IO . You can think of it as a database, file or other external data storage - you can get and install data in it, but for this you need to go through IO. The reason IO is needed at all is because Haskell is clean ; the compiler needs a way to find out what data the link points to at any given time (read sigfpe "You could have come up with monads" blogpost).

MVar is basically the same as IORef, except for two very important differences. MVar is a concurrency primitive, so it is designed to be accessed from multiple threads. The second difference is that MVar is a field that can be full or empty. Therefore, when IORef Int always has Int (or at the bottom), MVar Int may have Int , or it may be empty. If a thread tries to read a value from an empty MVar , it will block until the MVar is full (with another thread). Basically, MVar a equivalent to IORef (Maybe a) with additional semantics that are useful for concurrency.

State is a monad that provides mutable state, not necessarily with IO. In fact, this is especially useful for pure computing. If you have an algorithm that uses state but not IO , the State monad is often an elegant solution.

There is also a monad transformer version, StateT . This is often used to store program configuration data or game state states in applications.

ST little different. The basic data structure in ST is STRef , which is similar to IORef , but with a different monad. The ST monad uses the type system trickery (“state flows” mentioned in the documents) to ensure that volatile data cannot escape the monad; that is, when you start the ST calculation, you get a clean result. The reason ST is interesting is that it is a primitive monad, such as IO, which allows computations to perform low-level manipulations on bytes and pointers. This means that ST can provide a clean interface when using low-level operations on mutable data, which is very fast. From the point of view of the program, it is as if the ST calculation is performed in a separate thread with local thread storage.

Answer 3

Others have done basic things, but to answer a direct question:

All this makes the line type ENV = IORef [(String, IORef LispVal)] is confusing. Why the second IORef? Which will break if I do type ENV = State [(String, LispVal)] instead?

Lisp is a functional language with mutable state and lexical scope. Imagine that you have closed a variable. Now you have a link to this variable, which hangs inside some other function - let's say (in the Haskell-style pseudocode) (printIt, setIt) = let x = 5 in (\ () -> print x, \y -> set xy) . Now you have two functions: one prints x and sets its value. When you evaluate printIt , you want to find the name x in the initial environment in which printIt was defined, but you want to find the value that the name is associated with in the environment in which printIt is printIt (after setIt you could name it any number of times).

There are ways to do this that allow you to use two IORefs, but you certainly need more than the last type you propose, which does not allow you to change values ​​whose names are connected in lexical mode. Google's "problem with effects" for a series of interesting stories.