oop - poo - ¿Cómo funcionan los lenguajes de programación funcionales?

programacion en java pdf (9)

Si los lenguajes de programación funcionales no pueden guardar ningún estado, ¿cómo hacen cosas simples como leer las entradas de un usuario? ¿Cómo "almacenan" la entrada (o almacenan datos para ese asunto?)

Por ejemplo: ¿cómo se traduciría esta simple cosa C a un lenguaje de programación funcional como Haskell?

#include<stdio.h> int main() { int no; scanf("%d",&no); return 0; }

(Mi pregunta fue inspirada por esta excelente publicación: "Ejecución en el reino de los sustantivos" . Leer me dio una mejor comprensión de qué es exactamente la programación orientada a objetos, cómo la implementa Java de una manera extrema y cómo los lenguajes de programación funcionales son un contraste.)

Si los lenguajes de programación funcionales no pueden guardar ningún estado, ¿cómo hacen algunas cosas simples como leer las entradas de un usuario (es decir, cómo lo "almacenan"), o almacenar datos para ese asunto?

Como se reunió, la programación funcional no tiene estado, pero eso no significa que no pueda almacenar datos. La diferencia es que si escribo una declaración (Haskell) a lo largo de las líneas de

let x = func value 3.14 20 "random" in ...

Tengo garantizado que el valor de x siempre es el mismo en ... : nada puede cambiarlo. De manera similar, si tengo una función f :: String -> Integer (una función que toma una cadena y devuelve un entero), puedo estar seguro de que f no modificará su argumento, ni cambiará ninguna variable global, ni escribirá datos en un archivo , y así. Como sepp2k dijo en un comentario anterior, esta no mutabilidad es realmente útil para razonar sobre programas: usted escribe funciones que doblan, giran y mutilan sus datos, devolviendo nuevas copias para que pueda encadenarlas entre sí, y puede estar seguro de que ninguna de esas llamadas a funciones puede hacer cualquier cosa "dañina". Sabes que x siempre es x , y no tienes que preocuparte de que alguien haya escrito x := foo bar en algún lugar entre la declaración de x y su uso, porque eso es imposible.

Ahora, ¿y si quiero leer la entrada de un usuario? Como dijo KennyTM, la idea es que una función impura es una función pura que pasa por todo el mundo como argumento, y devuelve tanto su resultado como el mundo. Por supuesto, no quieres hacer esto: por un lado, es terriblemente torpe, y por otro, ¿qué pasa si reutilizo el mismo objeto del mundo? Así que esto se abstrae de alguna manera. Haskell lo maneja con el tipo IO:

main :: IO () main = do str <- getLine let no = fst . head $ reads str :: Integer ...

Esto nos dice que main es una acción IO que no devuelve nada; ejecutar esta acción es lo que significa ejecutar un programa Haskell. La regla es que los tipos IO nunca pueden escapar de una acción IO; en este contexto, presentamos esa acción usando do . Por lo tanto, getLine devuelve una IO String , que se puede pensar de dos maneras: primero, como una acción que, cuando se ejecuta, produce una cadena; segundo, como una cadena que está "contaminada" por IO ya que se obtuvo impuramente. El primero es más correcto, pero el segundo puede ser más útil. El <- saca la String de la IO String y la almacena en str pero como estamos en una acción IO, tendremos que volver a envolverla, para que no pueda "escapar". La siguiente línea intenta leer un número entero ( reads ) y toma la primera coincidencia exitosa (primera fst . head ); todo esto es puro (sin IO), así que le damos un nombre con let no = ... Entonces podemos usar tanto no como str en ... Por lo tanto, hemos almacenado datos impuros (de getLine en str ) y datos puros ( let no = ... ).

Este mecanismo para trabajar con IO es muy poderoso: te permite separar la parte pura y algorítmica de tu programa del lado impuro de interacción con el usuario y aplicar esto al nivel de tipo. Su función minimumSpanningTree no puede posiblemente cambiar algo en otro lugar en su código, o escribir un mensaje a su usuario, y así sucesivamente. Es seguro.

Esto es todo lo que necesita saber para usar IO en Haskell; si eso es todo lo que quieres, puedes parar aquí. Pero si quieres entender por qué funciona, sigue leyendo. (Y tenga en cuenta que esto será específico de Haskell; otros idiomas pueden elegir una implementación diferente).

Así que esto probablemente parecía un poco de trampa, de alguna manera añadiendo impureza a Haskell puro. Pero no lo es, resulta que podemos implementar el tipo IO completamente dentro de Haskell puro (siempre que se nos dé el RealWorld ). La idea es esta: un tipo IO de acción IO type es lo mismo que una función RealWorld -> (type, RealWorld) , que toma el mundo real y devuelve un objeto de tipo type y el RealWorld modificado. Luego definimos un par de funciones para que podamos usar este tipo sin volvernos locos:

return :: a -> IO a return a = /rw -> (a,rw) (>>=) :: IO a -> (a -> IO b) -> IO b ioa >>= fn = /rw -> let (a,rw'') = ioa rw in fn a rw''

El primero nos permite hablar sobre acciones IO que no hacen nada: return 3 es una acción IO que no consulta el mundo real y simplemente devuelve 3 . El operador >>= , pronunciado "vincular", nos permite ejecutar acciones IO. Extrae el valor de la acción IO, lo pasa y el mundo real a través de la función, y devuelve la acción IO resultante. Tenga en cuenta que >>= impone nuestra regla de que los resultados de las acciones de IO nunca se permitan escapar.

Entonces podemos convertir lo anterior en el siguiente conjunto ordinario de aplicaciones de funciones:

main = getLine >>= /str -> let no = (fst . head $ reads str :: Integer) in ...

El tiempo de ejecución de Haskell se inicia con el RealWorld inicial, ¡y estamos listos! Todo es puro, solo tiene una sintaxis elegante.

[ Editar: Como @Conal señala , esto no es realmente lo que Haskell usa para hacer IO. Este modelo se rompe si agrega concurrencia, o de hecho, cualquier forma en que el mundo cambie en el medio de una acción IO, por lo que sería imposible para Haskell usar este modelo. Es exacto solo para el cálculo secuencial. Por lo tanto, puede ser que el IO de Haskell sea un poco esquivo; incluso si no lo es, ciertamente no es tan elegante. La observación de Per @ Conal, vea lo que dice Simon Peyton-Jones en Tackling the Torpe Squad [pdf] , sección 3.1; presenta lo que podría equivaler a un modelo alternativo en esta línea, pero luego lo descarta por su complejidad y adopta un rumbo diferente.]

Nuevamente, esto explica (más o menos) cómo funciona IO y la mutabilidad en general en Haskell; si esto es todo lo que quiere saber, puede dejar de leer aquí. Si quiere una última dosis de teoría, siga leyendo, pero recuerde, en este punto, ¡nos hemos alejado mucho de su pregunta!

Entonces, la última cosa: resulta que esta estructura -un tipo paramétrico con return y >>= - es muy general; se llama mónada y la notación do , return y >>= funcionan con cualquiera de ellos. Como viste aquí, las mónadas no son mágicas; todo lo que es mágico es que los bloques se convierten en llamadas a funciones. El tipo de RealWorld es el único lugar donde vemos cualquier magia. Los tipos como [] , el constructor de lista, también son mónadas, y no tienen nada que ver con el código impuro.

Ahora sabe (casi) todo sobre el concepto de una mónada (excepto algunas leyes que deben ser satisfechas y la definición matemática formal), pero le falta la intuición. Hay una cantidad ridícula de tutoriales de mónada en línea; Me gusta este , pero tienes opciones. Sin embargo, esto probablemente no te ayudará ; la única forma real de obtener la intuición es a través de una combinación de usarlos y leer un par de tutoriales en el momento correcto.

Sin embargo, no necesita esa intuición para comprender IO . Comprender las mónadas en general es la guinda del pastel, pero puede usar IO en este momento. Podrías usarlo luego de mostrarte la primera función main . ¡Incluso puede tratar el código IO como si fuera un lenguaje impuro! Pero recuerda que hay una representación funcional subyacente: nadie hace trampa.

(PD: Perdón por la duración. Me alejé un poco).

¡El lenguaje funcional puede ahorrar estado! Por lo general, solo lo alientan o lo obligan a ser explícito al hacerlo.

Por ejemplo, echa un vistazo a la Mónada de estado de Haskell.

(Algunos lenguajes funcionales permiten funciones impuras).

Para lenguajes puramente funcionales , la interacción del mundo real generalmente se incluye como uno de los argumentos de función, como este:

RealWorld pureScanf(RealWorld world, const char* format, ...);

Los diferentes idiomas tienen diferentes estrategias para abstraer el mundo del programador. Haskell, por ejemplo, usa mónadas para ocultar el argumento del world .

Pero la parte pura del lenguaje funcional en sí ya está completa, lo que significa que cualquier cosa que se pueda hacer en C también es factible en Haskell. La principal diferencia para el lenguaje imperativo es en lugar de modificar los estados en su lugar:

int compute_sum_of_squares (int min, int max) { int result = 0; for (int i = min; i < max; ++ i) result += i * i; // modify "result" in place return result; }

Incorpora la parte de modificación en una llamada de función, por lo general convirtiendo los bucles en recurrencias:

int compute_sum_of_squares (int min, int max) { if (min >= max) return 0; else return min * min + compute_sum_of_squares(min + 1, max); }

Estoy interrumpiendo un comentario para responder a una nueva respuesta, para dar más espacio:

Escribí:

Hasta donde puedo decir, esta historia de IO ( World -> (a,World) ) es un mito cuando se aplica a Haskell, ya que ese modelo explica solo el cómputo puramente secuencial, mientras que el tipo de IO de Haskell incluye concurrencia. Por "puramente secuencial", quiero decir que ni siquiera el mundo (universo) puede cambiar entre el inicio y el final de un cálculo imperativo, que no sea debido a ese cálculo. Por ejemplo, mientras tu computadora se está agotando, tu cerebro, etc. no puede. La concurrencia puede manejarse por algo más parecido a World -> PowerSet [(a,World)] , que permite el no determinismo y el entrelazado.

Norman escribió:

@Conal: Creo que la historia de IO se generaliza bastante bien al no determinismo y el entrelazado; si no me equivoco, hay una buena explicación en el periódico "Torpe". Pero no sé de un buen documento que explique claramente el paralelismo verdadero.

@Norman: ¿Generaliza en qué sentido? Estoy sugiriendo que el modelo denotacional / explicación generalmente dado, World -> (a,World) , no coincide con Haskell IO porque no tiene en cuenta el no determinismo y la concurrencia. Puede haber un modelo más complejo que encaje, como World -> PowerSet [(a,World)] , pero no sé si dicho modelo se ha elaborado y se muestra adecuado y consistente. Personalmente, dudo que se pueda encontrar una bestia así, dado que IO está poblado por miles de llamadas API imperativas importadas por FFI. Y como tal, IO está cumpliendo su propósito:

Problema abierto: la mónada IO ha convertido en el sinky de Haskell. (Siempre que no comprendamos algo, lo arrojamos en la mónada IO).

(De la charla POPL de Simon PJ Llevando la camisa para el pelo Vistiendo la camisa para el pelo: una retrospectiva sobre Haskell ).

En la Sección 3.1 de Hacer frente al equipo incómodo , Simon señala lo que no funciona sobre el type IO a = World -> (a, World) , incluyendo "El enfoque no escala bien cuando agregamos concurrencia". Luego sugiere un posible modelo alternativo, y luego abandona el intento de explicaciones denotacionales, diciendo:

Sin embargo, en su lugar adoptaremos una semántica operacional, basada en enfoques estándar para la semántica de los cálculos de procesos.

Esta falla en encontrar un modelo denotacional preciso y útil es la raíz de por qué veo a Haskell IO como un alejamiento del espíritu y los profundos beneficios de lo que llamamos "programación funcional", o lo que Peter Landin llamó más específicamente "programación denotativa" . Ver comentarios aquí.

Haskell:

main = do no <- readLn print (no + 1)

Por supuesto, puede asignar cosas a las variables en los lenguajes funcionales. Simplemente no puede cambiarlos (por lo que básicamente todas las variables son constantes en los lenguajes funcionales).

La programación funcional deriva del cálculo lambda. Si realmente quieres entender la programación funcional echa un vistazo a http://worrydream.com/AlligatorEggs/

¡Es una forma "divertida" de aprender Cálculo lambda y llevarlo al apasionante mundo de la programación funcional!

Cómo saber que Lambda Calculus es útil en la programación funcional.

Entonces Lambda Calculus es la base para muchos lenguajes de programación del mundo real como Lisp, Scheme, ML, Haskell, ...

Supongamos que queremos describir una función que agrega tres a cualquier entrada para hacerlo, así escribiríamos:

plus3 x = succ(succ(succ x))

Lea "plus3 es una función que, cuando se aplica a cualquier número x, produce el sucesor del sucesor del sucesor de x"

Tenga en cuenta que la función que agrega 3 a cualquier número no necesita llamarse plus3; el nombre "plus3" es solo una abreviatura conveniente para nombrar esta función

( plus3 x) (succ 0) ≡ ((λ x. (succ (succ (succ x)))) (succ 0))

Tenga en cuenta que usamos el símbolo lambda para una función (creo que se parece a un cocodrilo, supongo que de ahí viene la idea de los huevos de cocodrilo)

El símbolo lambda es Alligator (una función) y x es su color. También puede pensar en x como un argumento (las funciones del cálculo de Lambda en realidad solo se supone que tienen un argumento) el resto lo puede considerar como el cuerpo de la función.

Ahora considera la abstracción:

g ≡ λ f. (f (f (succ 0)))

El argumento f se usa en una posición de función (en una llamada). Llamamos a una función de orden superior porque toma otra función como entrada. Puedes pensar en las otras llamadas de función f como " huevos ". Ahora tomando las dos funciones o " Alligator " que hemos creado, podemos hacer algo como esto:

(g plus3) = (λ f. (f (f (succ 0)))(λ x . (succ (succ (succ x)))) = ((λ x. (succ (succ (succ x)))((λ x. (succ (succ (succ x)))) (succ 0))) = ((λ x. (succ (succ (succ x)))) (succ (succ (succ (succ 0))))) = (succ (succ (succ (succ (succ (succ (succ 0)))))))

Si notas que puedes ver que nuestro λ f Alligator se come nuestro λ x Alligator y luego el λ x Alligator y muere. Entonces nuestro λ x Alligator renace en los huevos de Alligator de λ f. Luego el proceso se repite y el λ x Alligator a la izquierda ahora se come al otro λ x Alligator a la derecha.

Entonces puedes usar este sencillo conjunto de reglas de " Alligators " comiendo " Alligators " para diseñar una gramática y así nacieron los lenguajes de programación Funcionales.

Para que pueda ver si conoce el cálculo de Lambda, comprenderá cómo funcionan los lenguajes funcionales.

La técnica para manejar el estado en Haskell es muy sencilla. Y no necesita comprender las mónadas para manejarlo.

En un lenguaje de programación con estado, normalmente tiene algún valor almacenado en alguna parte, algún código se ejecuta y luego tiene un nuevo valor almacenado. En los lenguajes imperativos, este estado está en algún lugar "en el fondo". En un lenguaje funcional (puro) lo hace explícito, por lo que escribe explícitamente la función que transforma el estado.

Entonces, en lugar de tener algún estado de tipo X, escribes funciones que asignan X a X. ¡Eso es todo! Cambia de pensar en estado a pensar qué operaciones desea realizar en el estado. A continuación, puede encadenar estas funciones y combinarlas de varias formas para crear programas completos. Por supuesto, no está limitado a mapear X a X. Puede escribir funciones para tomar diversas combinaciones de datos como entrada y devolver varias combinaciones al final.

Las mónadas son una herramienta, entre muchas, para ayudar a organizar esto. Pero las mónadas en realidad no son la solución al problema. La solución es pensar en transformaciones de estado en lugar de estado.

Esto también funciona con E / S. En efecto, lo que sucede es esto: en lugar de recibir información del usuario con un equivalente directo de scanf y almacenarlo en algún lugar, en su lugar, escribe una función para decir qué harías con el resultado de scanf si lo tuvieras, y luego pasar esa función a la API de E / S. Eso es exactamente lo que >>= hace cuando usas la món IO en Haskell. Por lo tanto, nunca tendrá que almacenar el resultado de ninguna E / S en ningún lado, solo necesita escribir un código que diga cómo le gustaría transformarlo.

Muchas buenas respuestas aquí, pero son largas. Voy a tratar de dar una respuesta corta útil:

Los lenguajes funcionales ponen el estado en los mismos lugares que C: en las variables nombradas y en los objetos asignados en el montón. Las diferencias son eso:
- En un lenguaje funcional, una "variable" obtiene su valor inicial cuando se trata de alcance (a través de una llamada de función o un enlace de liberación), y ese valor no cambia después . De forma similar, un objeto asignado en el montón se inicializa inmediatamente con los valores de todos sus campos, que no cambian posteriormente.
- Los "cambios de estado" se manejan no mutando las variables u objetos existentes sino vinculando nuevas variables o asignando nuevos objetos.
IO funciona por un truco. Un cálculo de efecto lateral que produce una cadena se describe mediante una función que toma un mundo como argumento y devuelve un par que contiene la cadena y un nuevo mundo. The World incluye el contenido de todas las unidades de disco, el historial de cada paquete de red enviado o recibido, el color de cada píxel en la pantalla y cosas así. La clave del truco es que el acceso al Mundo está cuidadosamente restringido para que
- Ningún programa puede hacer una copia del Mundo (¿dónde lo pondrías?)
- Ningún programa puede tirar el mundo
El uso de este truco hace posible que haya un mundo único cuyo estado evoluciona con el tiempo. El sistema de tiempo de ejecución del idioma, que no está escrito en un lenguaje funcional, implementa un cálculo de efecto secundario al actualizar el mundo único en lugar de devolver uno nuevo.
Este truco está bellamente explicado por Simon Peyton Jones y Phil Wadler en su documento "Imperative Functional Programming" .

podría ser útil, programación de funciones para el resto de nosotros