Programació funcional

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, per l'ús industrial i educatiu, entre els quals s'inclouen Common Lisp, Scheme,^[3][4][5][6] Clojure, Wolfram Language,^[7][8] Racket,^[9] Erlang,^[10][11][12]Elixir,^[13] OCaml,^[14][15][16] Haskell,^[16][17] i F Sharp.^[18][19] La programació funcional també és clau per a alguns llenguatges que han tingut èxit en dominis específics com JavaScript al web,^[20] R en estadística,^[21][22][22] J, K i Q en l'anàlisi financer, i XQuery/XSLT per XML.^[23][24][24] Els llenguatges declaratius específics com SQL and Lex/Yacc utiltizen alguns elements de la programació funcional, com ara no permetre valors mutables.^[25][26] A més, molts altres llenguatges de programació admeten la programació en un estil funcional o han implementat característiques de la programació funcional, com ara C++11, C Sharp,^[27] Kotlin,^[28] Perl,^[29] PHP,^[30] Python,^[31] Go,^[32] Rust,^[33] Raku,^[34] Scala,^[35] i Java (des del Java 8).^[36]

Utilitat

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

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.^[37] 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 purs i els híbrids. La diferència entre tots dos estreba que els llenguatges funcionals híbrids són menys dogmàtics que els purs, en admetre conceptes presos dels llenguatges imperatius, com les seqüències d'instruccions o l'assignació de variables. En contrast, els llenguatges funcionals purs 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

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.^[38]

Funcions pures

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 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 dona 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".^[28]

Recursivitat

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.^[39] 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.^[40]

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

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.^[41] 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.^[42] 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

1. Univ. de Girona -- Programació funcional
2. Church, Alonzo «A set of postulates for the foundation of logic». Annals of Mathematics, 33, 2, 1932, pàg. 346–366. DOI: 10.2307/1968337. JSTOR: 1968337.
3. Clinger, Will «MultiTasking and MacScheme». MacTech, 3, 12, 1987 [Consulta: 28 agost 2008].
4. Hartheimer, Anne «Programming a Text Editor in MacScheme+Toolsmith». MacTech, 3, 1, 1987. Arxivat de l'original el 2011-06-29 [Consulta: 28 agost 2008].
5. Kidd, Eric. "Terrorism Response Training in Scheme" a CUFP 2007.   Arxivat 2010-12-21 a Wayback Machine. «Còpia arxivada». Arxivat de l'original el 2010-12-21. [Consulta: 27 octubre 2022].
6. Cleis, Richard. "Scheme in Space" a CUFP 2006.   Arxivat 2010-05-27 a Wayback Machine. «Còpia arxivada». Arxivat de l'original el 2010-05-27. [Consulta: 27 octubre 2022].
7. «Wolfram Language Guide: Functional Programming», 2015. [Consulta: 24 agost 2015].
8. «Functional vs. Procedural Programming Language». University of Colorado. Arxivat de l'original el 2007-11-13.
9. «State-Based Scripting in Uncharted 2». Arxivat de l'original el 2012-12-15. [Consulta: 8 agost 2011].
10. «Who uses Erlang for product development?». Frequently asked questions about Erlang. [Consulta: 27 abril 2018].
11. Armstrong, Joe (juny 2007). "Proceedings of the third ACM SIGPLAN conference on History of programming languages" a Third ACM SIGPLAN Conference on History of Programming Languages. . DOI:10.1145/1238844.1238850 
12. Larson, Jim «Erlang for concurrent programming». Communications of the ACM, 52, 3, 3-2009, pàg. 48. DOI: 10.1145/1467247.1467263.
13. «The Elixir Programming Language». [Consulta: 14 febrer 2021].
14. Minsky, Yaron; Weeks, Stephen «Caml Trading — experiences with functional programming on Wall Street». Journal of Functional Programming, 18, 4, 7-2008, pàg. 553–564. DOI: 10.1017/S095679680800676X [Consulta: 27 agost 2008].
15. Leroy, Xavier. "Some uses of Caml in Industry" a CUFP 2007.   Arxivat 2011-10-08 a Wayback Machine. «Còpia arxivada». Arxivat de l'original el 2011-10-08. [Consulta: 27 octubre 2022].
16. «Haskell in industry». Haskell Wiki. [Consulta: 26 agost 2009]. «Haskell has a diverse range of use commercially, from aerospace and defense, to finance, to web startups, hardware design firms and lawnmower manufacturers.»
17. (juny 2007) "A history of Haskell: being lazy with class" a Third ACM SIGPLAN Conference on History of Programming Languages. . DOI:10.1145/1238844.1238856 
18. Mansell, Howard (2008). "Quantitative Finance in F#" a CUFP 2008.   Arxivat 2015-07-08 a Wayback Machine. «Còpia arxivada». Arxivat de l'original el 2015-07-08. [Consulta: 2 octubre 2022].
19. Peake, Alex (2009). "The First Substantial Line of Business Application in F#" a CUFP 2009.   Arxivat 2009-10-17 a Wayback Machine. «Còpia arxivada». Arxivat de l'original el 2009-10-17. [Consulta: 2 octubre 2022].
20. comments, 27 Jun 2017 Matt Banz Feed 603up 2. «An introduction to functional programming in JavaScript» (en anglès). [Consulta: 9 gener 2021].
21. «The useR! 2006 conference schedule includes papers on the commercial use of R». R-project.org, 08-06-2006. [Consulta: 20 juny 2011].
22. Chambers, John M. Programming with Data: A Guide to the S Language. Springer Verlag, 1998, p. 67–70. ISBN 978-0-387-98503-9. 
23. Novatchev, Dimitre. «The Functional Programming Language XSLT — A proof through examples». [Consulta: 27 maig 2006].
24. Mertz, David. «XML Programming Paradigms (part four): Functional Programming approached to XML processing». IBM developerWorks. [Consulta: 27 maig 2006].
25. Chamberlin, Donald D.; Boyce, Raymond F. «SEQUEL: A structured English query language». Proceedings of the 1974 ACM SIGFIDET, 1974, pàg. 249–264.
26. «Sim-Diasca: a large-scale discrete event concurrent simulation engine in Erlang», 01-11-2011. Arxivat de l'original el 2013-09-17. [Consulta: 27 octubre 2022].
27. «Functional Programming with C# - Simon Painter - NDC Oslo 2020» (en anglès). Arxivat de l'original el 2021-10-30. [Consulta: 23 octubre 2021].
28. «Functional programming - Kotlin Programming Language». [Consulta: 1r maig 2019].
29. Dominus, Mark J. Higher-Order Perl. Morgan Kaufmann, 2005. ISBN 978-1-55860-701-9. 
30. Holywell, Simon. Functional Programming in PHP. php[architect], 2014. ISBN 9781940111056. 
31. The Cain Gang Ltd.. «Python Metaclasses: Who? Why? When?». Arxivat de l'original el 30 maig 2009. [Consulta: 27 juny 2009].
32. «GopherCon 2020: Dylan Meeus - Functional Programming with Go».
33. «Functional Language Features: Iterators and Closures - The Rust Programming Language». [Consulta: 9 gener 2021].
34. Vanderbauwhede, Wim. «Cleaner code with functional programming». Arxivat de l'original el 11 Sep 2020. [Consulta: 6 octubre 2020].
35. «Effective Scala». Scala Wiki. Arxivat de l'original el 2012-06-19. [Consulta: 21 febrer 2012]. «Effective Scala.»
36. «Documentation for package java.util.function since Java 8 (also known as Java 1.8)». [Consulta: 16 juny 2021].
37. 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]. 
38. «Copia archivada». Arxivat de l'original el 14 de març de 2011. [Consulta: 1r maig 2011].
39. Graham, Ronald; Donald Knuth, Oren Patashnik. Concrete Mathematics, 1990, p. Capítulo 1: Recurrent Problems.  Arxivat 2020-11-06 a Wayback Machine.
40. Felleisen, Matthias; Robert Bruce Findler, Matthew Flatt, Shriram Krishnamurthi. How to Design Programs: An Introduction to Computing and Programming. Cambridge, MASS: MIT Press, 2001, p. art V "Generative Recursion". 
41. The Implementation of Functional Programming Languages. Simon Peyton Jones, published by Prentice Hall, 1987
42. Hughes, John. «Why Functional Programming Matters», 1984.

Enllaços externs

• Univ. de Girona - Introducció a la prog. funcional amb explicació del Càlcul lambda

Presentacions en vídeo

• Malcom Wallace - ICFP 2009 i altres vídeos de presentacions recents sobre programació funcional (anglès)