Programación funcional

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Diagrama del funcionamiento de una subrutina.

En ciencias de la computación, la programación funcional es un paradigma de programación declarativa basado en la utilización de funciones aritméticas que no maneja datos mutables o de estado. Enfatiza la aplicación de funciones, en contraste con el estilo de programación imperativa, que enfatiza los cambios de estado. La programación funcional tiene sus raíces en el cálculo lambda, un sistema formal desarrollado en los años 1930 para investigar la definición de función, la aplicación de las funciones y la recursión. Muchos lenguajes de programación funcionales pueden ser vistos como elaboraciones del cálculo lambda.

En la práctica, la diferencia entre una función matemática y la noción de una "función" utilizada en la programación imperativa es que las funciones imperativas pueden tener efectos secundarios, al cambiar el valor de cálculos realizados previamente. Por esta razón carecen de transparencia referencial, es decir, la misma expresión sintáctica puede resultar en valores diferentes en diferentes momentos dependiendo del estado del programa siendo ejecutado. Con código funcional, en contraste, el valor generado por una función depende exclusivamente de los argumentos alimentados a la función. Al eliminar los efectos secundarios se puede entender y predecir el comportamiento de un programa mucho más fácilmente, y esta es una de las principales motivaciones para utilizar la programación funcional.

Los lenguajes de programación funcional, especialmente los que son puramente funcionales, han sido enfatizados en el ambiente académico principalmente y no tanto en el desarrollo de software comercial. Sin embargo, lenguajes de programación importantes tales como Scheme, Erlang, Rust, Objective Caml y Haskell, han sido utilizados en aplicaciones comerciales e industriales por muchas organizaciones. La programación funcional también es utilizada en la industria a través de lenguajes de dominio específico como R (estadística), Mathematica (matemáticas simbólicas), J y K (análisis financiero), F# en Microsoft.NET y XSLT (XML). Lenguajes de uso específico usados comúnmente como SQL y Lex/Yacc, utilizan algunos elementos de programación funcional, especialmente al procesar valores mutables. Las hojas de cálculo también pueden ser consideradas lenguajes de programación funcional.

La programación funcional también puede ser desarrollada en lenguajes que no están diseñados específicamente para la programación funcional. En el caso de Perl, por ejemplo, que es un lenguaje de programación imperativo, existe un libro que describe como aplicar conceptos de programación funcional. JavaScript, uno de los lenguajes más ampliamente utilizados en la actualidad, también incorpora capacidades de programación funcional. Python también incorpora particularidades de los lenguajes funcionales como listas de comprensión y funciones de tratamiento de listas como matemática de conjuntos. Java en su versión 8, esta incorporando la programación funcional, así como el uso de las expresiones lambda.

Utilidad[editar]

El objetivo es conseguir lenguajes expresivos y matemáticamente elegantes, en los que no sea necesario bajar al nivel de la máquina para describir el proceso llevado a cabo por el programa, y evitar el concepto de estado del cómputo. La secuencia de computaciones llevadas a cabo por el programa se rige única y exclusivamente por la reescritura de definiciones más amplias a otras cada vez más concretas y definidas, usando lo que se denominan "definiciones dirigidas".

Características[editar]

Los programas escritos en un lenguaje funcional están constituidos únicamente por definiciones de funciones, entendiendo éstas no como subprogramas clásicos de un lenguaje imperativo, sino como funciones puramente matemáticas, en las que se verifican ciertas propiedades como la transparencia referencial (el significado de una expresión depende únicamente del significado de sus subexpresiones), y por tanto, la carencia total de efectos colaterales.

Otras características propias de estos lenguajes son la no existencia de asignaciones de variables y la falta de construcciones estructuradas como la secuencia o la iteración (lo que obliga en la práctica a que todas las repeticiones de instrucciones se lleven a cabo por medio de funciones recursivas).

Existen dos grandes categorías de lenguajes funcionales: los funcionales puros y los híbridos. La diferencia entre ambos estriba en que los lenguajes funcionales híbridos son menos dogmáticos que los puros, al admitir conceptos tomados de los lenguajes imperativos, como las secuencias de instrucciones o la asignación de variables. En contraste, los lenguajes funcionales puros tienen una mayor potencia expresiva, conservando a la vez su transparencia referencial, algo que no se cumple siempre con un lenguaje funcional híbrido.

Funciones de primera clase y de orden superior[editar]

Funciones de orden superior son funciones que pueden tomar otras funciones como argumentos o devolverlos como resultados. En cálculo , un ejemplo de una función de orden superior es el operador diferencial d / dx , que devuelve la derivada de una función f .

Las funciones de orden superior están estrechamente relacionadas con las funciones de primera clase en las cuales las funciones de orden superior y las funciones de primera clase pueden recibir como argumentos y resultados otras funciones. La distinción entre los dos es sutil: "de orden superior", describe un concepto matemático de funciones que operan sobre otras funciones, mientras que la "primera clase" es un término informático que describe las entidades del lenguaje de programación que no tienen ninguna restricción de su utilización (por lo tanto funciones de primera clase pueden aparecer en cualquier parte del programa que otras entidades de primer nivel como los números pueden, incluidos como argumentos a otras funciones y como sus valores de retorno).

Las funciones de orden superior permiten la aplicación parcial, una técnica en la que se aplica una función a sus argumentos uno a la vez, con cada aplicación devolver una nueva función que acepta el siguiente argumento. Esto le permite a uno expresar, por ejemplo, la función sucesor como el operador de suma aplicada parcialmente al número natural uno.

Funciones puras[editar]

Las funciones puramente funcionales (o expresiones) no tienen efectos secundarios (memoria o E/S). Esto significa que las funciones puras tienen varias propiedades útiles, muchas de las cuales pueden ser utilizados para optimizar el código:

  • Si no se utiliza el resultado de una expresión pura, se puede eliminar sin afectar a otras expresiones.
  • Si una función pura se llama con parámetros que no causan efectos secundarios, el resultado es constante con respecto a la lista de parámetros (a veces llamada transparencia referencial), es decir, si la función pura se llama de nuevo con los mismos parámetros, el mismo resultado será devuelto (esto puede habilitar las optimizaciones de almacenamiento en caché).
  • Si no hay una dependencia de datos entre dos expresiones puras, entonces su orden puede ser invertido, o pueden llevarse a cabo en paralelo y que no pueda interferir con los otros.
  • Si el lenguaje no permite efectos secundarios, entonces cualquier estrategia de evaluación se puede utilizar, lo que da la libertad al compilador para reordenar o combinar la evaluación de expresiones en un programa (por ejemplo, usando la poda).

La mayoría de los compiladores de lenguajes imperativos detectan funciones puras automáticamente y realizan la eliminación de subexpresiones comunes. Sin embargo no siempre es posible detectarlo en bibliotecas pre-compiladas, porque por norma general no dan esta información. Esto provoca que no se puedan realizar optimizaciones que podrían aplicar a dichas funciones externas. Algunos compiladores, como gcc, sí que añaden palabras claves adicionales para que el programador marque explícitamente como puras aquellas funciones externas que proceda, de modo que se le apliquen las optimizaciones pertinentes. Fortran 95 también permite que declarar funciones "puras".

Recursividad[editar]

Iterar en los lenguajes funcionales es normalmente llevado a cabo mediante recursividad. Las funciones recursivas se invocan a sí mismas, permitiendo que una operación se realice una y otra vez hasta alcanzar el caso base. Aunque algunas recursividades requieren el mantenimiento de una pila, la recursividad mediante una cola puede ser reconocida y optimizada mediante un compilador dentro del mismo código utilizado, para implementar las iteraciones en un lenguaje imperativo. El estándar del esquema del lenguaje requiere implementaciones para conocer y optimizar la recursividad mediante una cola. La optimización de la recursividad mediante una cola puede ser implementada transformando el programa a un estilo de pase de continuidad durante la compilación, entre otros enfoques.

Los patrones comunes de recursividad puede ser factorizados usando funciones comunes más grandes, con “catamorfismos” y “anamorfismos” (pliegues y despliegues), siendo estos los ejemplos más evidentes. Tal y como las mayores funciones más comunes tienen un rol análogo para construir estructuras de control se tienen los iteradores en los lenguajes imperativos.

La mayoría de los lenguajes de programación funcional de propósito general permiten la recursividad sin restricciones y superan el test de Turing, lo que hace que el programa que se interrumpe no pueda tomar un decisión, lo que puede causar una falta de solidez en el razonamiento ecuacional y generalmente requiere introducir inconsistencia dentro de la lógica expresada por los tipos del sistema del lenguaje. Algunos lenguajes de propósito especial como Coq permiten tan sólo recursividad bien fundamentada y tienen una normalización fuerte(cálculos no finalizados pueden ser expresados tan sólo con flujos de valores infinitos llamados codata) En consecuencia, estos lenguajes fallan el test de Turing y declarar funciones ciertas en ellos es imposible, pero pueden declarar una amplia clase de cálculos interesantes mientras evitan los problemas producidos por la recursividad sin restricciones. La programación funcional limitada a la recursividad bien construida con unas cuantas restricciones más se llama programación funcional total.

Evaluación estricta frente a la no estricta[editar]

Los lenguajes funcionales pueden ser clasificados por el hecho de usar evaluación estricta(eager) o no estricta(lazy), conceptos que hacen referencia a cómo los argumentos de las funciones son procesados cuando una expresión está siendo evaluada. La diferencia técnica está en la notación semántica de las expresiones que contienen cálculos fallidos o divergentes. Bajo la evaluación estricta, la evaluación de cualquier término que contenga un sub-término fallido hará que este sea de por sí fallido.

Por ejemplo, la expresión:

print length([2+1, 3*2, 1/0, 5-4])

fallará bajo evaluación estricta por la división por cero en el tercer elemento de la lista. Utilizando evaluación no estricta, el tamaño de la función devolverá un valor de 4( por ejemplo el número de elementos de la lista) ya que evaluar esto no afectará al estar evaluando los que componen la lista. En resumen, la evaluación estricta evalúa por completo los argumentos a menos que sus valores requieran evaluar la propia función que se llama a sí misma.

La implementación de la estrategia común para evaluación no estricta en los lenguajes funcionales es la de reducción mediante un grafo. La evaluación no estricta es utilizada por defecto en multitud de lenguajes funcionales puros, incluidos Miranda, Clean y Haskell.

Hughes (1984) defendía la evaluación no estricta como un mecanismo para mejorar la modularidad de los programas a través de la separación de tareas, a partir de la implementación de productores y consumidores de flujos de datos de forma fácil e independiente. Launchbury (1993) describe algunas dificultades que tenía la evaluación no estricta, particularmente al analizar los requisitos de almacenamiento de los programas, y propone una semántica operacional para ayudar durante el análisis. Harper (2009) propone incluir ambas técnicas (evaluación estricta y no estricta) en el mismo lenguaje, utilizando los tipos del sistema del lenguaje para distinguirlas.

Tipo de sistemas[editar]

Especialmente desde el desarrollo de tipos de inferencia de Hindley - Milner en la década de 1970, los lenguajes de programación funcionales han tendido a utilizar el cálculo con tipo lambda, en comparación con el cálculo lambda sin tipo utilizado en Lisp y sus variantes (tales como el lenguaje scheme). El uso de tipos de datos algebraicos y la coincidencia de patrones hace que la manipulación de estructuras de datos complejas convenientes y expresivos, la presencia de comprobaciones estrictas de tipos en tiempo de compilación hace que los programas sean más fiable, mientras que la inferencia de tipos libera al programador de la necesidad de declarar manualmente los tipos para el compilador.

Algunos lenguajes funcionales orientados a la investigación, tales como Coq, Agda, Cayenne y Epigram se basan en la teoría de tipo intuicionista, que permite a los tipos a depender de los términos. Estos tipos se denominan tipos dependientes. Estos sistemas de tipo no tienen un tipo decidible inferencia y son difíciles de entender y programar con plantillas de citación. Pero tipos dependientes pueden expresar proposiciones arbitrarias en la lógica de predicados.

A través del isomorfismo de Curry-Howard, entonces, mecanografiados a programas en estas lenguas se convierten en una forma de escribir las pruebas matemáticas formales de las que un compilador puede generar código de certificado. Si bien estas lenguas son principalmente de interés en la investigación académica (incluyendo las matemáticas formalizadas), han comenzado a ser utilizado en la ingeniería también. Compcert es un compilador para un subconjunto del lenguaje de programación C que se escribe en Coq y verificó formalmente. Una forma limitada de tipos dependientes llamados tipos de datos algebraicos generalizados (GADTs) puede ser implementado de una manera que ofrece algunos de los beneficios de la programación dependiente escrito, evitando la mayor parte de su inconveniencia. GADTs están disponibles en el Glasgow Haskell Compiler, en OCaml (desde la versión 4.00) y en Scala y se han propuesto como adiciones a otros idiomas, incluyendo Java y C#.

La programación funcional en lenguajes no funcionales[editar]

Es posible utilizar un estilo de programación funcional en lenguajes que tradicionalmente no se consideran lenguajes funcionales. Por ejemplo, tanto D y Fortran95 se apoyan explícitamente en funciones puras. Funciones de primera clase, se han añadido lentamente a los lenguajes principales. Por ejemplo, a principios de 1994, el apoyo a lambda, filtro, mapa, y reducir esta en Python. Luego, durante el desarrollo de Python 3000, Guido van Rossum pidió la eliminación de estas características. Sin embargo, más tarde cambió de opinión, y sólo la reducción fue eliminado, a pesar de que sigue siendo accesible a través de los módulos de biblioteca functools estándar. Funciones de primera clase también fueron introducidas en PHP 5.3, Visual Basic9, C#3.0 y C++11.

En Java, las clases anónimas a veces pueden ser utilizados para simular [[Clausura_(informática)|clausuras]. Sin embargo, las clases anónimas no son siempre los reemplazos completos de las clausuras, ya que tienen capacidades más limitadas. Por ejemplo, Java 8, incluye expresiones lambda para reemplazar determinadas clases anónimas. Sin embargo, la presencia de excepciones con comprobaciones en este lenguaje puede desaconsejar el uso de programación funcional, ya que puede ser necesario para capturar las excepciones que se deben controlar para después volverlas a lanzar ellos (problema este que sin embargo no se produce en otros lenguajes sobre JVM que no tienen excepciones comprobadas, como es Scala).

Muchos patrones de diseño orientado a objetos se pueden expresar en términos de programación funcional por ejemplo : el patrón de estrategia simplemente dicta el uso de una función de orden superior, y el patrón de visitantes corresponde aproximadamente a un catamorfismo, o doble también conocido como reducir, comprimir, o inyectar, se refiere a una familia de funciones de orden superior que analiza una estructura de datos recursiva y se recombinan con el uso de una operación de combinación.

Del mismo modo, la idea de los datos inmutables de la programación funcional se incluye a menudo en lenguajes de programación imperativa, por ejemplo, la tupla de Python, que es una matriz inmutable.

Ventajas de usar un paradigma funcional[editar]

Entre las ventajas que suelen citarse de usar un paradigma funcional en la programación de computadoras, están las siguientes:[1]

  • Ausencia de efectos colaterales
  • Proceso de depuración menos problemático
  • Pruebas de unidades más confiables
  • Mayor facilidad para la ejecución concurrente

Simulación de estados[editar]

Hay tareas (como por ejemplo, el mantenimiento del saldo de una cuenta bancaria) que a menudo parecen implementadas con estados. La programación funcional pura actúa sobre esas tareas, tareas de entrada/salida de datos tales como entrada de datos por parte del usuario y mostrar resultados por pantalla, de una forma diferente.

El lenguaje de programación funcional Haskell lo implementa usando mónadas, estructura que representa cálculos que se describen como una secuencia de pasos, derivada de la teoría de categorías.

Las mónadas ofrecen una forma de abstraer ciertos tipos de patrones computacionales, incluyendo (pero no limitado a) el diseño de operaciones con estados cambiantes (y otras acciones secundarias tales como entrada/salida de datos) de una manera imperativa sin perder la pureza. Mientras las mónadas existentes pueden ser fáciles de aplicar en un programa usando las plantillas y ejemplos adecuados, muchos estudiantes tienen problemas para entenderlo conceptualmente, por ejemplo cuando se les pide definir nuevas mónadas. (lo que a veces resulta necesario para ciertos tipos de librerías)[2]

Otra forma en la que los lenguajes funcionales pueden simular estados es rodeando una estructura de datos que representa el estado actual como un parámetro para llamadas a funciones. En cada llamada a función, se crea una copia de esta estructura de datos que se diferencia con el resultado de la función. Esto se conoce como “estilo de paso de estado”.

Los lenguajes funcionales no puros normalmente incluyen métodos para gestionar el cambio de estado más directamente. Clojure por ejemplo, usa una gestión de referencias que pueden ser actualizadas aplicando funciones puras al estado actual. Este tipo de enfoque permite el cambio de estado, promoviendo el uso de funciones puras como la mejor forma de realizar cálculos.

Métodos alternativos como Hoare logic, el cual es un sistema formal con un conjunto de reglas lógicas que sirven para razonar con rigor acerca de la corrección de programas, y la singularidad han sido desarrollados para realizar un seguimiento de los efectos secundarios en los programas. Algunos lenguajes de investigación modernos usan sistemas de efectos para hacer explícita la presencia de efectos colaterales.

Cuestiones de eficiencia[editar]

Los lenguajes de programación son típicamente menos eficientes en el uso de CPU y memoria que los lenguajes imperativos como pueden ser C y Pascal. Esto está relacionado con el hecho de que algunas estructuras de datos de tamaño indefinido como los vectores tienen una programación muy sencilla usando el hardware existente, el cual es una máquina de Turing bastante evolucionada. Se puede acceder muy eficientemente a las posiciones del array con CPUs con un alto grado de perfeccionamiento, haciendo pre búsquedas eficientemente a través de las memorias caché o manejado con instrucciones SIMD. Y no es fácil crear componentes homólogos inmutables de propósito general con la misma eficiencia. Para lenguajes puramente funcionales, el peor caso descendente es el logarítmico en el número de celdas de memoria usadas, porque las estructuras de memoria que cambian de tamaño pueden ser representadas por estructuras de datos puramente funcionales con tiempo de acceso logarítmico, como por ejemplo un árbol equilibrado. Sin embargo, tales retrasos no son universales. Para programas que realizan cálculos numéricos intensivos, los lenguajes funcionales tales como OCaml y Clean son algo más lentos que C. Para programas que manejan grandes matrices y bases de datos multidimensionales, los vectores de los lenguajes funcionales, como J y K, fueron diseñados optimizando su velocidad.

La inalterabilidad de los datos puede llevar en muchos casos a ejecuciones eficientes permitiendo al compilador hacer suposiciones que en un lenguaje imperativo resultarían arriesgadas, aumentando las probabilidades para la expansión en línea, que es una optimización del compilador que sustituye en el lugar de la llamada a una función con el cuerpo del destinatario de la llamada mejorando el uso del tiempo y espacio en tiempo de ejecución.

La evaluación perezosa es una estrategia de evaluación que retrasa el cálculo de una expresión hasta que su valor sea necesario, también puede mejorar la velocidad del problema, incluso asintóticamente, mientras que puede reducir la velocidad por un factor constante, sin embargo puede producir pérdidas de memoria si se usa de manera incorrecta. Launchbury 1993 discute de manera teórica los problemas relacionados con las pérdidas de memoria de evaluación perezosa, y O’Sullivan et al. 2008 da algunos consejos prácticos para el análisis y la solución de estos problemas. Sin embargo, las implementaciones más generales de evaluación perezosa hace un uso extensivo de código sin referencia y los datos llevan a cabo un funcionamiento pobre en los procesadores modernos con un alto grado de paralelismo y cachés multinivel, donde un fallo de caché puede producir un coste de cientos de ciclos de reloj.

Lenguajes funcionales[editar]

Entre los lenguajes funcionales puros, cabe destacar a Haskell y Miranda. Los lenguajes funcionales híbridos más conocidos son Scala, Lisp, Clojure, Scheme, Ocaml, SAP y Standard ML (estos dos últimos, descendientes del lenguaje ML). Erlang es otro lenguaje funcional de programación concurrente. Mathematica permite la programación en múltiples estilos, pero promueve la programación funcional. R también es un lenguaje funcional dedicado a la estadística.[3] Recientemente Microsoft Research está trabajando en el lenguaje F# (Functional#).

Entre otros lenguajes que se podrían utilizar para programación funcional se podrían incluir a Perl, pues, aunque es un lenguaje de propósito muy general, se pueden realizar programas usando exclusivamente funciones definidas por el usuario; así como Python, como lenguaje que incorpora el paradigma funcional; o Ruby.

Estilos de codificación[editar]

Mientras que los programas imperativos tienden a proporcionar los pasos a dar por un programa, los funcionales tienden a enfatizar la composición y disposición de las funciones, sin especificar pasos de manera explícita.

Uso en la industria[editar]

La programación funcional es más popular en el ámbito académico que en ámbitos industriales. Sin embargo se ha empezado a usar importantes lenguajes de programación funcionales en sistemas comerciales o industriales. Un ejemplo de lenguaje de programación usado en el ámbito industrial es el Erlang, el cual fue desarrollado para poner en práctica el sistema de tolerancia a fallos en las telecomunicaciones. Importantes empresas como WhatsApp, Facebook, o T-Mobile optaron por Erlang como lenguaje en alguno de sus desarrollos. Otro ejemplo de uso de los lenguajes de programación funcionales en la industria es el caso del uso del Scheme de Lisp, que fue usado como base en el desarrollo de aplicaciones para los primeros ordenadores de la firma Apple Macintosh. De hecho, hoy en día,está siendo usado para desarrollo de sistemas de simulación y de control de telescopio. Haskell, es un ejemplo de lenguaje que creó con propósito de lenguaje de investigación pero que se ha usado para el desarrollo de sistemas aeroespaciales, programación web y diseño hardware. Otros lenguajes de programación funcionales han sido usados en ámbitos comerciales y financieros.

Véase también[editar]

Referencias[editar]