variables - Diferencia entre Estado, ST, IORef y MVar

haskell monads

Question

Estoy trabajando en Write Yourself a Scheme en 48 horas (estoy hasta aproximadamente 85 horas) y he llegado a la parte sobre Añadir variables y asignaciones . 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 todas formas…

Me he perdido con varias clases diferentes que parecen cumplir el 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 difieren entre sí?

En particular, estas oraciones no tienen sentido:

En su lugar, usamos una característica llamada subprocesos de estado , lo que permite a Haskell administrar el estado agregado 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 IORef le permite usar variables con estado dentro de la mónada IO .

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

Answer 1

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 funcionan 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 cual IO es necesario es porque Haskell es puro ; el compilador necesita una forma de saber a qué datos hace referencia la referencia en un momento dado (lea la publicación de blog "You could have inventoured monads" de sigfpe ).

MVar 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 una caja que puede estar llena o vacía. Entonces, cuando un IORef Int siempre tiene un Int (o está abajo), 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 el MVar se llene (por otro hilo). Básicamente, un MVar a es equivalente a un 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 de State menudo es una solución elegante.

También hay una versión de transformador de mónada de State, 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 STRef , que es como un IORef pero con una mónada diferente. La mónada de ST utiliza el engaño del sistema de tipo (los "hilos de estado" que mencionan 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 de ST ejecutara en un hilo separado con almacenamiento local de subprocesos.

Answer 2

Otros han hecho las cosas centrales, 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 type ENV = State [(String, LispVal)] ?

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, digamos (en pseudocódigo de estilo (printIt, setIt) = let x = 5 in (/ () -> print x, /y -> set xy) ) (printIt, setIt) = let x = 5 in (/ () -> print x, /y -> set xy) . Ahora tiene dos funciones: una imprime x, y una establece su valor. Cuando evalúa printIt , desea buscar el nombre de x en el entorno inicial en el que se definió la printIt , pero desea buscar el valor al que está vinculado ese nombre en el entorno en el que se llama setIt (después de setIt puede haber llamado cualquier cantidad de veces).

Hay 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.

Answer 3

La mónada de estado: un modelo de estado mutable

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

• obtener
• poner

Documentación en el paquete mtl .

La mónada de estado se usa comúnmente cuando se necesita estado en un solo 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, luego congeladas. También es muy eficiente, ya que el estado mutable es "hardware acelerado".

API principal:

• Control.Monad.ST
• runST: inicia un nuevo cálculo de memoria-efecto.
• Y STRefs : punteros a celdas mutables (locales).
• Los arrays basados ​​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.

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 bloqueos

Al igual que STRefs o IORefs, pero con un bloqueo adjunto, para un acceso concurrente seguro 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.

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