Diferencia entre Estado, ST, IORef y MVar

Question

Estoy trabajando a través de Write Yourself a Scheme in 48 Hours (estoy hasta aproximadamente 85 horas) y he llegado a la parte sobre Adding Variables and Assignments. Hay un gran salto conceptual en este capítulo, y ojalá hubiera sido hecho en dos pasos con una buena refactorización en el medio en lugar de saltar directamente a la solución final. De todos modos ...

he conseguido perdido con un número de diferentes clases que parecen servir al mismo propósito: State, ST, IORef y MVar. Los tres primeros se mencionan en el texto, mientras que el último parece ser la respuesta preferida a muchas preguntas de StackOverflow sobre los tres primeros. Todos parecen tener un estado entre invocaciones consecutivas.

¿Qué son cada uno de estos y cómo se diferencian entre sí?

---

En particular, estas frases no tienen sentido:

En cambio, usamos una función llamada hilos estatales, dejando Haskell gestionar el estado de agregación para nosotros. Esto nos permite tratar variables mutables como lo haríamos en cualquier otro lenguaje de programación, usando funciones para obtener o establecer variables.

y

El módulo de instrucción IOREF le permite utilizar las variables con estado dentro de la mónada IO.

Todo esto hace que la línea type ENV = IORef [(String, IORef LispVal)] confunda - ¿por qué la segunda IORef? ¿Qué se romperá si escribo type ENV = State [(String, LispVal)]?

Answer 1

La Mónada Estado: un modelo de estado mutable

La mónada Estado es un entorno puramente funcional para programas con el estado, con una simple API:

• obtener
• poner

Documentación en the mtl package.

La mónada de estado se usa comúnmente cuando se necesita estado en un único hilo de control. En realidad, no utiliza el estado mutable en su implementación. En cambio, el programa se parametriza por el valor de estado (es decir, el estado es un parámetro adicional para todos los cálculos). El estado solo parece estar mutado en un único subproceso (y no se puede compartir entre subprocesos).

La mónada ST y STRefs

La mónada ST es el primo restringido de la mónada IO.

Permite el estado mutable arbitrario, implementado como memoria mutable real en la máquina. La API se hace segura en los programas libres de efectos secundarios, ya que el parámetro de tipo rango 2 impide que los valores que dependen del estado mutable escapen del alcance local.

Por lo tanto, permite la mutabilidad controlada en programas puros.

Comúnmente utilizado para matrices mutables y otras estructuras de datos que están mutadas y luego congeladas. También es muy eficiente, ya que el estado mutable es "hardware acelerado".

API primario:

• Control.Monad.ST
• runST - iniciar un nuevo cálculo de efecto memoria.
• Y STRefs: punteros a celdas mutables (locales).
• Las matrices basadas en ST (como el vector) también son comunes.

Piense en ello como el hermano menos peligroso de la mónada IO. O IO, donde solo puedes leer y escribir en la memoria.

instrucción IOREF: STRefs en IO

Estos son STRefs (ver arriba) en la mónada IO. No tienen las mismas garantías de seguridad que STRefs sobre la localidad.

MVARs: IORefs con cerraduras

Como STRefs o IORefs, pero con un bloqueo unido, para la caja fuerte concurrente acceso desde varios subprocesos. IORefs y STRefs solo son seguros en una configuración de subprocesos múltiples cuando se usa atomicModifyIORef (una operación atómica de comparación y cambio). Los MVars son un mecanismo más general para compartir de forma segura el estado mutable.

Generalmente, en Haskell, use MVars o TVars (celdas mutables basadas en STM), sobre STRef o IORef.

Answer 2

Bien, comenzaré con IORef. IORef proporciona un valor que es mutable en la mónada IO. Es solo una referencia a algunos datos, y como cualquier referencia, hay funciones que le permiten cambiar los datos a los que hace referencia. En Haskell, todas esas funciones operan en IO. Puede pensarlo como una base de datos, un archivo u otro almacén de datos externo; puede obtener y establecer los datos en él, pero para hacerlo necesita pasar por IO. La razón por la que IO es necesario es porque Haskell es pure; el compilador necesita una forma de saber a qué datos hace referencia la referencia en un momento dado (lea el blog sigfpe's "You could have invented monads").

MVar s son básicamente lo mismo que un IORef, a excepción de dos diferencias muy importantes. MVar es una primitiva concurrencia, por lo que está diseñado para acceder desde múltiples hilos. La segunda diferencia es que un MVar es un cuadro que puede estar lleno o vacío. Entonces, donde un IORef Int siempre tiene un Int (o está en la parte inferior), un MVar Int puede tener un Int o puede estar vacío. Si un hilo intenta leer un valor de un MVar vacío, se bloqueará hasta que se llene el MVar (por otro hilo). Básicamente, MVar a es equivalente a IORef (Maybe a) con semántica adicional que es útil para la concurrencia.

State es una mónada que proporciona un estado mutable, no necesariamente con IO. De hecho, es particularmente útil para cálculos puros.Si tiene un algoritmo que usa estado pero no IO, una mónada State es a menudo una solución elegante.

Hay también una versión transformador mónada de Estado, StateT. Con frecuencia, esto se usa para mantener los datos de configuración del programa o tipos de estado "estado del mundo del juego" en las aplicaciones.

ST es algo ligeramente diferente. La estructura de datos principal en ST es la STRef, que es como un IORef pero con una mónada diferente. La mónada ST utiliza un truco de sistema de tipo (los "hilos de estado" mencionados por los documentos) para garantizar que los datos mutables no puedan escapar de la mónada; es decir, cuando ejecuta un cálculo ST obtiene un resultado puro. El motivo por el que ST es interesante es que se trata de una mónada primitiva como IO, lo que permite realizar cálculos en manipulaciones de bajo nivel mediante iteraciones y punteros. Esto significa que ST puede proporcionar una interfaz pura al usar operaciones de bajo nivel en datos mutables, lo que significa que es muy rápido. Desde la perspectiva del programa, es como si el cálculo ST se ejecutara en un hilo separado con almacenamiento local de subprocesos.

Answer 3

Otros lo han hecho las cosas básicas, pero para responder a la pregunta directa:

Todo esto hace que el tipo de línea ENV = IORef [(String, IORef LispVal)] confuso. ¿Por qué el segundo IORef? ¿Qué se romperá si hago type ENV = State [(String, LispVal)] en su lugar?

Lisp es un lenguaje funcional con estado mutable y alcance léxico. Imagine que ha cerrado una variable mutable. Ahora tiene una referencia a esta variable que cuelga dentro de alguna otra función, por ejemplo (en pseudocódigo de estilo haskell) (printIt, setIt) = let x = 5 in (\() -> print x, \y -> set x y). Ahora tiene dos funciones: una imprime x, y una establece su valor. Al evaluar printIt, que desea buscar el nombre de x en el entorno inicial en la que se definió printIt, pero que desea buscar el valor deese nombre está ligado a en el entorno en el que printIt es llamados (después de setIt puede haber sido llamado cualquier número de veces).

Hay dos formas en que los dos IORefs pueden hacer esto, pero ciertamente necesita más que el último tipo que ha propuesto, que no le permite alterar los valores a los que están ligados los nombres de forma léxica . Busca en Google el "problema de los funargs" para una gran cantidad de prehistoria interesante.