Programare funcțională

În informatică , programarea funcțională este o paradigmă de programare în care fluxul de execuție a programului ia forma unei serii de evaluări ale funcțiilor matematice . Principalul punct forte al acestei paradigme este lipsa efectelor secundare (efecte secundare) ale funcțiilor, ceea ce are ca rezultat o verificare mai ușoară a corectitudinii și a lipsei de erori în program și posibilitatea unei optimizări sporite a acestora. O utilizare particulară a paradigmei, pentru optimizarea programelor, este transformarea acestora pentru a le utiliza în programare paralelă .

Programarea funcțională pune un accent mai mare pe definirea funcțiilor, în comparație cu paradigmele procedurale și imperative , care preferă în schimb specificația unei secvențe de comenzi de executat. În acesta din urmă, valorile sunt calculate prin schimbarea stării programului prin sarcini ; un program funcțional, pe de altă parte, este imuabil: valorile nu se găsesc prin schimbarea stării programului, ci prin construirea unor stări noi pornind de la cele anterioare.

Introducere

Funcțiile matematice sunt foarte puternice în ceea ce privește flexibilitatea și analiza. De exemplu, dacă o funcție este idempotentă și nu are efecte secundare, atunci un apel către această funcție care are propria sa ieșire ca intrare ( f (f (x)) ) poate fi calculat eficient cu un singur apel către funcție.

Aceste tipuri de funcții au zero sau mai mulți parametri și o singură valoare returnată. Parametrii sunt intrările funcției, iar valoarea returnată este ieșirea acesteia. Definiția unei funcții descrie modul în care ar trebui evaluată (calculată) în termeni de alte funcții. De exemplu, funcția f (x) = x ² + 2 este definită în termeni de funcții de putere și adunare. La un moment dat în seria apelurilor de funcții, limbajul va oferi funcții atomice, adică funcții care nu apelează nicio altă funcție.

Într-un limbaj de programare funcțional, funcțiile pot fi manipulate în mai multe moduri. De obicei, în aceste limbi, funcțiile sunt entități de primă clasă , adică pot fi transmise ca parametri la alte funcții și pot fi returnate ca valori returnate de alte funcții. Acest lucru permite funcții precum mapcar în Lisp și map în Haskell , care iau o funcție și o listă ca intrare și aplică funcția de intrare fiecărui element al listei, pentru a returna o listă a rezultatelor. Funcțiile pot avea nume, ca în orice altă limbă, sau pot fi definite anonim (uneori chiar și în timpul rulării ) folosind abstractizarea lambda și pot fi utilizate ca valori în alte funcții.

Limbajele funcționale permit, de asemenea, o tehnică numită currying , care vă permite să transformați o funcție cu mai mulți parametri într-o funcție cu un singur parametru care mapează la o altă funcție cu un singur parametru și așa mai departe, până când parametrii sunt epuizați. Funcția transformată poate fi aplicată unui subset al parametrilor săi inițiali și are ca rezultat o nouă funcție în care parametrii acelui subset sunt constante și restul parametrilor au valori nespecificate. În cele din urmă, această nouă funcție poate fi aplicată parametrilor rămași pentru a obține rezultatul final. De exemplu, o funcție sumă (x, y) = x + y poate fi transformată în așa fel încât valoarea returnată a sumei (2) (rețineți că nu există parametru y) este o funcție anonimă echivalentă cu funcția sum2 ( y) = 2 + y . Această nouă funcție are un singur parametru la care adaugă 2. Această tehnică nu ar fi posibilă dacă funcțiile nu ar fi entități de primă clasă .

Istorie

Calculul Lambda poate fi considerat primul limbaj de programare funcțional, chiar dacă nu a fost conceput pentru a rula pe o mașină. Calculul Lambda este un model de calcul conceput de Alonzo Church în anii 1930, care oferă un mod foarte formal de a descrie evaluarea funcțiilor. Primul limbaj de programare funcțional conceput pentru un computer a fost Limbajul de procesare a informațiilor (IPL), dezvoltat de Newell, Shaw și Simon la RAND Corporation pentru computerul JOHNNIAC , la mijlocul anilor 1950 .

Un limbaj funcțional mult îmbunătățit a fost Lisp , dezvoltat de John McCarthy , în timp ce la Massachusetts Institute of Technology , pentru computerele din seria IBM 700/7000 , la sfârșitul anilor 1950. Deși nu este un limbaj pur funcțional, LISP a introdus multe dintre caracteristicile găsite astăzi în limbajele funcționale moderne.

În anii 1970 , limbajul ML a fost creat la Universitatea din Edinburgh , în timp ce la sfârșitul acestui deceniu va fi implementat un dialect al Lisp bazat pe calcul lambda, numit Scheme . De la mijlocul anilor 1980, numeroși cercetători au încercat să implementeze limbaje pure și leneșe , cum ar fi LazyML , Orwell , Clean , Daisy și Miranda . Prima versiune a limbajului Haskell a fost introdusă în 1990 pentru a reuni multe dintre ideile cercetării programării funcționale pentru a crea un limbaj pur .

Comparație cu programarea imperativă

În comparație cu programarea imperativă, programarea funcțională poate părea să nu aibă multe construcții deseori (dar incorect) considerate esențiale pentru un limbaj imperativ, cum ar fi C sau Pascal . De exemplu, în programarea funcțională strictă, nu există alocare explicită de memorie sau atribuire de variabile, dar, cu toate acestea, aceste operații apar automat atunci când este invocată o funcție: alocarea memoriei are loc pentru a crea spațiul necesar pentru parametri și valoarea de returnare și atribuire apare pentru a copia parametrii în noul spațiu alocat și pentru a copia valoarea returnată în funcția de apelare.

Ambele operații pot avea loc numai atunci când se apelează o funcție și se întoarce din aceasta și, prin urmare, efectele secundare sunt eliminate. Prin eliminarea efectelor secundare din funcții, veți obține ceea ce se numește transparență referențială , care asigură că rezultatul unei funcții este același pentru același set de parametri, indiferent de momentul și locul în care această funcție este evaluată. Transparența referențială ușurează atât demonstrarea corectitudinii programului, cât și identificarea automată a calculelor independente pentru executarea paralelă.

Ierațiile , un alt construct al programării imperative, sunt obținute prin construcția mai generală a apelurilor recursive la funcții. Funcțiile recursive se invocă, permițându-vă să efectuați aceeași operație din nou și din nou. Se poate arăta că o iterație este echivalentă cu un tip special de recursivitate numit recursivitate de coadă . Recursivitatea în programarea funcțională poate lua multe forme și, în general, este o tehnică mai puternică decât iterația. Din acest motiv, aproape toate limbile imperative îl susțin (cu excepția notabilă a Fortran 77 și COBOL , înainte de 2002 ).

Limbaje funcționale de programare

Programele pur funcționale (adică cele care obligă să respecte regulile efectului secundar, transparenței referențiale etc., spre deosebire de limbajele non-funcționale care sunt un hibrid între paradigma funcțională și imperativă) nu necesită variabile și nu au efecte garanție și, prin urmare, sunt sigure în mod automat. Limbajele funcționale fac de obicei o utilizare destul de sofisticată a stivei .

Programarea funcțională folosește pe larg recursivitatea și, în unele limbaje, cum ar fi Scheme , unele tipuri de recursivitate (cum ar fi recursivitatea cozii ) sunt recunoscute și optimizate automat de către compilator.

Mai mult, limbajele de programare funcționale impun transparența referențială, ceea ce înseamnă că termenii egali pot fi înlocuiți cu termeni egali fără a modifica rezultatul calculului. De exemplu, putem modifica expresia

 z = f (sqrt (2), sqrt (2));

calculând rădăcina pătrată a lui 2 ( sqrt(2) ) o dată și înlocuind rezultatul cu cei doi parametri

 s = sqrt (2);
    z = f (s, s);

eliminând astfel evaluarea ulterioară a funcției rădăcină pătrată.

Oricât de intuitiv ar părea, acest lucru nu este întotdeauna cazul limbajelor imperative. De exemplu, luați în considerare limbajul C „funcție” getchar() , care citește un caracter din intrarea standard ; este o funcție nu a parametrilor săi, ci a conținutului fluxului stdin și a cât de mult a fost deja citit. De exemplu, educația:

 z = f (getchar (), getchar ());

nu este echivalent cu blocul:

 s = getchar ();
    z = f (s, s);

deoarece în C, getchar() poate returna două valori diferite pentru două apeluri diferite, în funcție de starea unei variabile globale ( stdin ).

În limbajele de programare imperative, efectele secundare ascunse sunt în general regula, nu excepția. Ori de câte ori o procedură citește sau scrie o valoare din / într-o variabilă globală sau partajată, există efecte secundare potențial ascunse. Această lipsă a unei limite precise asupra a ceea ce o funcție poate modifica sau nu duce la o creștere a complexității ascunse a programelor scrise în limbaje nefuncționale.

Eliminând această lipsă de informații despre domeniul unei funcții, limbajele de programare funcționale oferă posibilitatea unor programe mai curate, care sunt mai ușor de proiectat și de depanat . Cu toate acestea, acestea nu sunt singurele avantaje.

Mulți programatori obișnuiți cu paradigme imperative găsesc cu greu învățarea programării funcționale, ceea ce necesită o abordare complet diferită a scrierii programelor. Această dificultate, împreună cu faptul că mediile funcționale de limbaj nu au aceeași cantitate de instrumente și biblioteci disponibile ca limbajele tradiționale, sunt printre principalele motive pentru care programarea funcțională a avut o utilizare redusă în industria software-ului. Limbajele funcționale au rămas în mare parte în domeniul academic și al hobby-urilor și acele limbi care au avut o utilizare mai mare sunt limbaje funcționale „non-pure”, cum ar fi Erlang și Common LISP . S-ar putea spune că cea mai mare influență a limbajelor funcționale asupra industriei software a fost dată de acei programatori, născuți în mediul academic, care au folosit stilul de programare funcțional „non-pur” cu limbajele de programare imperative tradiționale.

Funcții de ordin superior

Același subiect în detaliu: Funcția de comandă superioară .

Un mecanism puternic folosit adesea în programarea funcțională este cel al funcțiilor de ordin superior (sau funcții de ordin superior). Se spune că o funcție este de ordin superior atunci când poate lua alte funcții ca parametri și / sau returnează funcții ca rezultat. Operatorul diferențial în matematică este un exemplu de funcție care mapează o funcție la o altă funcție.

Funcțiile de ordin superior au fost studiate de teoria calculului lambda cu mult înainte de a exista noțiunea de programare funcțională și sunt prezente în proiectarea multor limbaje funcționale de programare, cum ar fi Scheme și Haskell.

Mai general, funcțiile de ordin superior se pot spune că fac parte din limbajul natural . De exemplu, adverbele pot modifica verbele (acțiunile) prin crearea verbelor derivate. Cu același raționament putem spune că verbele imperative sunt similare cu funcțiile „obișnuite” ale limbajelor de programare.

Funcțiile de ordin superior sunt cruciale în paradigma de programare funcțională (nu trebuie confundată cu programarea funcțională, despre care se referă această intrare), care include limbaje precum FP-ul lui John Backus și J.-ul lui Kenneth Eugene Iverson.

Considerații privind eficiența

Limbajele funcționale au fost etichetate mult timp ca limbaje consumatoare de resurse, atât în ceea ce privește procesorul, cât și memoria . Aceasta este din două motive principale:

unele dintre cele mai vechi limbaje funcționale au fost implementate cu puțină atenție la eficiență;
limbajele nefuncționale au câștigat viteză, cel puțin parțial, lăsând programatorului unele sarcini de nivel inferior.

Aceste sarcini de nivel scăzut au fost verificarea legăturilor , adică verificarea valorilor asumate de indexurile bufferelor pentru a evita revărsările , colectarea gunoiului , pentru gestionarea memoriei și altele asemenea. Aceste sarcini sunt părți esențiale ale programelor moderne, iar gestionarea greșită a acestora cauzează majoritatea erorilor software, cum ar fi scurgerile de memorie și diferite tipuri de revărsări.

Cu toate acestea, creșterea performanței computerului a mutat atenția comunității de calculatoare către dezvoltarea rapidă a software-ului, corectitudinea și mentenanța acestuia. Acest lucru a facilitat introducerea tehnicilor de tipul menționat anterior în limbile imperative utilizate în mod obișnuit. Aceasta înseamnă că astăzi converg performanțele limbajelor funcționale și ale limbajelor imperative. Pentru programele care își petrec cea mai mare parte a timpului făcând calcule numerice, unele limbaje funcționale (cum ar fi Ocaml și Clean ) se pot apropia de viteza C , în timp ce pentru programele care gestionează matrice mari și baze de date multidimensionale, aranjează limbaje funcționale (cum ar fi J și K ) sunt de obicei mai rapide decât programele C neoptimizate. Cu toate acestea, limbajele pur funcționale pot deveni considerabil mai lente decât cele imperative atunci când se manipulează structuri de date mari, datorită utilizării mai puțin eficiente a memoriei.

Utilizarea memoriei în programarea funcțională poate fi optimizată utilizând structuri de date persistente; aceste structuri de date permit ca unele sau toate datele să fie partajate cu alte valori, făcând copierea și editarea relativ ieftine. Aceste operațiuni sunt efectuate într-un mod sigur, deoarece aceste structuri de date sunt imuabile și, prin urmare, nu există erori datorate gestionării indicatorilor , așa cum se întâmplă în schimb în structurile de date imperative. Structurile de date persistente utilizate în mod obișnuit sunt liste legate și arbori binari .

Expresiile în limbaje funcționale pot fi evaluate (calculate) în două moduri diferite: într-un mod „riguros” (sau, de asemenea, „dornic” sau „strict”) sau într-un mod „leneș” (sau „leneș”). „Limbajele stricte” calculează toate argumentele unei funcții înainte de a evalua funcția în sine, în timp ce „limbile leneșe” calculează un argument numai atunci când este necesar. Haskell este cel mai frecvent exemplu de limbaj leneș, în timp ce limbajul ML este strict. Evaluarea leneșă este teoretic mai puțin eficientă decât riguroasă, deoarece necesită ca executorul de limbă să păstreze informații despre subiectele evaluate și nu evaluate. Cu toate acestea, este ușor să concepeți căi de execuție în care, neutilizând efectiv unul sau mai multe argumente, tehnica leneșă câștigă viteză (acest lucru este probabil mai ales când argumentele unei funcții sunt ele însele apeluri la alte funcții, potențial imbricate la mai multe niveluri de adâncime).

Performanța competitivă a limbajelor funcționale moderne (non-pure), cum ar fi Ocaml și SML, a condus la adoptarea lor în zone de calcul științifice dominate istoric de Fortran . Aceste limbaje moderne, grație conciziei și expresivității lor și grație aranjării unor structuri și algoritmi de date sofisticate, sunt astăzi utilizate în vaste domenii științifice, cum ar fi analiza numerică.

Limbaje funcționale

Cel mai vechi exemplu de limbaj funcțional este Lisp , deși nici LISP-ul original, nici Lisp-ul modern, cum ar fi Common Lisp, nu sunt pur funcționale. Variațiile Lisp includ Logo - ul , Schema , Dylan și Clojure . Exemple de limbaje funcționale moderne sunt Haskell și limbile familiei ML, cum ar fi ML și OCaml . Un alt limbaj derivat din ML este F # , dezvoltat de Microsoft în cadrul .NET . Scala rulează în schimb pe Java Runtime Environment (JRE).

Alții sunt Erlang , Mathematica , Clean și Miranda .

Alte limbi, cum ar fi Ruby , Python , Perl și TCL , pot fi utilizate într-un stil funcțional, deoarece au funcții de ordin superior și alte abstracții utile.

Astăzi încercăm, de asemenea, să dezvoltăm limbaje de programare cuantice funcționale, adică care pot exprima algoritmi cuantici . Câteva exemple sunt limbajul Peter Selinger ( EN ) descris aici și limbajul QML asemănător cu Haskell.

Bibliografie

( EN ) Cousineau, Guy și Michel Mauny. Abordarea funcțională a programării . Cambridge, Marea Britanie: Cambridge University Press, 1998.
( EN ) Felleisen, Matthias, Robert Findler, Matthew Flatt și Shriram Krishnamurthi. Cum se proiectează programe HTDP. Apăsați MIT. 2001. online
( EN ) Graham, Paul. ANSI Common LISP . Englewood Cliffs, New Jersey: Prentice Hall, 1996.
(EN) Hudak, Paul. „Concepția, evoluția și aplicarea limbajelor de programare funcționale”. ACM Computing Surveys 21 , n. 3 (1989): 359-411.
( EN ) Pratt, Terrence, W. și Marvin V. Zelkowitz. Limbaje de programare: proiectare și implementare . Ediția a treia. Englewood Cliffs, New Jersey: Prentice Hall, 1996.
( EN ) Salus, Peter H. Limbaje de programare funcționale și logice . Al patrulea volum al Manualului de limbaje de programare. Indianapolis, Indiana: Editura tehnică Macmillan, 1998.
(EN) Thompson, Simon. Haskell: Meșteșugul programării funcționale . Harlow, Anglia: Addison-Wesley Longman Limited, 1996.

Elemente conexe

linkuri externe

( RO ) De ce funcționează programarea funcțională de John Hughes
( EN ) „Programare funcțională” ^{[ link rupt ]} -Capitolul de trimestru al Advanced Language Programming Design Raphael Finkel , o introducere a programării funcționale
(EN) Programare funcțională în Python (a lui David Mertz ): Partea 1 , Partea 2 , Partea 3

Controlul autorității	Tesauro BNCF 64 923 · LCCN (EN) sh87007844 · GND (DE) 4198740-8 · BNF (FR) cb121910539 (dată) · BNE (ES) XX547935 (dată)

Portal IT : accesați intrările Wikipedia care se ocupă cu IT