Programare functionala

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 2 februarie 2022; verificările necesită 2 modificări .

Programarea funcțională  este o paradigmă de programare în care procesul de calcul este interpretat ca calculul valorilor funcțiilor în înțelegerea matematică a acestora din urmă (spre deosebire de funcțiile ca subrutine în programarea procedurală ).

În contrast cu paradigma programării imperative , care descrie procesul de calcul ca o schimbare succesivă a stărilor (într-un sens similar cu cel al teoriei automatelor ). Dacă este necesar, în programarea funcțională, întregul set de stări secvențiale ale procesului de calcul este reprezentat explicit, de exemplu, ca o listă .

Programarea funcțională se referă la calcularea rezultatelor funcțiilor din datele de intrare și a rezultatelor altor funcții și nu implică stocarea explicită a stării programului. În consecință, nici nu implică mutabilitatea acestei stări (spre deosebire de imperativ , unde unul dintre conceptele de bază este o variabilă care stochează valoarea acesteia și vă permite să o schimbați pe măsură ce algoritmul este executat ).

În practică, diferența dintre o funcție matematică și conceptul de „funcție” în programarea imperativă este că funcțiile imperative se pot baza nu numai pe argumente, ci și pe starea variabilelor externe funcției, precum și să aibă efecte secundare și să se modifice. starea variabilelor externe. Astfel, în programarea imperativă, la apelarea aceleiași funcție cu aceiași parametri, dar în etape diferite ale execuției algoritmului, puteți obține date de ieșire diferite datorită influenței stării variabilei asupra funcției. Și într-un limbaj funcțional, atunci când apelăm o funcție cu aceleași argumente, obținem întotdeauna același rezultat: ieșirea depinde doar de intrare. Acest lucru permite runtimelor funcționale ale limbajului să memoreze în cache rezultatele funcțiilor și să le apeleze într-o ordine nedefinită de algoritm și să le paralelizeze fără nicio muncă suplimentară din partea programatorului (care oferă funcții fără efecte secundare - funcții pure ) .

Calculul lambda este baza pentru programarea funcțională, multe limbaje funcționale pot fi considerate ca un „supliment” peste acesta [1] .

Limbaje de programare funcționale

Cele mai cunoscute limbaje de programare funcționale sunt :

Versiunile inițiale care nu sunt încă complet funcționale atât ale Lisp , cât și ale APL au avut o contribuție specială la crearea și dezvoltarea programării funcționale. Versiunile ulterioare ale Lisp, cum ar fi Scheme , precum și diverse variante de APL, au suportat toate caracteristicile și conceptele unui limbaj funcțional [3] .

De regulă, interesul pentru limbajele de programare funcționale, în special pentru cele pur funcționale, a fost mai mult științific decât comercial. Cu toate acestea, limbi notabile, cum ar fi Erlang , OCaml , Haskell , Scheme (după 1986), precum și specificul R (statistică), Wolfram (matematică simbolică), J și K (analiza financiară) și XSLT ( XML ) și-au găsit drum în industria programării comerciale... Limbajele declarative răspândite, cum ar fi SQL și Lex / Yacc , conțin unele elemente de programare funcțională, de exemplu, nu folosesc variabile. Limbile pentru foile de calcul pot fi, de asemenea, considerate funcționale, deoarece celulele foilor de calcul conțin o serie de funcții care depind de obicei doar de alte celule, iar dacă doriți să modelați variabile, trebuie să recurgeți la capacitățile unui limbaj macro imperativ.

Istorie

Calculul lambda a devenit baza teoretică pentru descrierea și calcularea funcțiilor. Fiind o abstractizare matematică , nu un limbaj de programare , acesta a stat la baza aproape tuturor limbajelor de programare funcționale de astăzi. Un concept teoretic similar, logica combinatorie , este mai abstract decât λ-calcul și a fost creat mai devreme. Această logică este folosită în unele limbi ezoterice, cum ar fi Unlambda . Atât λ-calcul, cât și logica combinatorie au fost dezvoltate pentru a descrie mai clar și mai precis principiile și fundamentele matematicii [4] .

Primul limbaj funcțional a fost Lisp , creat de John McCarthy în timp ce era la MIT la sfârșitul anilor cincizeci și implementat inițial pentru IBM 700/7000 [5] . Lisp a fost primul care a introdus multe concepte de limbaj funcțional, deși limbajul folosește mai mult decât paradigma de programare funcțională [6] . Lisp a fost dezvoltat în continuare de limbaje precum Scheme și Dylan .

Limbajul de procesare a informațiilor , IPL este uneori definit ca primul limbaj funcțional al mașinii [7] . Este un limbaj de asamblare pentru lucrul cu o listă de simboluri. Avea conceptul de „generator” care folosea o funcție ca argument și, de asemenea, deoarece este un limbaj la nivel de asamblare, poate fi poziționat ca un limbaj care are funcții de ordin superior. Cu toate acestea, în general, IPL subliniază utilizarea conceptelor imperative [8] .

Kenneth Iverson a dezvoltat limbajul APL la începutul anilor șaizeci, documentându-l în cartea sa A Programming Language ( ISBN 978-0-471-43014-8 ) [9] . APL a avut o influență semnificativă asupra limbajului FP creat de John Backus . La începutul anilor 1990, Iverson și Roger Hui au creat succesorul APL, limbajul de programare La mijlocul anilor 90 , Arthur Whitney , care lucrase anterior cu Iverson, a creat limbajul K , care a fost ulterior folosit comercial în industria financiară.

Robin Milner a creat limbajul ML la Universitatea din Edinburgh în anii 1970 , iar David Turner a început SASL la Universitatea din St. Andrews și mai târziu Miranda la Universitatea din Kent. În cele din urmă, au fost create mai multe limbi bazate pe ML, dintre care cele mai cunoscute sunt Objective Caml și Standard ML . Tot în anii șaptezeci, a fost dezvoltat un limbaj de programare bazat pe principiul Scheme (implementarea nu numai a unei paradigme funcționale), care a fost descris în celebra lucrare „Lambda Papers”, precum și în cartea anului optzeci și cinci. „ Structura și interpretarea programelor de calculator ”.

În 1972, Per Martin-Löf a creat teoria tipurilor intuiționistă (numită și constructivă). În această teorie, programarea funcțională a primit o dovadă constructivă a ceea ce era cunoscut anterior ca tip dependent. Acest lucru a dat un impuls puternic dezvoltării demonstrării teoremelor interactive și creării ulterioare a multor limbaje funcționale.

Haskell a fost creat la sfârșitul anilor 1980 într-o încercare de a combina multe dintre ideile din cercetarea de programare funcțională [3] .

Concepte

Unele concepte și paradigme sunt specifice programării funcționale și în mare parte străine de programare imperativă (inclusiv programarea orientată pe obiecte ). Cu toate acestea, limbajele de programare sunt de obicei un hibrid al mai multor paradigme de programare, astfel încât limbajele de programare „în mare parte imperative” pot folosi oricare dintre aceste concepte [10] .

Funcții de ordin superior

Funcțiile de ordin superior sunt funcții care pot lua drept argumente și pot returna alte funcții. [11] . Matematicienii numesc adesea o astfel de funcție un operator , de exemplu, operatorul derivat sau operatorul de integrare.

Funcțiile de ordin superior permit utilizarea currying  - transformarea unei funcții dintr-o pereche de argumente într-o funcție care își ia argumentele pe rând. Această transformare poartă numele lui Haskell Curry .

Funcții pure

Funcțiile pure sunt cele care nu au efecte secundare I/O și memorie (depind doar de parametrii lor și returnează doar rezultatul). Funcțiile pure au câteva proprietăți utile, dintre care multe pot fi folosite pentru a optimiza codul:

Datorită memorizării, dacă funcția este apelată ulterior cu aceleași argumente, rezultatul acesteia poate fi preluat direct din tabelul de valori fără a fi calculat (numit uneori principiul transparenței de referință). Memorizarea, cu prețul unui consum mic de memorie, poate crește semnificativ performanța și poate reduce ordinea de creștere a unor algoritmi recursivi.

În timp ce majoritatea compilatorilor limbajelor de programare imperative recunosc funcțiile pure și elimină subexpresiile comune pentru apelurile de funcții pure, nu pot face întotdeauna acest lucru pentru bibliotecile precompilate, care în general nu oferă aceste informații. Unele compilatoare, cum ar fi gcc , furnizează programatorului cuvinte cheie pentru funcții pure în scopuri de optimizare [12] . Fortran 95 vă permite să desemnați funcții ca „pure” (pure) [13] .

Recursiune

În limbajele funcționale, o buclă este de obicei implementată ca recursivitate. Strict vorbind, nu există o buclă în paradigma de programare funcțională. Funcțiile recursive se numesc singure, permițând efectuarea operației din nou și din nou. Poate fi necesară o stivă mare pentru a utiliza recursiunea , dar aceasta poate fi evitată cu recursiunea coadă . Recursiunea cozii poate fi recunoscută și optimizată de către compilator în cod rezultat din compilarea unei iterații similare într-un limbaj de programare imperativ. [14] Standardele de limbaj Scheme necesită recunoașterea și optimizarea recursiunii cozii. Recursiunea cozii poate fi optimizată prin conversia programului la stilul de utilizare a continuărilor la compilare, ca una dintre modalități. [cincisprezece]

Funcțiile recursive pot fi generalizate la funcții de ordin superior, folosind, de exemplu, catamorfismul și anamorfismul (sau „convoluția” și „expansiunea”) [16] . Funcțiile de acest fel joacă rolul unui astfel de concept ca ciclu în limbaje de programare imperative [17] .

Abordarea evaluării argumentelor

Limbile funcționale pot fi clasificate în funcție de modul în care sunt gestionate argumentele funcției în timpul evaluării. Din punct de vedere tehnic, diferența constă în semantica denotațională a expresiei. De exemplu, cu o abordare strictă a evaluării unei expresii:

imprimare ( len ([ 2 + 1 , 3 * 2 , 1 / 0 , 5 - 4 ]))

rezultatul va fi o eroare, deoarece al treilea element al listei conține împărțirea la zero. Cu o abordare nestrictă, valoarea expresiei va fi 4, deoarece, strict vorbind, valorile elementelor sale nu sunt importante pentru calcularea lungimii listei și este posibil să nu fie calculate deloc. Cu ordine strictă (aplicativă) de evaluare, valorile tuturor argumentelor sunt precalculate înainte ca funcția în sine să fie evaluată. Cu o abordare nestrictă (ordine normală de evaluare), valorile argumentelor nu sunt evaluate până când valoarea lor este necesară atunci când funcția este evaluată [18] .

De regulă, o abordare non-strictă este implementată sub forma reducerii grafice. Evaluarea nestrictă este implicită în mai multe limbaje pur funcționale, inclusiv Miranda și Haskell [19] .

În limbi nefuncționale

În principiu, nu există bariere în scrierea de programe în stil funcțional în limbi care nu sunt considerate în mod tradițional funcționale, la fel cum programele de stil orientate pe obiecte pot fi scrise în limbaje structurale. Unele limbaje imperative suportă constructe tipice limbajelor funcționale, cum ar fi funcțiile de ordin superior și listele de înțelegere, care facilitează utilizarea stilului funcțional în aceste limbi, în special, această abordare este utilizată pe scară largă în practica limbajului Python. . Un alt exemplu este limbajul Ruby , care are capacitatea de a crea atât funcții anonime folosind variabile legate (λ-obiecte), cât și capacitatea de a organiza funcții anonime de ordin superior printr-un bloc folosind yield. În C , indicatorii de funcție ca tipuri de argumente pot fi utilizați pentru a crea funcții de ordin superior. Funcțiile de ordin superior și structura de listă amânată sunt implementate în bibliotecile C++ . În Java 8 și versiunile ulterioare și C# 3.0 și versiunile ulterioare, puteți utiliza funcțiile λ pentru a scrie un program într-un stil funcțional.

Stiluri de programare

Programele imperative tind să sublinieze secvențele de pași pentru a efectua o anumită acțiune, în timp ce programele funcționale tind să sublinieze aranjarea și compoziția funcțiilor, deseori nedesemnând succesiunea exactă a pașilor. Un exemplu simplu de două soluții la aceeași problemă (folosind același limbaj Python ) ilustrează acest lucru.

# țintă de stil imperativ = [] # creați o listă goală pentru elementul din lista_sursă : # pentru fiecare element din lista sursă trans1 = G ( articol ) # aplică funcția G() trans2 = F ( trans1 ) # aplică funcția țintă F() . append ( trans2 ) # adaugă elementul convertit la listă

Versiunea funcțională arată diferit:

# stil funcțional # Limbile FP au adesea încorporat compose() în compose2 = lambda A , B : lambda x : A ( B ( x )) target = map ( compose2 ( F , G ), listă_sursă )

Spre deosebire de stilul imperativ, care descrie pașii care duc la atingerea unui scop, stilul funcțional descrie relația matematică dintre date și scop.

Mai exact, există patru etape în dezvoltarea stilului funcțional, în ordinea descrescătoare a rolului datelor în programe:

În primul caz, întreaga structură a programului este determinată de structura datelor, în ultimul caz, datele ca atare nu se află deloc în codul sursă, ele sunt doar implicite la intrare. Unele limbi acceptă o serie de stiluri: de exemplu, Haskell vă permite să scrieți atât în ​​stiluri aplicative, combinatorii, cât și fără puncte.

Caracteristici

Principala caracteristică a programării funcționale, care determină atât avantajele, cât și dezavantajele acestei paradigme, este că implementează un model de calcul fără stat. Dacă un program imperativ în orice stadiu de execuție are o stare, adică un set de valori ale tuturor variabilelor și produce efecte secundare, atunci un program pur funcțional nu are stare nici în întregime, nici în părți și nu produce secundare. efecte. Ceea ce se face în limbaje imperative prin atribuirea de valori variabilelor se realizează în limbaje funcționale prin trecerea expresiilor la parametrii funcției. Consecința imediată este că un program pur funcțional nu poate modifica datele pe care le are deja, ci poate genera doar altele noi prin copierea sau extinderea celor vechi. Consecința aceleiași este respingerea ciclurilor în favoarea recursiei.

Puncte forte

Îmbunătățirea fiabilității codului

Partea atractivă a calculului fără stat este fiabilitatea crescută a codului datorită structurii clare și absenței necesității de a urmări efectele secundare. Orice funcție funcționează numai cu date locale și funcționează întotdeauna cu ele în același mod, indiferent de unde, cum și în ce circumstanțe este numită. Imposibilitatea mutației datelor atunci când le folosiți în diferite locuri ale programului elimină apariția erorilor greu de detectat (cum ar fi, de exemplu, atribuirea accidentală a unei valori incorecte unei variabile globale într-un program imperativ).

Ușurința organizării testării unitare

Deoarece o funcție din programarea funcțională nu poate produce efecte secundare, obiectele nu pot fi modificate atât în ​​interiorul domeniului, cât și în exterior (spre deosebire de programele imperative, unde o funcție poate seta o variabilă externă citită de a doua funcție). Singurul efect al evaluării unei funcții este rezultatul pe care îl returnează, iar singurul factor care afectează rezultatul este valoarea argumentelor.

Astfel, este posibil să testați fiecare funcție dintr-un program prin simpla evaluare a acesteia din diferite seturi de valori ale argumentelor. În acest caz, nu trebuie să vă faceți griji despre apelarea funcțiilor în ordinea corectă sau despre formarea corectă a stării externe. Dacă vreo funcție din program trece testele unitare, atunci puteți fi sigur de calitatea întregului program. În programele imperative, verificarea valorii returnate a unei funcții nu este suficientă: funcția poate modifica starea externă, care trebuie și verificată, ceea ce nu este necesar în programele funcționale [20] .

Opțiuni de optimizare a compilatorului

Caracteristica pozitivă menționată în mod tradițional a programării funcționale este aceea că vă permite să descrieți programul în așa-numita formă „declarativă”, atunci când o succesiune rigidă de efectuare a multor operații necesare calculării rezultatului nu este specificată în mod explicit, ci se formează automat în procesul de calcul al funcțiilor. Această circumstanță, precum și absența stărilor, face posibilă aplicarea unor metode destul de complexe de optimizare automată la programele funcționale.

Capacități de concurență

Un alt avantaj al programelor funcționale este că oferă cele mai largi posibilități de paralelizare automată a calculelor. Deoarece absența efectelor secundare este garantată, în orice apel de funcție este întotdeauna permisă evaluarea a doi parametri diferiți în paralel - ordinea în care sunt evaluați nu poate afecta rezultatul apelului.

Lizibilitatea codului local

Când se analizează codul unui program imperativ, este important să știm „unde ne aflăm acum”. Fără o înțelegere a mediului, este dificil să faci modificări la cod, așa că înainte de a face modificări, trebuie mai întâi să înțelegi contextul general al execuției, sau cel puțin în cadrul modulului editat. În programarea funcțională, pe de altă parte, codul poate fi citit și editat local, fără teama că acest lucru va duce la vreo consecință neașteptată. Acest lucru permite participanților cu diferite niveluri de acces să lucreze împreună la program fără costuri suplimentare pentru asigurarea modularității codului.

Dezavantaje

Dezavantajele programării funcționale provin din aceleași caracteristici. Absența sarcinilor și înlocuirea lor cu generarea de date noi duc la necesitatea alocării constante și eliberării automate a memoriei, prin urmare, în sistemul de execuție al unui program funcțional, este obligatoriucolector de gunoi foarte eficient devine o componentă . Modelul de calcul non-strict duce la o ordine imprevizibilă a apelurilor de funcții, ceea ce creează probleme în I/O, unde ordinea operațiilor este importantă. De asemenea, evident, funcțiile de intrare în forma lor naturală (de exemplu, din getchar()biblioteca standard C ) nu sunt pure, deoarece sunt capabile să returneze valori diferite pentru aceleași argumente și sunt necesare anumite trucuri pentru a elimina acest lucru.

Pentru a depăși deficiențele programelor funcționale, chiar și primele limbaje de programare funcționale au inclus nu numai instrumente pur funcționale, ci și mecanisme de programare imperativă (atribuirea, bucla, „PROGN implicit” erau deja în Lisp). Folosirea unor astfel de instrumente rezolvă unele probleme practice, dar înseamnă îndepărtarea de ideile (și avantajele) de programare funcțională și scrierea de programe imperative în limbaje funcționale. În limbajele pur funcționale, aceste probleme sunt rezolvate prin alte mijloace, de exemplu, în Haskell , I/O este implementat folosind monade  , un concept împrumutat din teoria categoriilor.

Note

  1. ↑ A. Field, P. Harrison Programare funcțională: Per. din engleza. - M .: Mir, 1993. - 637 p., ill. ISBN 5-03-001870-0 . Pagină 120 [Capitolul 6: Fundamente matematice: λ-calcul].
  2. ↑ 1 2 Paul Hudak Conceperea, evoluția și aplicarea limbajelor de programare funcționale  (engleză)  // Association for Computing Machinery Computing Surveys : jurnal. - 1989. - Septembrie ( vol. 21 , nr. 3 ). - P. 359-411 . - doi : 10.1145/72551.72554 . Arhivat din original pe 5 iunie 2013.
  3. ↑ Roger Penrose . Capitolul 2: Calculul Lambda al Bisericii // Noua minte a regelui. Despre computere, gândire și legile fizicii = The Emperors New Mind: Concerning Computers, Minds and The Laws of Physics. - Editorial URSS, 2003. - ISBN 5-354-00005-X . + reeditare ISBN 978-5-382-01266-7 ; 2011
  4. ↑ McCarthy, John Istoria Lisp  // În Asociația pentru Mașini de Calcul SIGPLAN Conferința Istoria limbajelor de programare. - 1978. - Iunie. - S. 217-223 . - doi : 10.1145/800025.808387 . Arhivat din original pe 7 iunie 2008.
  5. ↑ J. Harrison, 1997 , cap. 3. λ-calcul ca limbaj de programare.
  6. ↑ În memoriile sale Herbert Simon (1991), Models of My Life pp.189-190 ISBN 0-465-04640-1 afirmă că al său, Al. Newell și Cliff Shaw, care sunt „deseori denumiți ca părinții inteligenței artificiale” pentru că au scris programul Logic Theorist care demonstrează automat teoremele din Principia Mathematica . Pentru a realiza acest lucru, ei au trebuit să vină cu un limbaj și o paradigmă care, retrospectiv, poate fi văzută ca programare funcțională.
  7. ↑ Istoria limbajelor de programare: IPL (downlink) . Consultat la 15 aprilie 2012. Arhivat din original la 1 noiembrie 2006. 
  8. ↑ XIV. Sesiune APL // Istoria limbajului de programare / Richard L. Wexelbblat. - Presa Academică, 1981. - S.  661 -693. — 749 p. — ISBN 0-12-745040-8 .
  9. ↑ Evgheni Kirpichev. Elemente ale limbajelor funcționale  // Practicarea programării funcționale. - 2009. - Decembrie ( numărul 3 ). — ISSN 2075-8456 . Arhivat din original pe 3 septembrie 2017.
  10. ↑ Descarcă PDF: „Tehnici de programare funcțională, V. A. Potapenko” p. 8 „Funcții de ordine superioară” . Data accesului: 10 ianuarie 2009. Arhivat din original la 30 iunie 2009.
  11. ↑ GCC, Declararea atributelor funcțiilor . Preluat la 28 august 2012. Arhivat din original la 18 august 2012.
  12. ↑ XL Fortran pentru AIX, V13.1 > Limbă de referință, proceduri pure (Fortran 95)
  13. ↑ Optimizarea apelului de coadă . Data accesului: 31 iulie 2012. Arhivat din original la 1 august 2012.
  14. ↑ Raport revizuit5 privind schema de limbaj algoritmic, 3.5. Recursie corectă a cozii . Data accesului: 31 iulie 2012. Arhivat din original la 5 ianuarie 2007.
  15. ↑ Meijer, Erik ; Fokkinga, Maarten; Paterson, Ross (1991). Programare funcțională cu banane, lentile, plicuri și sârmă ghimpată (PDF) . Conferință despre limbaje funcționale de programare și arhitectură de calculatoare (FPCA). Springer. pp. 124-144. CiteSeerX  10.1.1.41.125 . ISBN  3-540-54396-1 . Arhivat (PDF) din original pe 2017-07-09 . Extras 2020-03-03 . Parametrul depreciat folosit |deadlink=( ajutor )
  16. ↑ Bird, Richard. Perle de design al algoritmului funcțional  . - Cambrigde : University Press , 2010. - 277 p. - ISBN 978-0-521-51338-8 . Arhivat pe 8 martie 2022 la Wayback Machine
  17. ↑ N. A. Roganova Programare funcțională: Manual pentru studenții instituțiilor de învățământ superior - M .: GINFO, 2002. - 260 p. Pagină 14 p. 3.1. Calcul leneș și dornic
  18. ↑ Lazy Evaluation - o prezentare generală | Subiecte ScienceDirect . www.sciencedirect.com . Preluat: 23 martie 2021.
  19. ↑ Ahmechet V. „Programare funcțională pentru toată lumea” . Data accesului: 11 ianuarie 2009. Arhivat din original la 2 februarie 2009.

Literatură

  • Gorodnyaya LV Fundamentele programării funcționale. Curs de prelegeri - M .: Internet University of Information Technologies, 2004. S. 280. ISBN 5-9556-0008-6
  • Dushkin R. V. Programare funcțională în Haskell. — M.: DMK Press, 2006. S. 608. ISBN 5-94074-335-8
  • Câmpul A., Harrison P. Programare funcțională = Programare funcțională. — M .: Mir, 1993. — 637 p. — ISBN 5-03-001870-0 .
  • N. A. Roganova Programare funcţională: Manual pentru studenţii instituţiilor de învăţământ superior - M .: GINFO, 2002. - 260 p.
  • John Harrison. Programare functionala. Curs de prelegeri = Programare Funcțională . — 1997.
  • A. M. Mironov. Teoria programelor funcționale.

Link -uri

  Accesați articolul Wikidata  Dicționare și enciclopedii