Funciones de primer clase y d'orde cimeru

Funciones d'orde cimeru son funciones que pueden tomar otres funciones como argumentos o devolvelos como resultaos. En cálculu , un exemplu d'una función d'orde cimeru ye l'operador diferencial d / dx , que devuelve la derivada d'una función f .

Les funciones d'orde cimeru tán estrechamente rellacionaes coles funciones de primer clase nes cualos les funciones d'orde cimeru y les funciones de primer clase pueden recibir como argumentos y resultaos otres funciones. La distinción ente los dos ye sutil: "d'orde cimeru", describe un conceutu matemáticu de funciones qu'operen sobre otres funciones, ente que la "primer clase" ye un términu informáticu que describe les entidaes del llinguaxe de programación que nun tienen nenguna restricción del so usu (polo tanto funciones de primer clase pueden apaecer en cualesquier parte del programa qu'otres entidaes de primer nivel como los númberos pueden, incluyíos como argumentos a otres funciones y como los sos valores de torna).

Les funciones d'orde cimeru dexen l'aplicación parcial, una téunica na que s'aplica una función a los sos argumentos unu al empar, con cada aplicación devolver una nueva función qu'acepta'l siguiente argumentu. Esto déxa-y a unu espresar, por casu, la función socesor como l'operador de suma aplicada parcialmente al númberu natural unu.

Funciones pures

Les funciones puramente funcionales (o espresiones) nun tienen efeutos secundarios (memoria o E/S). Esto significa que les funciones pures tienen delles propiedaes útiles, munches de les cuales pueden ser utilizaes pa optimizar el códigu:

• Si nun s'utiliza la resultancia d'una espresión pura, puede esaniciase ensin afectar a otres espresiones.

• Si una función pura llamar con parámetros que nun causen efeutos secundarios, la resultancia ye constante con al respeutive de la llista de parámetros (dacuando llamada tresparencia referencial), esto ye, si la función pura llamar de nuevu colos mesmos parámetros, el mesmu resultáu va ser devueltu (esto puede habilitar les optimizaciones d'almacenamientu en caxé).

• Si nun hai una dependencia de datos ente dos expresión pures, entós el so orde puede ser invertíu, o pueden llevase a cabu en paralelu y que nun pueda interferir colos otros.

• Si'l llinguaxe nun dexa efeutos secundarios, entós cualquier estratexa d'evaluación puede utilizase, lo que da la llibertá al compilador pa reordenar o combinar la evaluación d'espresiones nun programa (por casu, usando la fradadura).

La mayoría de los compiladores de llinguaxes imperativos detecten funciones pures automáticamente y realicen la eliminación de subexpresiones comunes. Sicasí non siempres ye posible detectalo en biblioteques pre-compiladas, porque por norma xeneral nun dan esta información. Esto provoca que nun se puedan realizar optimizaciones que podríen aplicar a diches funciones esternes. Dellos compiladores, como gcc, añaden pallabres claves adicionales por que'l programador marque explícitamente como pures aquelles funciones esternes que proceda, de cuenta que se-y apliquen les optimizaciones pertinentes. Fortran 95 tamién dexa declarar funciones "pures".

Recursividad

Iterar nos llinguaxes funcionales ye de normal lleváu a cabu por aciu recursividad. Les funciones recursivas invocar a sigo mesmes, dexando qu'una operación realícese una y otra vez hasta algamar el casu base. Anque delles recursividades riquen el caltenimientu d'una pila, la recursividad por aciu una cola puede ser reconocida y optimizada por aciu un compilador dientro del mesmu códigu utilizáu, pa implementar les iteraciones nun llinguaxe imperativu. L'estándar del esquema del llinguaxe rique implementaciones pa conocer y optimizar la recursividad por aciu una cola. La optimización de la recursividad por aciu una cola puede ser implementada tresformando'l programa a un estilu de pase de continuidá mientres la compilación, ente otros enfoques.

Los patrones comunes de recursividad puede ser factorizados usando funciones comunes más grandes, con “catamorfismos” y “anamorfismos” (plegues y esplegues), siendo estos los exemplos más evidentes. Tal que les mayores funciones más comunes tienen un rol análogu pa construyir estructures de control tiénense los iteradores nos llinguaxes imperativos.

La mayoría de los llinguaxes de programación funcional de propósitu xeneral dexen la recursividad ensin restricciones y superen el test de Turing, lo que fai que'l programa que s'ataya nun pueda tomar una decisión, lo que puede causar una falta de solidez nel razonamientu ecuacional y xeneralmente rique introducir inconsistencia dientro de la lóxica espresada polos tipos del sistema del llinguaxe. Dellos llinguaxes de propósitu especial como Coq dexen tan solo recursividad bien encontada y tienen una normalización fuerte(cálculos ensin rematar pueden ser espresaos tan solo con fluxos de valores infinitos llamaos codata) Arriendes d'ello, estos llinguaxes fallen el test de Turing y declarar funciones ciertes nellos ye imposible, pero pueden declarar una amplia clase de cálculos interesantes mientres eviten los problemes producíos pola recursividad ensin restricciones. La programación funcional llindada a la recursividad bien construyida con unes cuantes restricciones más se llama programación funcional total.

Evaluación estricta frente a la non estricta

Los llinguaxes funcionales pueden ser clasificaos pol fechu d'usar evaluación estricta(eager) o non estricta(lazy), conceutos que faen referencia a cómo los argumentos de les funciones son procesaos cuando una espresión ta siendo evaluada. La diferencia téunica ta na notación semántica de les espresiones que contienen cálculos fallíos o diverxentes. So la evaluación estricta, la evaluación de cualquier términu que contenga un sub-términu fallíu va faer qu'esti sía de por sí fallíu.

Por casu, la espresión:

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

va fallar so evaluación estricta pola división por cero nel tercer elementu de la llista. Utilizando evaluación non estricta, el tamañu de la función va devolver un valor de 4( por casu el númberu d'elementos de la llista) yá que evaluar esto nun va afectar al tar evaluando los que componen la llista. En resume, la evaluación estricta evalúa por completu los argumentos nun siendo que los sos valores rican evaluar la mesma función que se llama a sigo mesma.

La implementación de la estratexa común pa evaluación non estricta nos llinguaxes funcionales ye la d'amenorgamientu por aciu un grafo. La evaluación non estricta ye utilizada por defectu n'ensame de llinguaxes funcionales puros, incluyíos Miranda, Clean y Haskell.

Hughes (1984) defendía la evaluación non estricta como un mecanismu p'ameyorar la modularidad de los programes al traviés de la separación de xeres, a partir de la implementación de productores y consumidores de fluxos de datos de forma fácil ya independiente. Launchbury (1993) describe delles dificultaes que tenía la evaluación non estricta, particularmente al analizar los requisitos d'almacenamientu de los programes, y propón una semántica operacional p'ayudar mientres l'analís. Harper (2009) propón incluyir dambes téuniques (evaluación estricta y non estricta) nel mesmu llinguaxe, utilizando los tipos del sistema del llinguaxe pa estremales.

Sistemes de tipos

Especialmente dende'l desenvolvimientu de inferencia de tipos Hindley - Milner na década de 1970, los llinguaxes de programación funcionales tendieron a utilizar el cálculu lambda con tipos, en comparanza col cálculu lambda ensin tipos utilizáu en Lisp y les sos variantes (tales como'l llinguaxe scheme).

L'usu de tipos de datos alxebraicos y la coincidencia de patrones fai que la manipulación d'estructures de datos complexes convenientes y espresivos, la presencia de comprobaciones estrictes de tipos en tiempu de compilación fai que los programes sían más fiables, ente que la inferencia de tipos llibera al programador de la necesidá de declarar manualmente los tipos pal compilador.

Dellos llinguaxes funcionales empobinaos a la investigación, tales como Coq, Agda, Cayenne y Epigram basar na teoría de tipu intuicionista, que dexa a los tipos a depender de los términos. Estos tipos denominar tipos dependientes. Demostróse qu'estos sistemes de tipos sofisticaos son tan espresivos que los sos respeutivos problemes de inferencia de tipos dexen de ser decidibles. Los tipos dependientes pueden espresar proposiciones arbitraries na lóxica de predicaos intuicionista. Esta resultancia conozse como isomorfismu de Curry-Howard, y convierte a la programación funcional con una teoría de tipos intuicionista o equivalente nuna forma d'escribir pruebes matemátiques formales, de les qu'un compilador puede xenerar códigu certificáu. Magar estos llinguaxes son principalmente d'interés na investigación académica (incluyendo les matemátiques formalizaes), empezaron a ser utilizaos na inxeniería tamién. Compcert ye un compilador pa un subconxuntu del llinguaxe de programación C que ta escritu en Coq y el cual verificóse formalmente. Una forma llindada de tipos dependientes llamaos tipos de datos alxebraicos xeneralizaos (GADTs) pue ser implementáu d'una manera qu'ufierta dalgunos de los beneficios de la programación dependiente, evitando la mayor parte de la so inconveniencia. GADTs tán disponibles nel Glasgow Haskell Compiler, en OCaml (dende la versión 4.00) y en Scala y propunxéronse como amiestes a otros llinguaxes, incluyendo Java y C#.

La programación funcional en llinguaxes non funcionales

Ye posible utilizar un estilu de programación funcional en llinguaxes que tradicionalmente nun se consideren llinguaxes funcionales. Por casu, tantu D y Fortran95 sofítense explícitamente en funciones pures. Funciones de primer clase, añadiéronse amodo a los llinguaxes principales. Por casu, a principios de 1994, el sofitu a lambda, filtru, mapa, y amenorgar esta en Python. Depués, mientres el desenvolvimientu de Python 3000, Guido van Rossum pidió la eliminación d'estes carauterístiques. Sicasí, más tarde camudó d'opinión, y namái l'amenorgamientu foi esaniciáu, a pesar de que sigue siendo accesible al traviés de los módulos de biblioteca functools estándar. Funciones de primer clase tamién fueron introducíes en PHP 5.3, Visual Basic9, C#3.0 y C++11.

En Java, les clases anónimes dacuando pueden ser utilizaos p'asemeyar clausures. Sicasí, les clases anónimes nun son siempres los reemplazos completos de les clausures, yá que tienen capacidaes más llindaes. Por casu, Java 8, inclúi expresión lambda pa reemplazar determinaes clases anónimes. Sicasí, la presencia d'esceiciones con comprobaciones nesti llinguaxe puede desaconseyar l'usu de programación funcional, yá que puede ser necesariu pa prindar les esceiciones que se deben controlar pa dempués volveles a llanzar ellos (problema esti que sicasí non se produz n'otros llinguaxes sobre JVM que nun tienen esceiciones comprobaes, como ye Scala).

Munchos patrones de diseñu empobináu a oxetos pueden espresase en términos de programación funcional por casu : el patrón d'estratexa a cencielles dicta l'usu d'una función d'orde cimeru, y el patrón de visitantes correspuende aproximao a un catamorfismo, o doble tamién conocíu como amenorgar, estruyir, o inyectar, referir a una familia de funciones d'orde cimeru qu'analiza una estructura de datos recursiva y se recombinan col usu d'una operación de combinación.

De la mesma, la idea de los datos inmutables de la programación funcional inclúyese de cutiu en llinguaxes de programación imperativa, por casu, la tupla de Python, que ye una matriz inmutable.

Simulación d'estaos

Hai xeres (como por casu, el caltenimientu del saldu d'una cuenta bancaria) que de cutiu paecen implementaes con estaos. La programación funcional pura actúa sobre eses xeres, xeres d'entrada salida de datos tales como entrada de datos per parte del usuariu y amosar resultancies per pantalla, d'una forma distinta.

El llinguaxe de programación funcional Haskell implementar usando mónaes, estructura que representa cálculos que se describen como una secuencia de pasos, derivada de la teoría de categoríes.

Les mónaes ufierten una forma de abstraer ciertos tipos de patrones computacionales, incluyendo (pero ensin llindar a) el diseñu d'operaciones con estaos cambiantes (y otres aiciones secundaries tales como entrada/salida de datos) d'una manera imperativa ensin perder la pureza. Mientres les mónaes esistentes pueden ser fáciles d'aplicar nun programa usando les plantíes y exemplos fayadizos, munchos estudiantes tienen problemes pa entendelo conceptualmente, por casu cuando se-yos pide definir nueves mónaes. (lo que dacuando resulta necesariu pa ciertos tipos de llibreríes)^[2]

Otra forma na que los llinguaxes funcionales pueden asemeyar estaos ye arrodiando una estructura de datos que representa l'estáu actual como un parámetru pa llamaes a funciones. En cada llamada a función, créase una copia d'esta estructura de datos que s'estrema cola resultancia de la función. Esto conozse como “estilu de camín d'estáu”.

Los llinguaxes funcionales non puros de normal inclúin métodos pa xestionar el cambéu d'estáu más direutamente. Clojure por casu, usa una xestión de referencies que pueden ser actualizaes aplicando funciones pures al estáu actual. Esti tipu d'enfoque dexa'l cambéu d'estáu, promoviendo l'usu de funciones pures como la meyor forma de realizar cálculos.

Métodos alternativos como Hoare logic, que ye un sistema formal con un conxuntu de regles lóxiques que sirven pa razonar con rigor alrodiu de la correición de programes, y la singularidá fueron desenvueltos pa realizar un siguimientu de los efeutos secundarios nos programes. Dellos llinguaxes d'investigación modernos usen sistemes d'efeutos pa faer esplícita la presencia d'efeutos colaterales.

Cuestiones d'eficiencia

Los llinguaxes de programación nesti paradigma son típicamente menos eficientes nel usu de CPU y memoria que los llinguaxes imperativos como pueden ser C y Pascal. Esto ta rellacionáu col fechu de que delles estructures de datos de tamañu indefiníu como los vectores tienen una programación bien senciella usando'l hardware esistente, que ye una máquina de Turing abondo evolucionada. Puede aportase bien eficientemente a les posiciones del array con CPUs con un altu grau de perfeccionamiento, faciendo pre busques eficientemente al traviés de les memories caxé o remanáu con instrucciones SIMD. Y nun ye fácil crear componentes homólogos inmutables de propósitu xeneral cola mesma eficiencia. Pa llinguaxes puramente funcionales, el peor casu descendente ye'l logarítmicu nel númberu de celdes de memoria usaes, porque les estructures de memoria que camuden de tamañu pueden ser representaes por estructures de datos puramente funcionales con tiempu d'accesu logarítmicu, como por casu un árbol equilibráu. Sicasí, tales retrasos nun son universales. Pa programes que realicen cálculos numbéricos intensivos, los llinguaxes funcionales tales como OCaml y Clean son daqué más lentos que C. Pa programes que remanen grandes matrices y bases de datos multidimensionales, los vectores de los llinguaxes funcionales, como J y K, fueron diseñaos optimizando la so velocidá.

La inalterabilidad de los datos puede llevar en munchos casos a execuciones eficientes dexando al compilador faer camientos que nun llinguaxe imperativu resultaríen ventureres, aumentando les probabilidaes pa la espansión en llinia, que ye una optimización del compilador que sustitúi nel llugar de la llamada a una función col cuerpu del destinatario de la llamada ameyorando l'usu del tiempu y espaciu en tiempu d'execución.

La evaluación perezosa ye una estratexa d'evaluación que retrasa'l cálculu d'una espresión hasta que'l so valor sía necesariu, tamién puede ameyorar la velocidá del problema, inclusive asintóticamente, ente que puede amenorgar la velocidá por un factor constante, sicasí puede producir perdes de memoria si usar de manera incorreuta. Launchbury 1993 alderica de manera teórica los problemes rellacionaos coles perdes de memoria d'evaluación perezosa, y O’Sullivan et al. 2008 da dellos conseyos práuticos pal analís y la solución d'estos problemes. Sicasí, les implementaciones más xenerales d'evaluación perezosa fai un usu estensivu de códigu ensin referencia y los datos lleven a cabu un funcionamientu probe nos procesadores modernos con un altu grau de paralelismu y caxés multinivel, onde un fallu de caxé puede producir un costu de cientos de ciclos de reló.

Estilos de codificación

Ente que los programes imperativos tienden a apurrir los pasos a dar por un programa, los funcionales tienden a enfatizar la composición y disposición de les funciones, ensin especificar pasos de manera esplícita.