Get best of the week

La programación funcional es lo que (probablemente) le dijeron. Si escuchaste

Me gustan las conversaciones sobre el tema "Antes me decían en la escuela / instituto / padres, pero ahora me enteré". Si, por casualidad, me encuentro al menos un poco competente en el asunto en discusión, entonces esas conversaciones generalmente se reducen a una de tres opciones: "¿Dónde has escuchado esas tonterías antes?" (si el interlocutor tiene razón), "¿y de dónde sacaste que esto es así?" (si está equivocado) y "tiene razón, solo que esto no contradice lo que le dijeron antes" (en la gran mayoría de los casos). Me gustan estas conversaciones por la siguiente razón: por lo general, su iniciador no está cargado con un conocimiento preliminar excesivo del problema, lo que en algunos casos le permite señalar algunos puntos que fueron aceptados como obvios, pero en realidad no lo son. Y uno de los temas para tales conversaciones fue la programación funcional.

En general, se ha escrito y dicho tanto sobre FP que parece ser todas las preguntas sobre su aplicabilidad, frescura, rendimiento, etc. roído hasta la médula ósea. Sin embargo, tales preguntas se plantean una y otra vez, y siempre habrá alguien que quiera hablar sobre lo que todos entendieron mal, pero de hecho es así. Tal vez hoy intentaré este papel desagradecido, ya que recientemente me llamó la atención en varias publicaciones sobre este tema tan sufrido. El primero y el segundo dicen una vez más que la FA es una basura y estudiarla solo arruina el karma de su futuro especialista. Otros ( uno y dos) son mucho más adecuados, en ellos el autor pretende explicar que todas estas lambdas, combinadores, categorías no son más que polvo en los ojos, y la FP en sí misma es algo simple, comprensible y agradable en la vida.

¿Qué tan cierto es esto?

Antes de pasar a la esencia del problema, haré una pequeña digresión y pondré énfasis. Creo que el contenido de las dos primeras publicaciones es una tontería de un analfabeto ... especialista que, con los dedos separados, discute cosas que ni siquiera pasó un poco de su precioso tiempo estudiando. Las buenas personas de entre los comentaristas ya han indicado que esto no es más que bromas. El problema es que, como resultó, no puedo percibir las tesis presentadas en estas traducciones como una broma, ya que tuve que escuchar la mayoría de ellas en vivo. Aparentemente, puede diagnosticar la presencia de trauma psicológico causado por una sobreoferta de tonterías que ha pasado por el cerebro.

Los dos segundos tenían más probabilidades de evocar emociones positivas, porque en ellos el autor aplica la práctica de FP a las tareas que entiende el desarrollador de OOP. A pesar del desacuerdo con el mensaje básico de la primera publicación reflejado en el título y las dudas sobre la razonabilidad de la implementación del concepto de mónada en una forma tan explícita en el lenguaje orientado a OOP, el autor no puede ser reprochado por la falta de elaboración del material. Pero hay un aspecto básico, que no podía ignorar. Este es un tipo de vulgarización de la programación funcional, un intento de considerarlo como un conjunto simple de herramientas y enfoques para el diseño de programas. Lo cual, en mi opinión, no es del todo cierto.

Por lo tanto, en este artículo, se intenta demostrar que las propiedades de los programas funcionales que el autor está tratando de reproducir en su código no son la base de la programación funcional, no establecidas por los sabios creadores de Haskell y sus soluciones de diseño, sino una consecuencia directa de esos conceptos y modelos que realmente establecido en sus cimientos, o, curiosamente, un intento de compensar las deficiencias que generan estos cimientos.

Entonces al punto


En ciencia, con bastante frecuencia se puede observar la siguiente metamorfosis. Primero, como parte de la consideración de cierto proceso / fenómeno / teoría, aparece un cierto objeto que posee algunas propiedades importantes y útiles. Pero generalmente también resulta ser bastante complicado en su estructura, lo que limita su utilidad práctica. Por lo tanto, a menudo actúan de esta manera: toman las propiedades de un objeto dado como base y sobre esta base construyen una nueva teoría / modelo / descripción, dentro de la cual el objeto deseado se vuelve simple o incluso trivial, o las propiedades inherentes necesarias aparecen en objetos mucho más simples. Algo como esto está relacionado con la programación funcional "real" y los "elementos de la programación funcional", que están disponibles en lenguajes modernos de alto nivel.

Como generalmente es útil familiarizarse con la historia de su origen para comprender un fenómeno, recordemos los momentos de la historia de la teoría de la computación y la programación que son importantes para nuestra pregunta. A finales del siglo XIX y principios del XX hubo una reestructuración significativa de los fundamentos de la ciencia matemática. Esto no solo resolvió una serie de problemas y contradicciones identificados que se introdujeron en el núcleo mismo de las ideas en ese momento de que había matemáticas y pruebas matemáticas, sino que también planteó una serie de nuevas preguntas. Uno de ellos fue el siguiente: ¿cuál es el algoritmo? O, lo que es lo mismo, qué clase de problemas se pueden resolver de forma puramente mecánica. No profundizaré en por qué esta pregunta resultó ser importante; sería mejor ir directamente a la respuesta que le dio Alan Turing, ampliamente conocido en círculos no muy estrechos. Él formuló la tesis:"Solo las funciones para las que se puede construir una máquina de Turing son computables". Esta declaración no está probada. Es decir, de hecho, Turing simplemente dio una definición formal estricta de lo que se considera una función computable, consistente con esas representaciones intuitivas que generalmente están integradas en este concepto. Esta definición demostró ser capaz de satisfacer a los solicitantes, porque son muy conscientes de lo que es una máquina, incluso con una cinta infinita, y de cómo debería funcionar. Pero para muchos matemáticos, esta definición no está muy satisfecha.que generalmente se invierten en este concepto. Esta definición demostró ser capaz de satisfacer a los solicitantes, porque son muy conscientes de lo que es una máquina, incluso con una cinta infinita, y de cómo debería funcionar. Pero para muchos matemáticos, esta definición no está muy satisfecha.que generalmente se invierten en este concepto. Esta definición demostró ser capaz de satisfacer a los solicitantes, porque son muy conscientes de lo que es una máquina, incluso con una cinta infinita, y de cómo debería funcionar. Pero para muchos matemáticos, esta definición no está muy satisfecha.

Aparentemente, los conceptos que operaba Turing les parecían insuficientemente ... abstractos. En este sentido, no abandonaron los intentos de dar una definición diferente, que abarcaría una clase más amplia de funciones matemáticas y, al mismo tiempo, correspondería a nuestras ideas intuitivas. Estos intentos fueron infructuosos. Cada definición alternativa que se propuso y resistió las críticas resultó ser equivalente a la definición de Turing en el sentido de que describía exactamente la misma clase de funciones matemáticas. Sin embargo, estos estudios no fueron de ninguna manera inútiles. Los intentos de mirar el objeto de estudio desde un punto de vista diferente generalmente son raramente inútiles. En nuestro caso, esto llevó a la aparición de varias teorías, una de las cuales fue el cálculo lambda propuesto por Alonzo Church.

La pereza es el motor del progreso.


¿Qué es tan útil en el cálculo lambda y por qué todos se preocupan tanto? Todo es simple En el modelo propuesto por Turing, el algoritmo es una secuencia de instrucciones que nos es familiar, que nuevamente debe ejecutar el ejecutante habitual. Es intuitivo. Pero la definición de Church es diferente. El mecanismo de construcción principal (y esencialmente el único) en el marco de esta teoría son los llamados términos lambda, que en nuestros términos actuales pueden llamarse (condicionalmente) funciones anónimas. El programa (algoritmo) en este caso es una combinación de estos términos construidos de acuerdo con ciertas reglas, los datos iniciales son los valores de las variables libres del término lambda, y el proceso de cálculo no es más que una reducción (simplificación) del término lambda (función), que puede ser llevado a cabotan pronto como alguna variable libre obtiene valor. El siguiente hecho resultó ser inesperado aquí: tan pronto como una variable recibe un valor, es decir, tan pronto como presentamos una parte de los datos iniciales al programa, podemos realizar la reducción, pero no de una, sino de dos maneras. En el primer caso, el proceso de cálculo resulta ser equivalente al reproducido por calculadoras mecánicas típicas como una máquina de Turing. La regla le corresponde: los argumentos de la función deben calcularse antes de calcular la función misma. Pero hay otra opción: el llamado cálculo parcial. En este caso, si solo se calcula una parte de los argumentos, aún podemos calcular (reducir) esa parte de la función que usa solo estos argumentos. Este enfoque generalmente se denomina modelo de computación "vago".En contraste con esto, el modelo de cómputo de Turing a veces se llama "enérgico" o "codicioso"; los lenguajes de programación creados sobre esta base se denominarán imperativos a continuación. Una característica importante de los cálculos "vagos" es que si una subrutina se escribe en función de, por ejemplo, tres argumentos, pero en realidad usa solo dos, entonces no hay necesidad de calcular este tercer argumento para calcular el valor de la función.

Y esto nos da interesantes posibilidades prácticas. Por ejemplo, la capacidad de trabajar con secuencias infinitas. Sería fácil para cualquiera que comenzara a conocer la programación funcional en general y con el lenguaje Haskell en particular para comprender esta forma de obtener los primeros n números de Fibonacci:

fibonacci2 a b = a : (fibonacci2 b (a+b))
fibonacci = fibonacci2 1 1

nfibonacci n = take n fibonacci

Explicación para Extraños con Haskell
fibonacci2 , , fibonacci2 b (a+b). ( !) :
def fibonacci2(a, b) :
    return [a] + fibonacci2(b, a+b)

def fibonacci() :
    return fibonacci2(1, 1)

def nfibonacci(n) :
    res = []
    data = fibonacci()
    for i in range(n) :
      res.append( data[i] )
    return res

nfibonacci.

La función de Fibonacci (y esta es precisamente la función) genera una lista interminable de números. Si utilizamos el modelo computacional que nos es familiar, entonces nfibonacci nunca podría haber terminado (lo cual, recuerdo, es perfectamente aceptable y no contradice las nociones de su "computabilidad"). Pero si usamos el modelo de cálculo "vago", es fácil notar que tan pronto como n toma un valor específico, para obtener el valor de la función nfibonacci, solo necesitamos los primeros n elementos de la lista que son el resultado de la función fibonacci . En este caso, podemos actuar así: obtener el elemento de la lista: realizar la reducción, el siguiente elemento es otro paso de reducción, n-th argumento: la reducción condujo a la obtención del valor de la función. Es decir, en este caso obtenemos un resultado por un tiempo finito a pesar del "ciclo" del procedimiento para construir una lista de números de Fibonacci.

Aquí, un lector particularmente entusiasta de mentalidad imperativa exclama: "¡ Pero espera, solo un idiota franco implementará la construcción de una lista de números de Fibonacci de esta manera! Hay soluciones obvias que no conducen a un bucle"Y él, por supuesto, tendrá razón. La transferencia estúpida de una solución que involucra la implementación del modelo de cálculos" perezosos "en un programa para cálculos" codiciosos "no es realmente un indicador de gran inteligencia. Si ofrece esta tarea a un programador que ha mantenido toda su vida profesional Lealtad, digamos, al lenguaje C, entonces probablemente ofrecerá una variante con un ciclo con un contador y dos variables de estado.

Pero el punto no son los números de Fibonacci en sí mismos. El hecho es que la regla para construir una secuencia en este ejemplo está separada del método de procesamiento de sus elementos. Y esta es una propiedad útil que es deseable poder reproducir en casos más complejos, cuando los elementos de la secuencia procesada se generan de una manera bastante complicada y la simple transferencia de la solución "de frente" para la secuencia de Fibonacci en este caso es ineficaz en el tiempo, la memoria o simplemente conduce a código, cuya comprensión no es accesible a los simples mortales. Tal aspiración es natural y puede realizarse, por ejemplo, mediante el uso de iteradores o generadores. En python, por ejemplo, podemos hacer esto:

def fibonacci() :
    a = 1
    b = 1
    yield a
    yield b
    while True :
      c = a + b
      yield c
      a = b
      b = c
     
def nfibonacci(n) :
    return [e for e in itertools.islice(fibonacci(), n)]

Aquí fibonacci () es un generador que crea una secuencia elemento por elemento. Y en este caso, en lugar de fibonacci, puede haber una función generadora de cualquier complejidad. Si traemos el código por completo, incluido el código del capó del motor, obtenemos un diseño de software muy complejo y completamente imperativo. Pero la versión final es bastante "funcional". En C ++, uno podría hacer un truco similar al tener una clase especial de Fibonachi e iteradores para ello. La decisión variará según las características del lenguaje de programación y las preferencias del programador, pero el objetivo seguirá siendo el mismo: dividir a nivel de organización del programa una forma de construir una secuencia de longitudes previamente desconocidas y una forma de procesar sus elementos.

La diferencia es que en el marco del enfoque funcional, dicha organización del programa es natural y se impone por el método mismo de su implementación, mientras que en el marco del programa imperativo requiere un trabajo creativo adicional, incluida la creación de conceptos y patrones de diseño adicionales.

La limpieza es la clave de la salud.


Otra propiedad, en presencia de la cual hablan de un enfoque funcional para la programación, es la "pureza" de las funciones. Es la ausencia de efectos secundarios. Es decir, una llamada de función con el mismo conjunto de argumentos debería conducir al mismo resultado. El autor de la publicación citada describió con suficiente detalle por qué en los programas ejecutados en un estilo imperativo, esta propiedad también es deseable. Sin embargo, no es más que una consecuencia del modelo de cálculos utilizado.

La razón por la cual todas las funciones en un programa funcional deben estar limpias es simple. Suponiendo la presencia de estos mismos efectos secundarios, resulta que el orden en que los argumentos de la función obtienen su valor afecta directamente el resultado de la función. Podemos decir que esto también es cierto en el marco del enfoque imperativo, pero en el caso de la "pereza" de los cálculos, todo es mucho peor. Incluso si suponemos que los argumentos de la función pueden calcularse independientemente unos de otros en un orden arbitrario, la "pereza" aún implica que (condicionalmente) no todo el código de la función se ejecutará de una sola vez. Se ejecutará en partes, dependiendo de dos cosas: de hecho, la estructura de la función que el compilador condicional nos proporcionará amablemente y el orden en el que presentaremos la función con sus argumentos.

Es natural para nosotros esperar que si primero definimos una función

def f(x,y) :
  ...

y despues de ella
def g(x, y) :
  return f(y, x)

entonces el resultado de llamar a g (a, b) será igual al resultado de llamar a f (b, a) para cualquier valor computable independiente de a y b . Pero si f tiene efectos secundarios que afectan el cálculo de los valores de los argumentos, nuestras expectativas pueden ser brutalmente engañadas . Por ejemplo, al calcular b , se produce la lectura del archivo, y al calcular f , también se lee del mismo archivo. En los cálculos "perezosos", no sabemos de antemano qué parte del código (para b o para f) se ejecutará primero. Eso significa que no sabemos qué resultado dará el programa, incluso si conocemos el contenido del archivo que debería leer. Tal comportamiento es en principio inaceptable y, por lo tanto, debe excluirse categóricamente. Por lo tanto, dentro del marco del modelo de cálculos "perezosos" (efectos no controlados) de la función debería estar prohibido .

Si se aplica el codicioso orden de los cálculos, los efectos secundarios son mucho más predecibles. Por esto y solo por esta razón, están permitidos en la programación imperativa. Pero si abusa de ellos, la función se convertirá en un error. Entonces, no debes abusar de ellos. Entonces, nuevamente, el concepto de “pureza” que es natural en la programación funcional es muy demandado en el mundo imperativo.

En consecuencia, la tesis
Programa funcional: un programa que consiste en funciones puras
incorrecto si se ve como una definición. Sí, un programa funcional consta de funciones "puras", pero un programa que consiste en funciones puras no tiene que ser "funcional" en absoluto. Esta es su propiedad, pero no una propiedad definitoria.

Sin embargo, hay un problema. La capacidad de guardar el estado e incluso la entrada-salida banal son cosas directamente relacionadas con los efectos secundarios. Y la vida sin ellos está llena de dolor y sufrimiento. Surge la pregunta: ¿cómo combinar los efectos secundarios y los cálculos "perezosos"? La respuesta en general es de ninguna manera. La respuesta es correcta: en cada caso particular se debe buscar una solución particular satisfactoria. Resultó que muchas formas de reproducir cálculos con efectos secundarios sin violar el concepto de "pureza" de los cálculos se ajustan al concepto general de la mónada, tomado de la teoría de categorías. No me gustaría volver a intentar explicar qué es y con qué se come, aunque solo sea porque en cualquier caso no reemplazará (y en mi experiencia ni siquiera simplificará) una explicación de cómo se pueden implementar específicamente las variables de estado,excepciones y cosas similares en lenguajes funcionales "puros". La moraleja principal es que la programación imperativa es una fuente de inspiración para lo funcional, así como funcional para lo imperativo. Además, a veces una idea pasa por un concepto competitivo como a través de un filtro, regresa de forma alterada y da lugar a la aparición de una nueva herramienta.

¿Se necesitan mónadas en un mundo imperativo? No tengo una opinión establecida sobre este tema. El autor de esteayuno seguro que necesitaba. Me inclino a dudar de esta afirmación, ya que el uso del concepto de una mónada en programas funcionales generalmente está relacionado con el hecho de que se puede formular un cierto algoritmo independientemente de los efectos secundarios específicos que oculta esta mónada. En otras palabras, si un tipo de datos definido por el usuario (hipotético, aún no creado por la humanidad) satisface los requisitos para una mónada, entonces el algoritmo escrito para él funcionará correctamente. Esto es conveniente principalmente en estudios teóricos. Pero hay un par de matices. En primer lugar, no está muy claro por qué esconderse en el envoltorio, los efectos secundarios son efectivos en los idiomas para los cuales son un fenómeno natural. En segundo lugar,Cuando se escriben programas específicos con tipos de datos específicos y una arquitectura de destino específica, este algoritmo generalizado se ve obligado a someterse a una reestructuración para aumentar la productividad. Es posible escribir algoritmos generalizados utilizando mónadas en un estilo imperativo, pero la conveniencia de este enfoque plantea mis dudas. Es poco probable que el hecho de que algún análogo tal vez de tipo std :: opcional de C ++ sea declarado mónada afecte de alguna manera la práctica de su uso.

?


Las funciones de orden superior son una herramienta tan ampliamente utilizada en programas funcionales que el hecho de admitir algo similar en algún lenguaje de programación es suficiente para que algunas personas extrañas reconozcan este lenguaje como funcional. ¿Qué son las "funciones de orden superior"? Esta es una función que opera en otras funciones como argumentos, o devuelve una función como resultado. Parece que aquí puede causar debate? Resulta mucho Para empezar, lo que generalmente se entiende por el término "función". Los programadores generalmente razonan simplemente: si algo se puede llamar como una función, entonces se puede considerar como una función. En el marco del enfoque imperativo, esto tiene sentido, ya que intuitivamente una función es que para un conjunto dado de argumentos da un cierto resultado.Si admitimos la presencia de efectos secundarios, entonces, en el sentido práctico, realmente no hay diferencia entre la función "normal" del lenguaje y, por ejemplo, el objeto de la clase que tiene el operador sobrecargado ().

Pero en la programación funcional, dicha definición de una función no es suficientemente constructiva, ya que no permite interpretar el concepto de un cálculo parcial de esta función en sí. En la programación funcional, una función no es "uno de" los elementos estructurales de un programa, sino en cierto sentido lo contrario: todos los elementos del programa son funciones. Por lo tanto, de hecho, esto es "programación funcional". Y, de nuevo, si todo es una función, es decir, cualquier argumento de cualquier función es una función, entonces cualquier función con argumentos es una función de orden superior. Por lo tanto, las funciones de orden superior son un elemento natural de un programa funcional. Tanto es así que incluso su asignación en una clase separada no tiene mucho sentido.

Como una función de orden superior, generalmente se asigna un mapa o un pliegue .. Pero consideraremos una función más trivial, cualquiera , de los dos argumentos f (x, y) . Dentro del marco del modelo de cálculos "perezosos", los argumentos de esta función se calcularán solo cuando realmente sean necesarios. Supongamos que el primer argumento es x .

Calculamos este argumento, proporcionamos su valor f y, además, calculamos todo lo que podemos calcular sin usar el valor del argumento y . Luego, el resto de los cálculos se pueden representar como una nueva función, ya independiente de x , por ejemplo, g (y) . Pero en este caso, nada nos impide presentar formalmente f no en función de dos argumentos, sino en función de un argumentof (x) , cuyo resultado es otra función g (y) . En otras palabras, dentro del marco del enfoque funcional, cualquier función de los argumentos N> 1 es una función de orden superior, ya que puede interpretarse como una función de un argumento, cuyo resultado es la función de los argumentos N-1 .

¿Podemos implementar este comportamiento como parte de un enfoque imperativo? Por supuesto que podemos. En python, escribiríamos algo como lo siguiente:

def partial(f, x) :
	def g(*args) :
		return f(x, *args)
	return g

Al llamar a la función parcial , cuyo primer argumento es la función de N argumentos, y el segundo es el valor de su primer argumento, obtenemos la función N-1 del argumento. Ahora podemos usar la nueva función donde sea que podamos usar la función de argumento N-1 . Es decir, obtuvieron lo mismo que en el programa funcional. ¿Entonces? No, no así. Si estuviéramos tratando con un programa verdaderamente funcional, entonces cuando llamábamos parcial , calcularíamos parte del valor del primer argumento. En algunos casos, incluso podría resultar que g es un valor constante. ¿Qué tenemos en un análogo imperativo? El valor pasado del argumento xRecién recordado (agregado al contexto de la función g ). Cuando llamamos a g , el valor de x se tomará de los contenedores y simplemente se sustituirá en f . Es decir, no hay diferencia en la forma, sino en el contenido: significativo.

El uso de funciones de funciones es conveniente porque le permite describir naturalmente muchos algoritmos importantes. Por lo tanto, se vieron obligados a aparecer en lenguajes de programación imperativos. Y aparecieron. Pero dado que usan un modelo de cálculo diferente, esto habría requerido el desarrollo de nuevos conceptos. Y fueron desarrollados. Por ejemplo, el cierre descrito anteriormente. Es decir, las funciones de órdenes superiores en lenguajes imperativos corresponden a lo que se puede observar en lenguajes funcionales, solo externamente. Pero el contenido es completamente diferente. ¿Es esto importante para el programador? Probablemente no, pero solo si comprende bien cómo funcionan esos mecanismos que implementan características similares en su lenguaje de programación favorito. De lo contrario, puede, por ejemplo, implementar "aplicación parcial", cerrar al construir una nueva función (bueno, olo que en su caso se verá como una función) en lugar de valor y obtendrá un comportamiento interesante del programa. Y después de eso, grita sobre la inferioridad del enfoque funcional.

Entonces, ¿quién engañaba a quién?


En esta etapa de la presentación, es bastante posible poner un punto y coma y volver a la pregunta principal. Desde ahora podemos formular las siguientes declaraciones:

  • La principal diferencia entre la programación funcional e imperativa no es la propiedad de la pureza de las funciones, ni la presencia de funciones anónimas, funciones de órdenes superiores, mónadas, polimorfismo paramétrico o cualquier otra cosa. La principal diferencia es el uso de un modelo de cálculo diferente. Todo lo demás no es más que consecuencias.
  • , , . . , «» «» . , . .
  • , , , . . — .
  • , . , «» ; , . , - , - . .
  • , . , . , , , . .

La programación funcional es lo que (probablemente) le dijeron. Estos son la reducción beta, los combinadores de punto fijo, las mónadas, la escritura Hindley-Milner y más. No confunda el envoltorio con el contenido. FP no se basa en las matemáticas más simples, no se puede dominar por un par de noches con un vaso de té; es poco probable que se proyecte directamente sobre sus problemas y proyectos apremiantes; no obtendrá un beneficio rápido y garantizado de este conocimiento. Pero muchos elementos de lo que está en el enfoque funcional son prestados, procesados ​​y finalmente implementados en lenguajes de programación orientados al desarrollo de grandes proyectos. Sí, están organizados de manera diferente a sus antepasados ​​funcionales, pero esto no los hace menos útiles. Solo un idiota clínico transmitirá un mensaje serio de que Haskell es un mal lenguaje,porque es difícil escribir un programa para cualquier tipo de contabilidad. Una persona cargada con la presencia de inteligencia, incluso desde el punto de vista de su actividad profesional, sin una profunda inmersión en las complejidades de la teoría, es bastante capaz de comprender exactamente qué prácticas de la programación funcional deberían adoptarse para mejorar su código. Por una demostración convincente de la cual expreso gratitudPsyhast.

Aprende programación funcional. En tu nombre.

More articles:


All Articles