traduccion programacion monadas monada monad funtores functores haskell functional-programming mercury

haskell - programacion - ¿De qué otras maneras se puede manejar el estado en un lenguaje funcional puro además de las Mónadas?



monads (6)

Así que comencé a rodear mi cabeza con las Mónadas (usadas en Haskell). Tengo curiosidad por saber qué otras formas de IO o estado se pueden manejar en un lenguaje funcional puro (tanto en teoría como en realidad). Por ejemplo, hay un lenguaje lógico llamado "mercurio" que usa "efecto-tipado". En un programa como haskell, ¿cómo funcionaría el efecto de tipeo? ¿Cómo funcionan otros sistemas?

Bueno, primero, ¿qué es el estado? Se puede manifestar como una variable mutable, que no tienes en Haskell. Solo tiene referencias de memoria (IORef, MVar, Ptr, etc.) y acciones IO / ST para actuar sobre ellas.

Sin embargo, el estado mismo puede ser puro también. Para reconocer que revisa el tipo ''Stream'':

data Stream a = Stream a (Stream a)

Esta es una corriente de valores. Sin embargo, una forma alternativa de interpretar este tipo es un valor cambiante:

stepStream :: Stream a -> (a, Stream a) stepStream (Stream x xs) = (x, xs)

Esto se vuelve interesante cuando permite que dos flujos se comuniquen. A continuación, obtiene la categoría de autómata automático:

newtype Auto a b = Auto (a -> (b, Auto a b))

Esto es realmente como Stream , excepto que ahora en cada instante la transmisión obtiene un valor de entrada de tipo a . Esto forma una categoría, por lo que un instante de una secuencia puede obtener su valor del mismo instante de otra secuencia.

De nuevo, una interpretación diferente de esto: tiene dos cálculos que cambian con el tiempo y usted les permite comunicarse. Entonces cada computación tiene un estado local. Aquí hay un tipo que es isomorfo a Auto :

data LS a b = forall s. LS s ((a, s) -> (b, s))

Existe un enfoque llamado Programación funcional reactiva que representa valores variables en el tiempo y / o secuencias de eventos como una abstracción de primera clase. Un ejemplo reciente que me viene a la mente es Elm (está escrito en Haskell y tiene una sintaxis similar a la de Haskell).

Hay varias preguntas diferentes involucradas aquí.

Primero, IO y State son cosas muy diferentes. State es fácil de hacer usted mismo: simplemente pase un argumento adicional a cada función, y devuelva un resultado adicional, y tiene una "función con estado"; por ejemplo, convierta a -> b en a -> s -> (b,s) .

No hay magia involucrada aquí: Control.Monad.State proporciona un contenedor que hace que trabajar con "acciones de estado" de la forma s -> (a,s) conveniente, así como un conjunto de funciones auxiliares, pero eso es todo.

I / O, por su naturaleza, tiene que tener algo de magia en su implementación. Pero hay muchas formas de expresar E / S en Haskell que no involucran la palabra "mónada". Si tuviéramos un subconjunto libre de IO de Haskell tal como está, y quisiéramos inventar IO desde cero, sin saber nada sobre mónadas, hay muchas cosas que podríamos hacer.

Por ejemplo, si todo lo que queremos hacer es imprimir en stdout, podríamos decir:

type PrintOnlyIO = String main :: PrintOnlyIO main = "Hello world!"

Y luego tiene un RTS (sistema de tiempo de ejecución) que evalúa la cadena y la imprime. Esto nos permite escribir cualquier programa Haskell cuya E / S consiste completamente en imprimir en stdout.

Sin embargo, esto no es muy útil porque queremos interactividad. Inventemos un nuevo tipo de IO que lo permita. Lo más simple que viene a la mente es

type InteractIO = String -> String main :: InteractIO main = map toUpper

Este enfoque de IO nos permite escribir cualquier código que lea desde stdin y escriba a stdout (el Preludio viene con una función interact :: InteractIO -> IO () que hace esto, dicho sea de paso).

Esto es mucho mejor, ya que nos permite escribir programas interactivos. Pero todavía es muy limitado en comparación con todo el IO que queremos hacer, y también bastante propenso a errores (si accidentalmente intentamos leer demasiado en stdin, el programa simplemente bloqueará hasta que el usuario escriba más).

Queremos ser capaces de hacer más que leer stdin y escribir stdout. Así es como las primeras versiones de Haskell hicieron E / S, aproximadamente:

data Request = PutStrLn String | GetLine | Exit | ... data Response = Success | Str String | ... type DialogueIO = [Response] -> [Request] main :: DialogueIO main resps1 = PutStrLn "what''s your name?" : GetLine : case resps1 of Success : Str name : resps2 -> PutStrLn ("hi " ++ name ++ "!") : Exit

Cuando escribimos main , obtenemos un argumento de lista diferida y, como resultado, devolvemos una lista perezosa. La lista perezosa que devolvemos tiene valores como PutStrLn s GetLine ; después de obtener un valor (de solicitud), podemos examinar el siguiente elemento de la lista (respuesta), y el RTS se encargará de que sea la respuesta a nuestra solicitud.

Hay formas de mejorar el trabajo con este mecanismo, pero como se puede imaginar, el enfoque se torna bastante incómodo con bastante rapidez. Además, es propenso a errores de la misma manera que el anterior.

Aquí hay otro enfoque que es mucho menos propenso a errores, y conceptualmente muy parecido a cómo se comporta realmente Haskell IO:

data ContIO = Exit | PutStrLn String ContIO | GetLine (String -> ContIO) | ... main :: ContIO main = PutStrLn "what''s your name?" $ GetLine $ /name -> PutStrLn ("hi " ++ name ++ "!") $ Exit

La clave es que en lugar de tomar una "lista perezosa" de respuestas como un gran argumento al comienzo de main, hacemos solicitudes individuales que aceptan un argumento a la vez.

Nuestro programa ahora es solo un tipo de datos regular, muy parecido a una lista vinculada, excepto que no puede simplemente atravesarlo normalmente: cuando el RTS interpreta main , a veces encuentra un valor como GetLine que tiene una función; luego tiene que obtener una cadena de stdin usando magia RTS, y pasar esa cadena a la función, antes de que pueda continuar. Ejercicio: escribir interpret :: ContIO -> IO () .

Tenga en cuenta que ninguna de estas implementaciones implica "paso del mundo". "Pasar el mundo" no es realmente cómo funciona la E / S en Haskell. La implementación real del tipo IO en GHC involucra un tipo interno llamado RealWorld , pero eso es solo un detalle de implementación.

Actual Haskell IO agrega un parámetro de tipo para que podamos escribir acciones que "produzcan" valores arbitrarios, por lo que se parece más a data IO a = Done a | PutStr String (IO a) | GetLine (String -> IO a) | ... data IO a = Done a | PutStr String (IO a) | GetLine (String -> IO a) | ... data IO a = Done a | PutStr String (IO a) | GetLine (String -> IO a) | ... Eso nos da más flexibilidad, porque podemos crear "acciones IO " que producen valores arbitrarios.

(Como señala Russell O''Connor, este tipo es solo una mónada gratuita. Podemos escribir una instancia de Monad fácilmente).

¿Dónde entran las mónadas, entonces? Resulta que no necesitamos Monad para I / O, y no necesitamos Monad para state, entonces, ¿por qué lo necesitamos en absoluto? La respuesta es que no. No hay nada mágico sobre la clase de tipo Monad .

Sin embargo, cuando trabajamos con IO y State (y listas y funciones y Maybe y analizadores y estilo de paso de continuación y ...) durante el tiempo suficiente, finalmente nos damos cuenta de que se comportan de forma bastante similar en algunos aspectos. Podríamos escribir una función que imprime cada cadena en una lista, y una función que ejecuta cada cálculo con estado en una lista y pasa el estado, y se verán muy similares entre sí.

Como no nos gusta escribir mucho código de aspecto similar, queremos una forma de abstraerlo; Monad resulta ser una gran abstracción, porque nos permite abstraer muchos tipos que parecen muy diferentes, pero que aún proporcionan una gran cantidad de funcionalidades útiles (incluido todo en Control.Monad ).

Dado bindIO :: IO a -> (a -> IO b) -> IO b y returnIO :: a -> IO a , podríamos escribir cualquier programa IO en Haskell sin siquiera pensar en mónadas. Pero probablemente terminemos replicando muchas de las funciones en Control.Monad , como mapM y forever y when y (>=>) .

Al implementar la API de Monad común, podemos usar el mismo código exacto para trabajar con acciones de IO que hacemos con los analizadores y las listas. Esa es realmente la única razón por la que tenemos la clase Monad : para capturar las similitudes entre diferentes tipos.

No puede ser (no si por "estado" quiere decir "E / S o comportamiento variable mutable como en un lenguaje de procedimiento"). En primer lugar, debe comprender de dónde proviene el uso de mónadas para variables mutables o E / S. A pesar de la creencia popular, la E / S monádica no proviene de lenguajes como Haskell, sino de lenguajes como ML. Eugenio Moggi desarrolló las mónadas originales mientras estudiaba el uso de la teoría de categorías para la semántica denotacional de lenguajes funcionales impuros como ML. Para ver por qué, considere que una mónada (en Haskell) se puede categorizar por tres propiedades:

  • Hay una distinción entre valores (en Haskell, de tipo a ) y expresiones (en Haskell, de tipo IO a ).
  • Cualquier valor se puede convertir en una expresión (en Haskell, convirtiendo x para return x ).
  • Cualquier función sobre valores (devolver una expresión) se puede aplicar a una expresión (en Haskell, calculando f =<< a ).

Estas propiedades son obviamente ciertas de (al menos) la semántica denotacional de cualquier lenguaje funcional impuro:

  • Una expresión , como print "Hello, world!/n" , puede tener efectos secundarios, pero su valor , como () , no puede. Entonces, debemos hacer una distinción entre los dos casos en la semántica denotacional.
  • Un valor, como 3 , se puede usar en cualquier lugar donde se requiera una expresión. Entonces, nuestra semántica denotacional necesita una función para convertir un valor en una expresión.
  • Una función toma valores como argumentos (los parámetros formales de una función en un lenguaje estricto no tienen efectos secundarios), pero se puede aplicar a una expresión. Entonces, necesitamos una forma de aplicar una función (expresión-retorno) de valores a una expresión.

Por lo tanto, cualquier semántica denotacional para un lenguaje funcional impuro (o de procedimiento) tendrá la estructura de una mónada bajo el capó, incluso si esa estructura no se usa explícitamente para describir cómo funciona la E / S en el lenguaje.

¿Qué hay de los lenguajes puramente funcionales?

Hay cuatro formas principales de hacer E / S en lenguajes puramente funcionales, que conozco (en la práctica) (nuevamente, limitándonos a la E / S de estilo procedimental, FRP es realmente un paradigma diferente):

  • E / S monádica
  • Continuaciones
  • Unicidad / tipos lineales
  • Diálogos

Monadic I / O es obvio. La E / S basada en la continuación se ve así:

main k = print "What is your name? " $ getLine $ / myName -> print ("Hello, " ++ myName ++ "/n") $ k ()

Cada acción de E / S toma una ''continuación'', lleva a cabo su acción y luego realiza llamadas (debajo del capó) la continuación. Entonces en el programa de arriba:

  • print "What is your name? " ejecuta, luego
  • getLine ejecuta, luego
  • print ("Hello, " ++ myName ++ "/n") ejecuta, luego
  • k ejecuta (que devuelve el control al sistema operativo).

La mónada de continuación es una mejora sintáctica obvia a la anterior. De manera más significativa, semánticamente , solo puedo ver dos maneras de hacer que la E / S realmente funcione en lo anterior:

  • Haga que las acciones de E / S (y las continuaciones) devuelvan un "tipo de E / S" que describa la E / S que desea realizar. Ahora tiene una mónada de E / S (continuación basada en mónadas) sin el envoltorio de tipo nuevo.
  • Haga que las acciones de E / S (y las continuaciones) devuelvan lo que es esencialmente () y realice las E / S como un efecto secundario de llamar a las operaciones individuales (por ejemplo, print , getLine , etc.). Pero si la evaluación de una expresión en su idioma (que es el lado derecho de la definición main anterior) es de efecto secundario, no lo consideraría puramente funcional.

¿Qué pasa con la singularidad / tipos lineales? Estos usan valores especiales ''token'' para representar el estado del mundo después de cada acción, e imponen la secuencia. El código se ve así:

main w0 = let w1 = print "What is your name? " w0 (w2, myName) = getLine w1 w3 = print $ "Hello, " ++ myName ++ "!/n" in w3

La diferencia entre los tipos lineales y los tipos de singularidad es que en los tipos lineales , el resultado debe ser w3 (tiene que ser de tipo World ), mientras que en los tipos de singularidad , el resultado podría ser algo como w3 `seq` () . w3 solo tiene que ser evaluado para que ocurra la E / S.

Nuevamente, la mónada de estado es una mejora sintáctica obvia a la anterior. Más significativamente, semánticamente , nuevamente tiene dos opciones:

  • Haga que las operaciones de E / S, como print y getLine , sean estrictas en el argumento World (de modo que la operación anterior se ejecute primero y con efecto lateral (para que la E / S ocurra como un efecto secundario de evaluarlas). De nuevo, si tiene efectos secundarios de evaluación, en mi opinión eso no es puramente funcional.
  • Haga que el tipo World realmente represente la E / S que debe realizarse. Esto tiene el mismo problema que la implementación de IO de GHC con los programas recursivos de cola. Supongamos que cambiamos el resultado de main a main w3 . Ahora la cola main llama a sí misma. Cualquier función que se llame a sí misma, en un lenguaje puramente funcional, no tiene valor (es solo un ciclo infinito); este es un hecho básico sobre cómo funciona la semántica denotacional de recursión en un lenguaje puro. Nuevamente, no consideraría que ningún lenguaje que rompa esa regla (especialmente para un tipo de datos "especial" como World ) sea puramente funcional.

Entonces, realmente, la singularidad o los tipos lineales a) producen programas que son más claros / limpios si los envuelve en una mónada de estado yb) no son en realidad una forma de hacer E / S en un lenguaje puramente funcional después de todo.

¿Qué hay de los diálogos? Esta es la única forma de hacer I / O (o, técnicamente, variables mutables, aunque eso es mucho más difícil) que realmente es puramente funcional e independiente de las mónadas. Eso se ve así:

main resps = [ PrintReq "What is your name? ", GetLineReq, PrintReq $ "Hello, " ++ myName ++ "!/n" ] where LineResp myName = resps !! 1

Sin embargo, notará algunas desventajas de este enfoque:

  • No está claro cómo incorporar procedimientos de E / S en este enfoque.
  • Debe utilizar la indexación numérica o posicional para encontrar la respuesta correspondiente a una solicitud determinada, que es bastante frágil.
  • No hay una forma obvia de determinar una respuesta justo sobre las acciones después de que se recibió; si este programa de alguna manera usara myName antes de emitir la solicitud getLine correspondiente, el compilador aceptará su programa pero se bloqueará en tiempo de ejecución.

Una forma fácil de resolver todos estos problemas es ajustar los diálogos en continuaciones, como este:

type Cont = [Response] -> [Request] print :: String -> Cont -> Cont print msg k resps = PrintReq msg : case resps of PrintResp () : resps1 -> k resps1 getLine :: (String -> Cont) -> Cont getLine k resps = GetLineReq : case resps of GetLineResp msg : resps1 -> k msg resps1

El código ahora parece idéntico al código para la aprobación de continuación de la E / S anterior. De hecho, los diálogos son un excelente tipo de resultado para sus continuaciones en un sistema de E / S basado en continuación, o incluso en un sistema de E / S monádica basado en una mónada de continuación. Sin embargo, al convertir de nuevo a continuaciones, se aplica el mismo argumento, por lo que vemos que, incluso si el sistema en tiempo de ejecución usa los diálogos internamente, los programas deben escribirse para hacer E / S en un estilo monádico.

Otro enfoque importante es la tipificación de exclusividad , como en Clean . La historia breve es que los identificadores al estado (incluido el mundo real) solo se pueden usar una vez, y las funciones que acceden al estado mutable devuelven un nuevo identificador. Esto significa que una salida de la primera llamada es una entrada de un segundo, forzando la evaluación secuencial.

La tipificación de efectos se usa en el compilador de discípulos para Haskell, pero a mi leal saber y entender, el trabajo del compilador sería considerable para habilitarlo en, digamos, GHC. Dejaré la discusión de los detalles a aquellos mejor informados que yo.