Programació funcional

En informàtica, la programació funcional és un paradigma de programació declarativa basat en l'us de verdaderes funcions matemàtiques. En este estil de programació les funcions són ciutadanes de primera classe, perque les seues expressions poden ser assignades a variables com es faria en qualsevol atre valor; ademés de que poden crear-se funcions d'orde superior.

La programació funcional té les seues raïls en el càlcul lambda, un sistema formal desenrollat en els anys 1930 per a investigar la naturalea de les funcions, la naturalea de la computabilidad i la seua relació en la recursión. Els llenguages funcionals priorisen l'us de recursividad i aplicació de funcions d'orde superior per a resoldre problemes que en atres llenguages es resoldrien per mig d'estructures de control (per eixemple, cicles).

Alguns llenguages funcionals també busquen eliminar la mutabilidad o efectes secundaris; en contrast en la programació imperativa, que es basa en els canvis d'estat per mig de la mutació de variables. En programació funcional pura, si dos expressions són sintácticamente iguals llavors sempre tornaran el mateix resultat. És dir, són llenguages en transparència referencial. Lo anterior també pot ser aprofitat per a dissenyar estratègies d'evaluació que eviten repetir el còmput d'expressions abans vistes, o per a evaluar distintes branques d'un programa en paralel sense major preocupació.

Els llenguages de programació funcional, especialment els purament funcionals, han segut emfatisats en l'ambient acadèmic i no tant en el desenroll comercial o industrial. No obstant, llenguages de programació funcional com Lisp (Scheme, Common Lisp, etc.), Erlang, Rust, Objective Caml, Scala, F#, Clojure, Racket, Wolfram Language i Haskell, també han segut utilisats en aplicacions comercials i industrials. També és utilisada en l'indústria a través de llenguages de domini específic com R (estadística), Mathematica (còmput simbòlic), J i K (anàlisis financer). Els llenguages d'us específic usats comunament com SQL i Lex/Yacc, utilisen alguns elements de programació funcional, especialment en processar valors mutables. Les hoja també poden ser considerades llenguages de programació funcional.

Atres llenguages de programació no estan dissenyats específicament per a seguir un estil funcional, no obstant ho oferixen com a alternativa. Per eixemple, Perl, JavaScript i Python varen ser dissenyats en capacitats de programació funcional, ademés d'incorporar atres paradigmes. Versions recents de llenguages originalment sense capacitats funcionals, com C++ i Java, han anat incorporant alguns conceptes de la programació funcional.

Utilitat

La programació funcional es caracterisa per dividir la major cantitat possible de tasques en funcions, d'esta forma estes tasques poden ser usades per atres funcions en diferents objectius.

L'objectiu és conseguir llenguages expressius i matemàticament elegants, en els que no siga necessari baixar al nivell de la màquina per a descriure el procés portat a terme pel programa, i evitar el concepte de estat del còmput. La seqüència de #computació portades a terme pel programa es rig única i exclusivament per la reescritura de definicions més àmplies a unes atres cada volta més concretes i definides.

Este paradigma, per no contindre senyes mutables, es caracterisa per ser usat per al maneig d'informació i no per a la creació o modificació de la mateixa.

Característiques

Els programes escrits en un llenguage funcional estan constituïts únicament per definicions de funcions, entenent estes no com subprogramas clàssics d'un llenguage imperatiu, sino com a funcions purament matemàtiques, en les que es verifiquen certes propietats com la transparència referencial (el significat d'una expressió depén únicament del significat dels seus subexpresiones), i per tant, la carència total de efectes colaterals.

Atres característiques pròpies d'estos llenguages són la no existència de #assignació de variables i la falta de construccions estructurades com la seqüència o la iteración (lo que obliga en la pràctica a que totes les repeticions d'instruccions es porten a terme per mig de funcions recursivas).

Existixen dos grans categories de llenguages funcionals: els funcionals purs i els híbrits. La diferència entre abdós estreba que els llenguages funcionals híbrits són menys dogmàtics que els purs, en admetre conceptes presos dels llenguages imperatius, com les seqüències d'instruccions o l'assignació de variables. En contrast, els llenguages funcionals purs tenen una major potència expressiva, conservant al mateix temps la seua transparència referencial, alguna cosa que no es complix sempre en un llenguage funcional híbrit.

Funcions de primera classe i d'orde superior

Vore també: Funcions de primera classe i Funció d'orde superior

Funcions d'orde superior són funcions que poden prendre atres funcions com a arguments o tornar-los com a resultats. En càlcul , un eixemple d'una funció d'orde superior és l'operador diferencial d / dx , que torna la derivada d'una funció f .

Les funcions d'orde superior estan estretament relacionades en les funcions de primera classe en les quals les funcions d'orde superior i les funcions de primera classe poden rebre com a arguments i resultats atres funcions. La distinció entre els dos és sotil: "d'orde superior", descriu un concepte matemàtic de funcions que operen sobre atres funcions, mentres que la "primera classe" és un terme informàtic que descriu les entitats del llenguage de programació que no tenen cap restricció de la seua utilisació (per lo tant funcions de primera classe poden aparéixer en qualsevol part del programa que atres entitats de primer nivell com els números poden, inclosos com a arguments a atres funcions i com els seus valors de tornada).

Les funcions d'orde superior permeten l'aplicació parcial i la currificación, una tècnica en la que s'aplica una funció als seus arguments un al mateix temps, en cada aplicació tornar una nova funció que accepta el següent argument. Açò li permet a un expressar, per eixemple, la funció successor com l'operador de suma aplicada parcialment al número natural un.

Funcions pures

Les funcions purament funcionals (o expressions) no tenen efectes secundaris (memòria o I/S). Açò significa que les funcions pures tenen vàries propietats útils, moltes de les quals poden ser utilisades per a optimisar el còdic:

• Si no s'utilisa el resultat d'una expressió pura, es pot eliminar sense afectar a atres expressions.

• Si una funció pura es diu en paràmetros que no causen efectes secundaris, el resultat és constant sobre la llista de paràmetros (a voltes cridada transparència referencial), és dir, si la funció pura es diu de nou en els mateixos paràmetros, el mateix resultat serà tornat (açò pot habilitar les optimisacions d'almagasenament en caché).

• Si no hi ha una dependència de senyes entre dos expressions pures, llavors el seu orde pot ser invertit, o poden portar-se a terme en paralel i que no puga interferir en els atres.

• Si el llenguage no permet efectes secundaris, llavors qualsevol estratègia d'evaluació es pot utilisar, lo que dona la llibertat al compilador per a reordenar o combinar l'evaluació d'expressions en un programa (per eixemple, usant la poda).

La majoria dels compiladors de llenguages imperatius detecten funcions pures automàticament i realisen l'eliminació de subexpresiones comunes. No obstant no sempre és possible detectar-ho en biblioteques pre-compiladas, perque per norma general no donen esta informació. Açò provoca que no es puguen realisar optimisacions que podrien aplicar a dites funcions externes. Alguns compiladors, com gcc, afigen paraules claus adicionals per a que el programador marque explícitament com a pures aquelles funcions externes que procedixca, de modo que se li apliquen les optimisacions pertinents. Fortran 95 també permet declarar funcions "pures".

Recursividad

Artícul principal → Recursión (ciències de computació) .

Iterar en els llenguages funcionals és normalment portat a terme per mig de recursividad. Les funcions recursivas s'invoquen a sí mateixes, permetent que una operació es realise una i una atra volta fins a alcançar el cas base. Encara que algunes recursividades requerixen el manteniment d'una pila, la recursividad per mig d'una coa pot ser reconeguda i optimisada per mig d'un compilador dins del mateix còdic utilisat, per a implementar les iteraciones en un llenguage imperatiu. L'estàndart de l'esquema del llenguage requerix implementacions per a conéixer i optimisar la recursividad per mig d'una coa. L'optimisació de la recursividad per mig d'una coa pot ser implementada transformant el programa a un estil de passe de continuïtat durant la compilació, entre atres enfocaments.

Els patrons comuns de recursividad poden ser factorizados usant funcions comunes més grans, en “catamorfismos” i “anamorfismos” (plecs i desplegaments), sent estos els eixemples més evidents. Tal i com les majors funcions més comunes tenen un rol anàlec per a construir estructures de control es tenen els iteradores en els llenguages imperatius.

La majoria dels llenguages de programació funcional de propòsit general permeten la recursividad sense restriccions i superen el test de Turing, lo que fa que el programa que s'interromp no puga prendre una decisió, lo que pot causar una falta de solidea en el raonament ecuacional i generalment requerix introduir inconsistencia dins de la llògica expressada pels tipos del sistema del llenguage. Alguns llenguages de propòsit especial com Coq permeten tan sol recursividad ben fonamentada i tenen una normalisació forta(càlculs no finalisats poden ser expressats tan sol en #fluix de valors infinits cridats codata) En conseqüència, estos llenguages fallen el test de Turing i declarar funcions certes en ells és impossible, pero poden declarar una àmplia classe de càlculs interessants mentres eviten els problemes produïts per la recursividad sense restriccions. La programació funcional llimitada a la recursividad ben construïda en unes quantes restriccions més es diu programació funcional total.

Evaluació estricta front a la no estricta

Els llenguages funcionals poden ser classificats pel fet d'usar evaluació estricta(eager) o no estricta(lazy), conceptes que fan referència a cóm els arguments de les funcions són processats quan una expressió està sent evaluada. La diferència tècnica està en la notació semàntica de les expressions que contenen càlculs fallancs o divergents. Baixe l'evaluació estricta, l'evaluació de qualsevol terme que continga un sub-terme fallanc farà que este siga de per sí fallanc.

Per eixemple, l'expressió:

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

fallarà baix evaluació estricta per la divisió per zero en el tercer element de la llista. Utilisant evaluació no estricta, el tamany de la funció tornarà un valor de 4( per eixemple el número d'elements de la llista) ya que evaluar açò no afectarà en estar evaluant els que componen la llista. En resum, l'evaluació estricta evalua per complet els arguments a menos que els seus valors requerixquen evaluar la pròpia funció que es diu a sí mateixa.

L'implementació de l'estratègia comuna per a evaluació no estricta en els llenguages funcionals és la de reducció per mig d'un grafo. L'evaluació no estricta és utilisada per defecte en multitut de llenguages funcionals purs, inclosos Miranda, Clean i Haskell.

Hughes (1984) defenia l'evaluació no estricta com un mecanisme per a millorar la modularidad dels programes a través de la separació de tasques, a partir de l'implementació de productors i consumidors de #fluix de senyes de forma fàcil i independent. Launchbury (1993) descriu algunes dificultats que tenia l'evaluació no estricta, particularment en analisar els requisits d'almagasenament dels programes, i propon una semàntica operacional per a ajudar durant l'anàlisis. Harper (2009) propon incloure abdós tècniques (evaluació estricta i no estricta) en el mateix llenguage, utilisant els tipos del sistema del llenguage per a distinguir-les.

Sistemes de tipos

Especialment des del desenroll d'inferència de tipos Hindley - Milner en la década de 1970, els llenguages de programació funcionals han tendit a utilisar el càlcul lambda en tipos, en comparació al càlcul lambda sense tipos utilisat en Lisp i les seues variants (tals com el llenguage scheme).

L'us de tipos de senyes algebraiques i la coincidència de patrons fa que la manipulació d'estructures de senyes complexes convenients i expressius, la presència de comprovacions estrictes de tipos en temps de compilació fa que els programes siguen més fiables, mentres que l'inferència de tipos llibera al programador de la necessitat de declarar manualment els tipos per al compilador.

Alguns llenguages funcionals orientats a l'investigació, tals com Coq, Agda, Cayenne i Epigram es basen en la teoria de tipos intuicionista, que permet als tipos a dependre dels térmens. Estos tipos es denominen tipos depenents. S'ha demostrat que estos sistemes de tipos sofisticats són tan expressius que els seus respectius problemes d'inferència de tipos deixen de ser decidibles. Els tipos depenents poden expressar proposicions arbitràries en la llògica de predicats intuicionista. Este resultat es coneix com a isomorfisme de Curry-Howard, i convertix a la programació funcional en una teoria de tipos intuicionista o equivalent en una forma d'escriure proves matemàtiques formals, de les que un compilador pot generar còdic certificat. Si ben estos llenguages són principalment d'interés en l'investigació acadèmica (incloent les matemàtiques formalisades), han començat a ser utilisats en l'ingenieria també. Compcert és un compilador per a un subconjunt del llenguage de programació C que està escrit en Coq i el qual es va verificar formalment.

Una forma llimitada de tipos depenents cridats tipos de senyes algebraiques generalisades (GADTs) pot ser implementat d'una manera que oferix alguns dels beneficis de la programació depenent, evitant la major part de la seua inconveniencia. GADTs estan disponibles en el Glasgow Haskell Compiler, en OCaml (des de la versió 4.00) i en Scala i s'han propost com a #adició a atres llenguages, incloent Java i C#.

La programació funcional en llenguages no funcionals

És possible utilisar un estil de programació funcional en llenguages que tradicionalment no es consideren llenguages funcionals. Per eixemple, tant D i Fortran95 es recolzen explícitament en funcions pures. Funcions de primera classe, s'han afegit llentament als llenguages principals. Per eixemple, a principis de 1994, el respal a lambda, filtre, mapa, i reduir està en Python. Després, durant el desenroll de Python 3000, Guido van Rossum va demanar l'eliminació d'estes característiques. No obstant, més tart va canviar d'opinió, i solament la reducció va ser eliminat, a pesar de que seguix sent accessible a través dels mòduls de biblioteca functools estàndar. Funcions de primera classe també varen ser introduïdes en PHP 5.3, Visual Basic9, C#3.0 i C++11.

En Java, les classes anònimes a voltes poden ser utilisats per a simular #clausura. No obstant, les classes anònimes no són sempre les tongades completes de les #clausura, ya que tenen capacitats més llimitades. Per eixemple, Java 8, inclou expressions lambda per a reemplaçar determinades classes anònimes. No obstant, la presència d'excepcions en comprovacions en este llenguage pot desaconsellar l'us de programació funcional, ya que pot ser necessari per a capturar les excepcions que es deuen controlar per a despuix tornar-les a llançar ells (problema este que no obstant no es produïx en atres llenguages sobre JVM que no tenen excepcions comprovades, com és Scala).

Molts patrons de disseny orientat a objectes es poden expressar en térmens de programació funcional per eixemple : el patró d'estratègia simplement dicta l'us d'una funció d'orde superior, i el patró de visitants correspon aproximadament a un catamorfismo, o doble també conegut com reduir, comprimir, o injectar, es referix a una família de funcions d'orde superior que analisa una estructura de senyes recursiva i es recombinan en l'us d'una operació de combinació.

De la mateixa manera, l'idea de les senyes immutables de la programació funcional s'inclou a sovint en llenguages de programació imperativa, per eixemple, la tupla de Python, que és una matriu immutable.

Ventages d'usar un paradigma funcional

Entre les ventages que solen citar-se d'usar un paradigma funcional en la programació de computadores, estan les següents:

• Absència d'efectes colaterals.
• Procés de depuració menys problemàtic.
• Proves d'unitats més confiables.
• Major facilitat per a l'eixecució concurrent.

Simulació d'estats

Hi ha tasques (com per eixemple, el manteniment del saldo d'un conte bancari) que a sovint semblen implementades en estats. La programació funcional pura actua sobre eixes tasques, tasques d'entrada/eixida de senyes tals com a entrada de senyes per part de l'usuari i mostrar resultats per pantalla, d'una forma diferent.

El llenguage de programació funcional Haskell ho implementa usant mónadas, estructura que representa càlculs que es descriuen com una seqüència de passos, derivada de la teoria de categories.

Les mónadas oferixen una forma d'abstraure certs tipos de patrons computacionals, incloent (pero no llimitat a) el disseny d'operacions en estats canviants (i atres accions secundàries tals com a entrada/eixida de senyes) d'una manera imperativa sense perdre la purea. Mentres les mónadas existents poden ser fàcils d'aplicar en un programa usant les plantilles i eixemples adequats, molts estudiants tenen problemes per a entendre-ho conceptualment, per eixemple quan se'ls demana definir noves mónadas. (lo que a voltes resulta necessari per a certs tipos de llibreries).

Una atra forma en la que els llenguages funcionals poden simular estats és rodejant una estructura de senyes que representa l'estat actual com un paràmetro per a cridades a funcions. En cada cridada a funció, es crea una còpia d'esta estructura de senyes que es diferencia en el resultat de la funció. Açò es coneix com a “estil de pas d'estat”.

Els llenguages funcionals no purs normalment inclouen métodos per a gestionar el canvi d'estat més directament. Clojure per eixemple, usa una gestió de referències que poden ser actualisades aplicant funcions pures a l'estat actual. Este tipo d'enfocament permet el canvi d'estat, promovent l'us de funcions pures com la millor forma de realisar càlculs.

Métodos alternatius com llògica de Hoare, el qual és un sistema formal en un conjunt de regles llògiques que servixen per a raonar en rigor sobre la correcció de programes, i la singularitat han segut desenrollats per a realisar un seguiment dels efectes secundaris en els programes. Alguns llenguages d'investigació moderns usen sistemes d'efectes per a fer explícita la presència d'efectes colaterals.

Qüestions d'eficiència

Els llenguages de programació en este paradigma són típicament menys eficients en l'us de CPU i memòria que els llenguages imperatius com poden ser C i Pascal. Açò està relacionat en el fet de que algunes estructures de senyes de tamany indefinit com els vectores tenen una programació molt senzilla usant l'hardware existent, el qual és una màquina de Turing prou evolucionada. Es pot accedir molt eficientemente a les posicions del array en CPUs en un alt grau de perfeccionament, fent pre busques eficientemente a través de les memòries caché o manejat en instruccions SIMD. I no és fàcil crear components homòlecs immutables de propòsit general en la mateixa eficiència. Per a llenguages purament funcionals, el pijor cas descendent és el logarítmic en el número de celes de memòria usades, perque les estructures de memòria que canvien de tamany poden ser representades per estructures de senyes purament funcionals en temps d'accés logarítmic, com per eixemple un arbre equilibrat. No obstant, tals retarts no són universals. Per a programes que realisen càlculs numèrics intensius, els llenguages funcionals tals com OCaml i Clean són alguna cosa més llents que C. Per a programes que manegen grans matrius i bases de senyes multidimensionales, els vectores dels llenguages funcionals, com J i K, varen ser dissenyats optimisant la seua velocitat.

La inalterabilidad de les senyes pot dur en molts casos a eixecucions eficients permetent al compilador fer suposicions que en un llenguage imperatiu resultarien arriscades, aumentant les provabilitats per a l'expansió en llínea, que és una optimisació del compilador que substituïx en el lloc de la cridada a una funció en el cos del destinatari de la cridada millorant l'us del temps i espai en temps d'eixecució.

l'evaluació pereosa és una estratègia d'evaluació que retarda el càlcul d'una expressió fins que el seu valor siga necessari, també pot millorar la velocitat del problema, inclús asintóticament, mentres que pot reduir la velocitat per un factor constant, no obstant pot produir pèrdues de memòria si s'usa de manera incorrecta. Launchbury 1993 discutix de manera teòrica els problemes relacionats en les pèrdues de memòria d'evaluació pereosa, i O’Sullivan et al. 2008 dona alguns consells pràctics per a l'anàlisis i la solució d'estos problemes. No obstant, les implementacions més generals d'evaluació pereosa fa un us extensiu de còdic sense referència i les senyes porten a terme un funcionament pobre en els processadors moderns en un alt grau de paralelisme i cachés multinivel, a on un fallo de caché pot produir un cost de centenars de cicles de rellonge.

Llenguages funcionals

Entre els llenguages funcionals purs, cal destacar a Haskell i Miranda. Els llenguages funcionals híbrits més coneguts són Scala, Lisp, Clojure, Scheme, OCaml, SAP i Standard ML (estos dos últims, descendents del llenguage ML). Erlang és un atre llenguage funcional de programació concurrent. Mathematica permet la programació en múltiples estils, pero promou la programació funcional. R també és un llenguage funcional dedicat a l'estadística. Recentment Microsoft Research està treballant en el llenguage F# (Functional#).

Entre atres llenguages que es podrien utilisar per a programació funcional es podrien incloure a Perl, puix, encara que és un llenguage de propòsit molt general, es poden realisar programes usant exclusivament funcions definides per l'usuari; aixina com Python, com a llenguage que incorpora el paradigma funcional; o Ruby.

Estils de codificació

Mentres que els programes imperatius tendixen a proporcionar els passos a donar per un programa, els funcionals tendixen a emfatisar la composició i disposició de les funcions, sense especificar passos de manera explícita.

Us en l'indústria

La programació funcional és més popular en l'àmbit acadèmic que en àmbits industrials. No obstant s'han escomençat a usar importants llenguages de programació funcionals en sistemes comercials o industrials. Un eixemple de llenguage de programació funcional usat en l'àmbit industrial és Erlang, el qual va ser desenrollat per a posar en pràctica sistemes de tolerància a fallos en les telecomunicacions. Importants empreses com WhatsApp, Facebook, o T-Mobile varen optar per Erlang com a llenguage en algun dels seus desenrolls. Un atre eixemple d'us dels llenguages de programació funcionals en l'indústria és el cas de l'us del Scheme de Lisp, que va ser usat com a base en el desenroll d'aplicacions per als primers ordenadors de la firma Apple Macintosh. De fet, hui en dia, està sent usat per a desenroll de sistemes de simulació i de control de telescopi. Haskell, és un eixemple de llenguage que es va crear en propòsit de llenguage d'investigació pero que s'ha usat per al desenroll de sistemes aeroespacials, programació web i disseny d'hardware. Atres llenguages de programació funcionals han segut usats en àmbits comercials i financers.

Vore també

• Llenguage de programació
• Programació per procediments
• Càlcul Lambda
• Teoria de categories