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

Si los lenguajes de programación funcionales no pueden guardar ningún estado, ¿cómo hacen cosas simples como leer la entrada de un usuario? ¿Cómo "almacenan" la entrada (o almacenan cualquier dato para el caso?)

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

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

(Mi pregunta se inspiró en esta excelente publicación: "Ejecución en el reino de los sustantivos" . Leerla me dio una mejor comprensión de qué es exactamente la programación orientada a objetos, cómo Java la implementa 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 cosas simples como leer la entrada de un usuario (me refiero a cómo la "almacenan"), o almacenar cualquier dato para el caso?

Como pudo deducir, 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) en la línea de

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

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

Ahora, ¿qué pasa 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 se transmite al mundo entero como argumento y devuelve tanto su resultado como el mundo. Por supuesto, en realidad no quieres hacer esto: por un lado, es horriblemente torpe, y por otro, ¿qué sucede si reutilizo el mismo objeto mundial? Entonces 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 maines 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, introducimos esa acción usando do. Por tanto, getLinedevuelve an IO String, que se puede considerar de dos formas: 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 de manera impura. El primero es más correcto, pero el segundo puede ser más útil. El <-toma elString salida de la IO Stringy lo almacena en str-pero ya que estamos en una acción IO, tendremos que envuelve una copia de seguridad, por lo que no pueden "escapar". La siguiente línea intenta leer un entero ( reads) y toma la primera coincidencia exitosa (fst . head); todo esto es puro (sin IO), así que le damos un nombre con let no = .... Luego podemos usar ambos noy stren el .... Por lo tanto, hemos almacenado datos impuros (desde getLineadentro str) y datos puros ( let no = ...).

Este mecanismo para trabajar con IO es muy poderoso: le permite separar la parte algorítmica pura de su programa del lado impuro de interacción con el usuario, y hacer cumplir esto a nivel de tipo. Es posible que su minimumSpanningTreefunción no pueda cambiar algo en otro lugar de 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 estas cosas serán específicas de Haskell; otros lenguajes pueden elegir una implementación diferente).

Así que esto probablemente parecía una trampa, agregando de alguna manera impureza al 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: una acción IO IO typees lo mismo que una función RealWorld -> (type, RealWorld), que toma el mundo real y devuelve tanto un objeto de tipo typecomo el modificado RealWorld. 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'

La primera nos permite hablar de acciones IO que no hacen nada: return 3es una acción IO que no consulta el mundo real y simplemente regresa 3. El >>=operador, pronunciado "bind", nos permite ejecutar acciones IO. Extrae el valor de la acción IO, lo pasa al mundo real a través de la función y devuelve la acción IO resultante. Tenga en cuenta que>>= hace cumplir nuestra regla de que los resultados de las acciones de IO nunca pueden escapar.

Luego podemos convertir lo anterior mainen 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 comienza maincon la inicialRealWorld , ¡y estamos listos! Todo es puro, solo tiene una sintaxis elegante.

[ Editar: como señala @Conal , esto no es realmente lo que Haskell usa para hacer IO. Este modelo se rompe si agrega simultaneidad o, de hecho, cualquier forma de que el mundo cambie en medio de una acción de IO, por lo que sería imposible para Haskell usar este modelo. Es preciso solo para cálculos secuenciales. Por lo tanto, puede ser que la IO de Haskell sea un poco esquiva; incluso si no lo es, ciertamente no es tan elegante. Según la observación de @ Conal, vea lo que dice Simon Peyton-Jones en Tackling the Awkward Squad [pdf] , sección 3.1; presenta lo que podría equivaler a un modelo alternativo en este sentido, pero luego lo abandona por su complejidad y toma un rumbo diferente.]

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

Así que una última cosa: resulta que esta estructura, un tipo paramétrico con returny >>=, es muy general; se llama mónada, y la donotación return, y >>=funciona con cualquiera de ellos. Como vio aquí, las mónadas no son mágicas; todo lo que es mágico es que los dobloques se convierten en llamadas a funciones. El RealWorldtipo es el único lugar en el que vemos magia. Los tipos como [], el constructor de listas, también son mónadas y no tienen nada que ver con código impuro.

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

Sin embargo, no necesitas esa intuición para entender IO . Entender las mónadas en su totalidad es la guinda del pastel, pero puedes usar IO ahora mismo. Podrías usarlo después de que te mostré el primeromain función. ¡Incluso puede tratar el código IO como si estuviera en un lenguaje impuro! Pero recuerde que hay una representación funcional subyacente: nadie está haciendo trampa.

(PD: Perdón por la duración. Fui un poco más lejos).

Aquí hay muchas buenas respuestas, pero son largas. Voy a intentar dar una respuesta breve útil:

• Los lenguajes funcionales colocan el estado en los mismos lugares que C: en variables con nombre y en objetos asignados en el montón. Las diferencias son que:

  • En un lenguaje funcional, una "variable" obtiene su valor inicial cuando entra en el alcance (a través de una llamada a una función o un enlace let), y ese valor no cambia después . De manera similar, un objeto asignado en el montón se inicializa inmediatamente con los valores de todos sus campos, que no cambian a partir de entonces.

  • Los "cambios de estado" se manejan no mutando variables u objetos existentes, sino vinculando nuevas variables o asignando nuevos objetos.

• IO funciona mediante un truco. Un cálculo de efectos secundarios 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. El mundo 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 por el estilo. 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 lenguaje, que no está escrito en un lenguaje funcional, implementa un cálculo de efectos secundarios al actualizar el mundo único en su lugar en lugar de devolver uno nuevo.

  Este truco está bellamente explicado por Simon Peyton Jones y Phil Wadler en su artículo histórico "Programación funcional imperativa" .

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

Escribí:

Por lo que puedo decir, esta IOhistoria ( World -> (a,World)) es un mito cuando se aplica a Haskell, ya que ese modelo solo explica el cálculo puramente secuencial, mientras que el IOtipo de Haskell incluye la concurrencia. Por "puramente secuencial", quiero decir que ni siquiera el mundo (universo) puede cambiar entre el comienzo y el final de un cálculo imperativo, salvo debido a ese cálculo. Por ejemplo, mientras su computadora está funcionando, su cerebro, etc. no puede hacerlo. La concurrencia se puede manejar con algo más parecido World -> PowerSet [(a,World)], lo 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 al entrelazado; si mal no recuerdo, hay una explicación bastante buena en el artículo de "Awkward Squad". Pero no conozco un buen artículo que explique claramente el verdadero paralelismo.

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

Problema abierto: la IOmónada se ha convertido en el pecado de Haskell. (Siempre que no entendemos algo, lo tiramos en la mónada IO).

(De la charla POPL de Simon PJ Llevando la camiseta con el pelo Llevando la camiseta con el pelo: una retrospectiva de Haskell ).

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

Sin embargo, adoptaremos en cambio una semántica operativa, basada en enfoques estándar de la semántica de los cálculos de procesos.

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

La programación funcional se deriva de lambda Calculus. Si realmente desea comprender la programación funcional, visite http://worrydream.com/AlligatorEggs/

Es una forma "divertida" de aprender el cálculo lambda y llevarte al apasionante mundo de la programación funcional.

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

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

Supongamos que queremos describir una función que suma tres a cualquier entrada para hacerlo, por lo que escribiríamos:

plus3 x = succ(succ(succ x)) 

Lea "más3 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 suma 3 a cualquier número no necesita ser nombrada plus3; el nombre "plus3" es solo una forma abreviada de nombrar esta función

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

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

El símbolo lambda es el Alligator (una función) y la x es su color. También puede pensar en x como un argumento (se supone que las funciones de Lambda Calculus solo tienen un argumento), el resto puede pensar en él como el cuerpo de la función.

Ahora considere 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 ga función de orden superior porque toma otra función como entrada. Puede pensar en las otras llamadas a funciones f como " huevos ". Ahora tomando las dos funciones o " Caimanes " 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, puedes ver que nuestro λ f Alligator se come a nuestro λ x Alligator y luego al λ 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 de la izquierda ahora se come al otro λ x Alligator de la derecha.

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

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

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

En un lenguaje de programación con estado, normalmente tiene algún valor almacenado en algún lugar, 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 segundo plano". 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 mapean X a X. ¡Eso es! Pasas de pensar en el estado a pensar en las operaciones que deseas 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 simplemente asignar X a X. Puede escribir funciones para tomar varias 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 no son en realidad 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 algún equivalente directo descanf y almacenarla en algún lugar, escribe una función para decir qué haría con el resultado de scanfsi la tuviera, y luego pasa eso función a la API de E / S. Eso es exactamente lo que >>=hace cuando usa la IOmónada en Haskell. Por lo tanto, nunca necesita almacenar el resultado de ninguna E / S en ningún lugar, solo necesita escribir un código que diga cómo le gustaría transformarlo.

(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 la función, así:

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

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

Pero la parte pura del lenguaje funcional en sí ya es Turing completo, lo que significa que cualquier cosa factible en C también es factible en Haskell. La principal diferencia con el lenguaje imperativo es en lugar de modificar 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, generalmente convirtiendo los bucles en recursiones:

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);
}

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

Por ejemplo, consulte State Monad de Haskell .

puede ser útil, programación de funciones para el resto de nosotros

Haskell:

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

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