Programació funcional

De Viquipèdia

En informàtica, la programació funcional[1] és un paradigma de programació que tracta les computacions com un procés d'aplicació de funcions, evitant les dades mudables amb els seus canvis d'estat. La programació funcional es fonamenta en el càlcul lambda, un sistema formal desenvolupat a la dècada del 1930.[2] La diferència entre funció matemàtica i el concepte de funció emprat en la programació imperativa és que les funcions imperatives tenen efectes laterals, canviant el valor d'objectes ja calculats, mostrant una manca d'integritat referencial, doncs una mateixa expressió pot tenir diferents valors en moments diferents, depenen de l'estat d'execució del programa.

Els llenguatges de programació funcional, sobretot els funcionalment purs, han estat esperonats en cercles universitaris més que no en el sector comercial. Tanmateix n'hi ha amb un notable ús comercial, entre els quals s'inclouen Scheme, Haskell, Erlang, ML, Scala i llenguatges de domini específic com R (estadística), Mathematica, J i K en anàlisi financera i XSLT en transformació de documents. Llenguatges declaratius com SQL i Lex/Yacc empren aspectes de programació funcional, esquivant les variables mudables. Els fulls de càlcul també poden ser vistos com a llenguatges de programació funcional.

Utilitat[modifica]

La programació funcional es caracteritza per dividir la major quantitat possible de tasques en funcions, d'aquesta forma aquestes tasques poden ser usades per altres funcions amb diferents objectius.

L'objectiu és aconseguir llenguatges expressius i matemàticament elegants, en els quals no sigui necessari baixar al nivell de la màquina per descriure el procés dut a terme pel programa, i evitar el concepte de estat del còmput. La seqüència de computacions dutes a terme pel programa es regeix única i exclusivament per la reescriptura de definicions més àmplies a unes altres cada vegada més concretes i definides.

Aquest paradigma, per no contenir dades mutables, es caracteritza per ser usat per al maneig d'informació i no per a la creació o modificació de la mateixa.

Característiques[modifica]

fold(f, [1,2,3,4,5]) Funció d'ordre superior ¨fold¨ (també anomenada "reduce"). Pren una funció arbitrària f d'aritat 2 (per exemple, la suma) així com una llista d'arguments.[3] Després aplica la funció a una parella de la llista, i el resultat s'usa per aplicar la funció recursivament amb el següent element de la llista. Això pot ser usat, per exemple, per imitar un bucle "for" o "while" amb una variable acumuladora. És a dir, una sumatòria.

Els programes escrits en un llenguatge funcional estan constituïts únicament per definicions de funcions, entenent aquestes no com a subprogrames clàssics d'un llenguatge imperatiu, sinó com a funcions purament matemàtiques, en les quals es verifiquen certes propietats com la transparència referencial (el significat d'una expressió depèn únicament del significat dels seus subexpressions), i per tant, la manca total d’efectes col·laterals.

Altres característiques pròpies d'aquests llenguatges són la no existència d'assignacions de variables i la falta de construccions estructurades com la seqüència o la iteració (el que obliga en la pràctica al fet que totes les repeticions d'instruccions es duguin a terme per mitjà de funcions recursives).

Existeixen dues grans categories de llenguatges funcionals: els funcionals puros i els híbrids. La diferència entre tots dos estreba que els llenguatges funcionals híbrids són menys dogmàtics que els puros, en admetre conceptes presos dels llenguatges imperatius, com les seqüències d'instruccions o l'assignació de variables. En contrast, els llenguatges funcionals puros tenen una major potència expressiva, conservant alhora la seva transparència referencial, alguna cosa que no es compleix sempre amb un llenguatge funcional híbrid.

Funcions de primera classe i d'ordre superior[modifica]

Vegeu també: Funció d'ordre superior

Funcions d'ordre superior són funcions que poden prendre altres funcions com a arguments o retornar-los com a resultats. En càlcul, un exemple d'una funció d'ordre superior és l'operador diferencial d / dx, que retorna la derivada d'una funció f .

Les funcions d'ordre superior estan estretament relacionades amb les funcions de primera classe en les quals les funcions d'ordre superior i les funcions de primera classe poden rebre com a arguments i resultats altres funcions. La distinció entre els dos és subtil: "d'ordre superior", descriu un concepte matemàtic de funcions que operen sobre altres funcions, mentre que la "primera classe" és un terme informàtic que descriu les entitats del llenguatge de programació que no tenen cap restricció de la seva utilització (per tant funcions de primera classe poden aparèixer en qualsevol part del programa que altres entitats de primer nivell com els nombres poden, inclosos com a arguments a altres funcions i com els seus valors de tornada).

Les funcions d'ordre superior permeten l'aplicació parcial, una tècnica en la qual s'aplica una funció als seus arguments un alhora, amb cada aplicació retornar una nova funció que accepta el següent argument. Això li permet a un expressar, per exemple, la funció successor com l'operador de suma aplicada parcialment al nombre natural un.[4]

Funcions pures[modifica]

Transparència referencial. La programació funcional "pura" cerca prohibir la re-definició o re-assignació.

Les funcions purament funcionals (o expressions) no tenen efectes secundaris (memòria o E/S). Això significa que les funcions pures tenen diverses propietats útils, moltes de les quals poden ser utilitzades per optimitzar el codi:

  • Si no s'utilitza el resultat d'una expressió pura, es pot eliminar sense afectar a altres expressions.
  • Si una funció pura es diu amb paràmetres que no causen efectes secundaris, el resultat és constant pel que fa a la llista de paràmetres (de vegades cridada transparència referencial), és a dir, si la funció pura es diu de nou amb els mateixos paràmetres, el mateix resultat serà retornat (això pot habilitar les optimitzacions d'emmagatzematge en elegància).
  • Si no hi ha una dependència de dades entre dues expressions pures, llavors el seu ordre pot ser invertit, o poden dur-se a terme en paral·lel i que no pugui interferir amb els altres.
  • Si el llenguatge no permet efectes secundaris, llavors qualsevol estratègia d'avaluació es pot utilitzar, la qual cosa dóna la llibertat al compilador per reordenar o combinar l'avaluació d'expressions en un programa (per exemple, usant la poda).

La majoria dels compiladors de llenguatges imperatius detecten funcions pures automàticament i realitzen l'eliminació de subexpressions comunes. No obstant això no sempre és possible detectar-ho en biblioteques pre-compilades, perquè per norma general no donen aquesta informació. Això provoca que no es puguin realitzar optimitzacions que podrien aplicar a aquestes funcions externes. Alguns compiladors, com gcc, afegeixen paraules claus addicionals perquè el programador marqui explícitament com a pures aquelles funcions externes que procedeixi, de manera que se li apliquin les optimitzacions pertinents. Fortran 95 també permet declarar funcions "pures".[5]

Recursivitat[modifica]

Article principal: Algorisme recursiu

Iterar en els llenguatges funcionals és normalment dut a terme mitjançant recursivitat. Les funcions recursives s'invoquen a si mateixes, permetent que una operació es realitzi una vegada i una altra fins a aconseguir el cas base.[6] Encara que algunes recursivitats requereixen el manteniment d'una pila, la recursivitat mitjançant una cua pot ser reconeguda i optimitzada mitjançant un compilador dins del mateix codi utilitzat, per implementar les iteracions en un llenguatge imperatiu. L'estàndard de l'esquema del llenguatge requereix implementacions per conèixer i optimitzar la recursivitat mitjançant una cua. L'optimització de la recursivitat mitjançant una cua pot ser implementada transformant el programa a un estil de passada de continuïtat durant la compilació, entre altres enfocaments.[7]

Els patrons comuns de recursivitat poden ser factoritzats usant funcions comunes més grans, amb "catamorfismes" i "anamorfismes" (plecs i desplegaments), sent aquests els exemples més evidents. Tal com les majors funcions més comunes tenen un rol anàleg per construir estructures de control es tenen els iteradors en els llenguatges imperatius.

La majoria dels llenguatges de programació funcional de propòsit general permeten la recursivitat sense restriccions i superen el test de Turing, la qual cosa fa que el programa que s'interromp no pugui prendre una decisió, la qual cosa pot causar una falta de solidesa en el raonament equacional i generalment requereix introduir inconsistència dins de la lògica expressada pels tipus del sistema del llenguatge. Alguns llenguatges de propòsit especial com Coq permeten tan sol recursivitat ben fonamentada i tenen una normalització forta (càlculs no finalitzats poden ser expressats tan sol amb fluxos de valors infinits anomenats codata) En conseqüència, aquests llenguatges fallen el test de Turing i declarar funcions certes en ells és impossible, però poden declarar una àmplia classe de càlculs interessants mentre eviten els problemes produïts per la recursivitat sense restriccions. La programació funcional limitada a la recursivitat ben construïda amb unes quantes restriccions més es diu programació funcional total.

Avaluació estricta davant de la no estricta[modifica]

Els llenguatges funcionals poden ser classificats pel fet d'usar avaluació estricta (eager) o no estricta (lazy), conceptes que fan referència a com els arguments de les funcions són processats quan una expressió està sent avaluada. La diferència tècnica està en la notació semàntica de les expressions que contenen càlculs fallits o divergents. Sota l'avaluació estricta, l'avaluació de qualsevol terme que contingui un sub-terme fallit farà que aquest sigui per si mateix fallit.

Per exemple, l'expressió:

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

fallarà sota avaluació estricta per la divisió per zero en el tercer element de la llista. Utilitzant avaluació no estricta, la grandària de la funció retornarà un valor de 4( per exemple el nombre d'elements de la llista) ja que avaluar això no afectarà en estar avaluant els que componen la llista. En resum, l'avaluació estricta avalua per complet els arguments tret que els seus valors requereixin avaluar la pròpia funció que es diu a si mateixa.

La implementació de l'estratègia comuna per a avaluació no estricta en els llenguatges funcionals és la de reducció mitjançant un graf.[8] L'avaluació no estricta és utilitzada per defecte en multitud de llenguatges funcionals puros, inclosos Miranda, Clean i Haskell.

Hughes (1984) defensava l'avaluació no estricta com un mecanisme per millorar la modularitat dels programes a través de la separació de tasques, a partir de la implementació de productors i consumidors de fluxos de dades de forma fàcil i independent.[9] Launchbury (1993) descriu algunes dificultats que tenia l'avaluació no estricta, particularment en analitzar els requisits d'emmagatzematge dels programes, i proposa una semàntica operacional per ajudar durant l'anàlisi. Harper (2009) proposa incloure ambdues tècniques (avaluació estricta i no estricta) en el mateix llenguatge, utilitzant els tipus del sistema del llenguatge per distingir-les.

Referències[modifica]

  1. Univ. de Girona -- Programació funcional
  2. Church, Alonzo «A set of postulates for the foundation of logic». Annals of Mathematics, vol. 33, 2, 1932, pàg. 346–366. DOI: 10.2307/1968337. JSTOR: 1968337.
  3. Sancho de Sant Romà, Joan. «2. Lògica de Primer Ordre». A: Lògica matemàtica i computabilitat (en espanyol). Edicions Díaz de Santos, 1990, p. 57. ISBN 9788487189531 [Consulta: 21 juny 2010]. 
  4. «Copia archivada». Arxivat de l'original el 14 de març de 2011. [Consulta: 1r maig 2011].
  5. Bruce Eckel. Thinking in Java. Pearson Education, 2006, p. 24. ISBN 978-0-13-187248-6. 
  6. Graham, Ronald; Donald Knuth, Oren Patashnik. Concrete Mathematics, 1990. 
  7. Felleisen, Matthias; Robert Bruce Findler, Matthew Flatt, Shriram Krishnamurthi. How to Design Programs: An Introduction to Computing and Programming. Cambridge, MASS: MIT Press, 2001. 
  8. The Implementation of Functional Programming Languages. Simon Peyton Jones, published by Prentice Hall, 1987
  9. Hughes, John. «Why Functional Programming Matters», 1984.

Enllaços externs[modifica]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Programació funcional
Presentacions en vídeo