scala haskell f# functional-programming

scala - ¿Qué significa el "mundo" en el mundo de la programación funcional?



haskell f# (7)

He estado sumergiéndome en la programación funcional durante más de 3 años y he estado leyendo y comprendiendo muchos artículos y aspectos de la programación funcional.

Pero a menudo me topé con muchos artículos sobre el "mundo" en los cómputos de efectos secundarios y también llevando y copiando el "mundo" en muestras de mónadas IO. ¿Qué significa el "mundo" en este contexto? ¿Es este el mismo "mundo" en todos los contextos de cálculo de efectos secundarios o solo se aplica en mónadas IO?

También la documentación y otros artículos sobre Haskell mencionan el "mundo" muchas veces.

Algunas referencias sobre este "mundo": http://channel9.msdn.com/Shows/Going+Deep/Erik-Meijer-Functional-Programming

y esto: http://www.infoq.com/presentations/Taming-Effect-Simon-Peyton-Jones

Espero una muestra, no solo una explicación del concepto del mundo. Doy la bienvenida al código de muestra en Haskell, F #, Scala, Scheme.

Básicamente, cada programa que escribe puede dividirse en 2 partes (en palabras de PF, en el mundo imperativo / OO no existe tal distinción).

  1. Parte principal / pura: esta es su lógica / algoritmo real de la aplicación que se utiliza para resolver el problema para el que ha creado la aplicación. (El 95% de las aplicaciones actuales carecen de esta parte, ya que son solo un lío de llamadas a la API con / else asperjado, y las personas comienzan a llamarse programadores) Por ejemplo: en una herramienta de manipulación de imágenes, el algoritmo para aplicar varios efectos a la imagen pertenece a esta parte central Entonces, en FP, construye esta parte central utilizando conceptos de FP como pureza, etc. Construye su función que toma entrada y devuelve resultados y no hay ninguna mutación en esta parte de su aplicación.

  2. La parte de la capa externa: ahora dice que ha completado la parte central de la herramienta de manipulación de imágenes y ha probado los algoritmos al llamar a la función con varias entradas y verificar la salida, pero esto no es algo que pueda enviar, cómo se supone que debe usar el usuario Esta parte central no tiene cara de cara, es solo un montón de funciones. Ahora para hacer que este núcleo sea usable desde el punto de vista del usuario final, debe crear algún tipo de interfaz de usuario, la forma de leer los archivos desde el disco, puede usar alguna base de datos integrada para almacenar las preferencias del usuario y la lista continúa. Esta interacción con varias otras cosas, que no es el concepto central de su aplicación pero que aún se requiere para que sea utilizable, se llama el world en FP.

Ejercicio: piense en cualquier aplicación que haya creado anteriormente e intente dividirla en las 2 partes mencionadas anteriormente y, con suerte, eso aclarará las cosas.

Creo que lo primero que debemos leer sobre este tema es Abordar al escuadrón torpe . (No lo hice y lo lamento). El autor en realidad describe la representación interna de IO de GHC como world -> (a,world) como "un poco de pirateo". Creo que este "truco" pretende ser una especie de mentira inocente. Creo que hay dos tipos de mentiras aquí:

  1. GHC pretende que el ''mundo'' es representable por alguna variable.
  2. El world -> (a,world) tipos world -> (a,world) básicamente dice que si pudiéramos crear una instancia del mundo, el "próximo estado" de nuestro mundo está determinado funcionalmente por un pequeño programa que se ejecuta en una computadora. Dado que esto claramente no es realizable, las primitivas se implementan (por supuesto) como funciones con efectos secundarios, ignorando el parámetro "mundo" sin sentido, como en la mayoría de los otros idiomas.

El autor defiende este "hack" en las dos bases:

  1. Al tratar a la IO como una envoltura delgada del world -> (a,world) tipo world -> (a,world) , GHC puede reutilizar muchas optimizaciones para el código IO, por lo que este diseño es muy práctico y económico.
  2. La semántica operacional de la computación IO implementada como anteriormente puede ser probada si el compilador satisface ciertas propiedades. Este documento es citado para la prueba de esto.

El problema (que quería preguntar aquí, pero primero lo pediste, así que perdóname para escribirlo aquí) es que en la presidencia de las funciones estándar de ''IO perezoso'', ya no estoy seguro de que la semántica operacional del GHC siga siendo sólida. .

Las funciones estándar ''IO perezosas'', como hGetContents , hGetContents internamente unsafeInterleaveIO que a su vez es equivalente a unsafeDupableInterleaveIO para programas de un solo hilo.

unsafeDupableInterleaveIO :: IO a -> IO a unsafeDupableInterleaveIO (IO m) = IO ( / s -> let r = case m s of (# _, res #) -> res in (# s, r #))

Pretendiendo que el razonamiento ecuacional todavía funciona para este tipo de programas (tenga en cuenta que m es una función impura) e ignorando el constructor, tenemos unsafeDupableInterleaveIO m >>= f ==> /world -> f (snd (m world)) world , que semánticamente tendría el mismo efecto que Andreas Rossberg describió anteriormente: "duplica" el mundo. Ya que nuestro mundo no se puede duplicar de esta manera, y el orden de evaluación preciso de un programa Haskell es prácticamente impredecible, lo que obtenemos es una carrera de concurrencia casi sin restricciones y sin sincronizar para algunos recursos preciosos del sistema, como los manejadores de archivos. Este tipo de operación, por supuesto, nunca se considera en Ariola y Sabry . Por lo tanto, no estoy de acuerdo con Andreas en este aspecto: la mónada de IO no enlaza el mundo correctamente, incluso si nos restringimos dentro del límite de la biblioteca estándar (y es por eso que algunas personas dicen que la IO perezosa es mala).

El "mundo" es solo un concepto abstracto que captura "el estado del mundo", es decir, el estado de todo lo que está fuera del cálculo actual.

Tome esta función de E / S, por ejemplo:

write : Filename -> String -> ()

Esto no es funcional, ya que cambia el archivo (cuyo contenido es parte del estado del mundo) por efecto secundario. Sin embargo, si modelamos el mundo como un objeto explícito, podríamos proporcionar esta función:

write : World -> Filename -> String -> World

Esto toma el mundo actual y produce funcionalmente uno "nuevo", con el archivo modificado, que luego puede pasar a llamadas consecutivas. El mundo en sí es solo un tipo abstracto, no hay forma de verlo directamente, excepto a través de las funciones correspondientes como read .

Ahora, hay un problema con la interfaz anterior: sin más restricciones, permitiría que un programa "duplique" el mundo. Por ejemplo:

w1 = write w "file" "yes" w2 = write w "file" "no"

Has usado el mismo mundo dos veces, produciendo dos mundos futuros diferentes. Obviamente, esto no tiene sentido como modelo para la E / S física. Para evitar ejemplos como ese, se necesita un sistema de tipo más sofisticado que asegure que el mundo se maneje de manera lineal , es decir, nunca se use dos veces. El lenguaje Clean se basa en una variación de esta idea.

Alternativamente, puede encapsular el mundo de tal manera que nunca se vuelva explícito y, por lo tanto, no pueda ser duplicado por construcción. Eso es lo que logra la mónada de E / S: se puede considerar como una mónada de estado cuyo estado es el mundo, que se enlaza implícitamente a través de las acciones monádicas.

El "mundo" es un concepto involucrado en un tipo de integración de la programación imperativa en un lenguaje puramente funcional.

Como seguramente sabrá, la programación puramente funcional requiere que el resultado de una función dependa exclusivamente de los valores de los argumentos. Supongamos que queremos expresar una operación típica de getLine como una función pura. Hay dos problemas evidentes:

  1. getLine puede producir un resultado diferente cada vez que se llame con los mismos argumentos (sin argumentos, en este caso).
  2. getLine tiene el efecto secundario de consumir parte de un flujo. Si su programa usa getLine , entonces (a) cada invocación debe consumir una parte diferente de la entrada, (b) cada parte de la entrada del programa debe ser consumida por alguna invocación. (No puede tener dos llamadas para getLine lee la misma línea de entrada dos veces, a menos que esa línea getLine dos veces en la entrada; tampoco puede hacer que el programa omita una línea de entrada).

Entonces getLine simplemente no puede ser una función, ¿verdad? Bueno, no tan rápido, hay algunos trucos que podríamos hacer:

  1. Las llamadas múltiples a getLine pueden devolver resultados diferentes. Para que sea compatible con el comportamiento puramente funcional, esto significa que un getLine puramente funcional podría tomar un argumento: getLine :: W -> String . Luego podemos reconciliar la idea de resultados diferentes en cada llamada estipulando que cada llamada debe hacerse con un valor diferente para el argumento W Se podría imaginar que W representa el estado del flujo de entrada.
  2. Las múltiples llamadas a getLine deben ejecutarse en un orden definido, y cada una debe consumir la entrada que quedó de la llamada anterior. Cambio: getLine a getLine el tipo W -> (String, W) y prohíba que los programas utilicen un valor W más de una vez (algo que podemos verificar en la compilación). Ahora, para usar getLine más de una vez en su programa, debe tener cuidado de getLine el resultado W la llamada anterior a la llamada subsiguiente.

Mientras pueda garantizar que los W s no se reutilizarán, puede utilizar este tipo de técnica para traducir cualquier programa imperativo (de un solo hilo) a uno puramente funcional. Ni siquiera necesita tener ningún objeto real en la memoria para el tipo W ; solo tiene que teclear su programa y analizarlo para demostrar que cada W se usa solo una vez, luego emite un código que no se refiere a nada de el género

Entonces el "mundo" es solo esta idea, pero generalizada para cubrir todas las operaciones imperativas, no solo getLine .

Ahora que has explicado todo esto, puedes preguntarte si es mejor que lo sepas. Mi opinión es no, no lo eres. Mira, IMO, toda la idea de "pasar el mundo alrededor" es una de esas cosas como tutoriales de mónada, donde muchos programadores de Haskell han elegido ser "útiles" en formas que realmente no lo son.

"Pasar el mundo alrededor" se ofrece habitualmente como una "explicación" para ayudar a los novatos a comprender Haskell IO. Pero el problema es que (a) es un concepto realmente exótico para que muchas personas envuelvan la cabeza ("¿qué quieres decir con que voy a pasar el estado de todo el mundo ?"), (B) muy abstracto ( mucha gente no puede comprender la idea de que casi todas las funciones de su programa tendrán un parámetro ficticio no utilizado que ni aparece en el código fuente ni en el código del objeto, y (c) no es la explicación más sencilla y práctica de todos modos .

La explicación más sencilla y práctica de Haskell I / O, IMHO, es la siguiente:

  1. Haskell es puramente funcional, por lo que cosas como getLine no pueden ser funciones.
  2. Pero Haskell tiene cosas como getLine . Esto significa que esas cosas son otra cosa que no es una función. Los llamamos acciones .
  3. Haskell te permite tratar las acciones como valores. Puede tener funciones que producen acciones (por ejemplo, putStrLn :: String -> IO () ), funciones que aceptan acciones como argumentos (por ejemplo, (>>) :: IO a -> IO b -> IO b) , etc.
  4. Sin embargo, Haskell no tiene ninguna función que ejecute una acción. No puede haber un execute :: IO a -> a porque no sería una función verdadera.
  5. Haskell tiene funciones integradas para componer acciones: realiza acciones compuestas a partir de acciones simples. Usando acciones básicas y combinadores de acciones, puede describir cualquier programa imperativo como una acción.
  6. Los compiladores de Haskell saben cómo traducir acciones en código nativo ejecutable. Entonces, escribe un programa ejecutable de Haskell escribiendo una acción main :: IO () en términos de subacciones.

El mundo se refiere a interactuar con el mundo real / tiene efectos secundarios, por ejemplo

fprintf file "hello world"

lo que tiene un efecto secundario: el archivo ha sido añadido a "hello world" .

Esto se opone al código puramente funcional como

let add a b = a + b

que no tiene efectos secundarios

El mundo significa precisamente eso: el mundo físico y real. (Sólo hay uno, fíjate.)

Al descuidar los procesos físicos que se limitan a la CPU y la memoria, se puede clasificar cada función:

  1. Aquellos que no tienen efectos en el mundo físico (excepto los efectos efímeros, en su mayoría no observables en la CPU y la RAM)
  2. Los que sí tienen efectos observables. por ejemplo: imprimir algo en la impresora, enviar electrones a través de cables de red, lanzar cohetes o mover cabezas de disco.

La distinción es un poco artificial, en la medida en que ejecutar incluso el programa Haskell más puro en realidad tiene efectos observables, como: su CPU se está calentando, lo que hace que el ventilador se encienda.

Transmitir valores que representan "el mundo" es una forma de hacer un modelo puro para hacer IO (y otros efectos secundarios) en programación declarativa pura.

El "problema" con la programación declarativa pura (no solo funcional) es obvio. La programación declarativa pura proporciona un modelo de computación. Estos modelos pueden expresar cualquier computación posible, pero en el mundo real usamos programas para que las computadoras hagan cosas que no son computación en un sentido teórico: toma de entrada, renderización de pantallas, almacenamiento de lectura y escritura, uso de redes, robots de control, etc. , etc. Puede modelar directamente casi todos los programas de este tipo como computación (por ejemplo, qué salida debe escribirse en un archivo dado que esta entrada es una computación), pero las interacciones reales con cosas fuera del programa simplemente no son parte del modelo puro .

Eso es realmente cierto de la programación imperativa también. El "modelo" de cálculo que es el lenguaje de programación C no proporciona ninguna forma de escribir en archivos, leer desde teclados, o cualquier otra cosa. Pero la solución en la programación imperativa es trivial. Realizar una computación en el modelo imperativo es ejecutar una secuencia de instrucciones, y lo que realmente hace cada instrucción depende de todo el entorno del programa en el momento en que se ejecuta. Por lo tanto, solo puede proporcionar instrucciones "mágicas" que realicen sus acciones de IO cuando se ejecuten. Y como los imperativos programadores están acostumbrados a pensar en sus programas operativamente 1 , esto se ajusta muy naturalmente a lo que ya están haciendo.

Pero en todos los modelos puros de computación, lo que hará una unidad de computación dada (función, predicado, etc.) dependerá únicamente de sus entradas, no de algún entorno arbitrario que pueda ser diferente cada vez. Así que no solo es imposible realizar acciones de E / S, sino también implementar cálculos que dependen del universo fuera del programa.

Sin embargo, la idea para la solución es bastante simple. Construye un modelo para ver cómo funcionan las acciones de E / S dentro de todo el modelo puro de cómputo. Entonces, todos los principios y teorías que se aplican al modelo puro en general también se aplicarán a la parte del modelo que modela el IO. Luego, dentro del lenguaje o la implementación de la biblioteca (debido a que no se puede expresar en el lenguaje mismo), se conectan las manipulaciones del modelo IO a las acciones reales de IO.

Esto nos lleva a transmitir un valor que representa al mundo. Por ejemplo, un programa de "hola mundo" en Mercury tiene este aspecto:

:- pred main(io::di, io::uo) is det. main(InitialWorld, FinalWorld) :- print("Hello world!", InitialWorld, TmpWorld), nl(TmpWorld, FinalWorld).

Al programa se le da InitialWorld , un valor en el tipo io que representa todo el universo fuera del programa. Pasa este mundo para print , lo que devuelve a TmpWorld , el mundo que es como InitialWorld pero en el que "Hello world!" se ha impreso en el terminal, y todo lo que haya ocurrido entretanto desde que InitialWorld se pasó a main también se ha incorporado. Luego pasa TmpWorld a nl , lo que devuelve a FinalWorld (un mundo que se parece mucho a TmpWorld pero incorpora la impresión de la nueva línea, más cualquier otro efecto que haya ocurrido mientras tanto). FinalWorld es el estado final del mundo que se pasa de nuevo al sistema operativo.

Por supuesto, no estamos pasando todo el universo como un valor en el programa. En la implementación subyacente, generalmente no hay un valor de tipo io en absoluto, porque no hay información que sea útil para transmitir; todo existe fuera del programa. Pero el uso del modelo en el que transmitimos los valores de io nos permite programar como si todo el universo fuera una entrada y una salida de cada operación que se ve afectada por ella (y, en consecuencia, ver que cualquier operación que no tome un argumento de entrada y salida no puede ser afectado por el mundo externo).

Y, de hecho, normalmente ni siquiera pensarías en programas que hacen IO como si estuvieran pasando por todo el universo. En el código de Mercury real utilizarías el azúcar sintáctico "variable de estado" y escribirías el programa anterior como este:

:- pred main(io::di, io::uo) is det. main(!IO) :- print("Hello world!", !IO), nl(!IO).

La sintaxis del signo de exclamación significa que !IO realmente representa dos argumentos, IO_X e IO_Y , donde las partes X e Y se completan automáticamente por el compilador, de tal manera que la variable de estado se "enlaza" a través de los objetivos en el orden en que están escrito. Esto no solo es útil en el contexto de IO por cierto, las variables de estado son muy útiles para el azúcar sintáctica en Mercury.

Por lo tanto, el programador en realidad tiende a pensar en esto como una secuencia de pasos (que dependen del estado externo y que lo afectan) que se ejecutan en el orden en que se escriben. !IO casi se convierte en una etiqueta mágica que solo marca las llamadas a las que se aplica.

En Haskell, el modelo puro para IO es una mónada, y el programa "hola mundo" tiene este aspecto:

main :: IO () main = putStrLn "Hello world!"

Una forma de interpretar la mónada IO es similar a la mónada State ; se transfiere automáticamente un valor de estado, y cada valor en la mónada puede depender o afectar este estado. Solo en el caso de IO el estado que se está enlazando es todo el universo, como en el programa Mercury. Con las variables de estado de Mercury y la notación de haskell de Haskell, los dos enfoques terminan pareciéndose bastante similares, con el "mundo" automáticamente enlazado de una manera que respeta el orden en que se escribieron las llamadas en el código fuente, = pero aún teniendo acciones IO Marcado explícitamente.

Como se explica bastante bien en la respuesta de sacundim , otra forma de interpretar la mónada IO de Haskell como modelo para los cálculos de IO-y es imaginar que se putStrLn "Hello world!" no es, de hecho, una computación a través de la cual "el universo" necesita ser enlazado, sino más bien que se putStrLn "Hello World!" es en sí misma una estructura de datos que describe una acción de IO que se podría tomar. En este entendimiento, lo que hacen los programas en la mónada IO es usar programas puros de Haskell para generar en tiempo de ejecución un programa imperativo. En Haskell puro, no hay forma de ejecutar ese programa, pero como main es del tipo IO () main se evalúa a dicho programa, y ​​solo sabemos operativamente que el tiempo de ejecución de Haskell ejecutará el programa main .

Ya que estamos conectando estos modelos puros de IO a interacciones reales con el mundo exterior, debemos ser un poco cuidadosos. Estamos programando como si todo el universo fuera un valor que podemos transmitir al igual que otros valores. Pero otros valores pueden transferirse a múltiples llamadas diferentes, almacenarse en contenedores polimórficos y muchas otras cosas que no tienen ningún sentido en términos del universo real. Así que necesitamos algunas restricciones que nos impiden hacer cualquier cosa con "el mundo" en el modelo que no se corresponda con nada que se pueda hacer al mundo real.

El enfoque adoptado en Mercury es utilizar modos únicos para imponer que el valor de io siga siendo único. Es por eso que el mundo de entrada y salida se declararon como io::di y io::uo respectivamente; es una forma abreviada de declarar que el tipo del primer parámetro es io y su modo es di (abreviatura de "entrada destructiva"), mientras que el tipo del segundo parámetro es io y su modo es uo (abreviatura de "salida única") . Dado que io es un tipo abstracto, no hay forma de crear nuevos, por lo que la única manera de cumplir con el requisito de singularidad es pasar siempre el valor de io a una llamada como máximo, lo que también debe devolverle un valor de io único, y luego para dar salida al valor final de io desde la última cosa que llame.

El enfoque adoptado en Haskell es utilizar la interfaz de la mónada para permitir que los valores en la mónada IO se construyan a partir de datos puros y de otros valores IO , pero no exponga ninguna función en los valores IO que le permita "extraer" datos puros de la IO mónada. Esto significa que solo los valores de IO incorporados en main harán algo, y esas acciones deben estar correctamente secuenciadas.

Mencioné antes que los programadores que hacen IO en un lenguaje puro todavía tienden a pensar operativamente en la mayoría de sus IO. Entonces, ¿por qué tomarse todas estas molestias para crear un modelo puro para IO si solo lo pensamos de la misma manera que lo hacen los imperativos programadores? La gran ventaja es que ahora todas las teorías / código / lo que se aplique a todo el lenguaje se aplican también al código IO.

Por ejemplo, en Mercury el equivalente de fold procesa una lista elemento por elemento para acumular un valor acumulador, lo que significa que el fold toma un par de variables de entrada / salida de algún tipo arbitrario como el acumulador (este es un patrón muy común en La biblioteca estándar de Mercury, y es por eso que dije que la sintaxis de las variables de estado a menudo resulta muy útil en otros contextos que IO. Ya que "el mundo" aparece explícitamente en los programas de Mercury como un valor en el tipo io , ¡es posible usar los valores de io como el acumulador! Imprimir una lista de cadenas en Mercury es tan simple como foldl(print, MyStrings, !IO) . De manera similar, en Haskell, el código genérico de mónada / functor funciona bien en los valores de IO / S. Obtenemos una gran cantidad de operaciones de IO de "orden superior" que tendrían que implementarse de nuevo especializadas en IO en un lenguaje que maneje IO mediante algún mecanismo completamente especial.

Además, dado que evitamos romper el modelo puro por IO, las teorías que son verdaderas del modelo computacional siguen siendo verdaderas incluso en presencia de IO. Esto hace que el razonamiento del programador y las herramientas de análisis del programa no tengan que considerar si IO podría estar involucrado. En lenguajes como Scala, por ejemplo, aunque mucho código "normal" es de hecho puro, las optimizaciones y las técnicas de implementación que funcionan con código puro generalmente no son aplicables, porque el compilador debe suponer que cada llamada puede contener IO u otros efectos.

1 Pensar en los programas operativamente significa entenderlos en términos de las operaciones que la computadora llevará a cabo al ejecutarlos.