Elemente de programare funcțională. Caracteristici ale limbajelor de programare funcționale

Programarea funcțională este o ramură a matematicii discrete și o paradigmă de programare în care procesul de calcul este interpretat ca calcularea valorilor funcțiilor în sensul matematic al acestora din urmă (spre deosebire de funcțiile ca subrutine în programarea procedurală).

Este în contrast cu paradigma de programare imperativă, care descrie procesul de calcul ca o schimbare secvențială a stărilor (într-un sens similar cu cel din teoria automatelor). Dacă este necesar, în programarea funcțională întregul set de stări secvențiale ale unui proces de calcul este reprezentat în mod explicit, de exemplu, ca o listă.

Programarea funcțională implică 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ță, nu implică schimbarea acestei stări (spre deosebire de cea imperativă, unde unul dintre conceptele de bază este o variabilă care stochează valoarea acesteia și permite modificarea acesteia pe măsură ce se execută algoritmul).

Î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 și, de asemenea, au efecte secundare și modifică starea variabilelor externe. Astfel, în programarea imperativă, la apelarea aceleiași funcție cu aceiași parametri, dar în etape diferite ale algoritmului, puteți obține date de ieșire diferite datorită influenței stării variabilelor asupra funcției. Și într-un limbaj funcțional, atunci când apelăm o funcție cu aceleași argumente, vom obține întotdeauna același rezultat: ieșirea depinde doar de intrare. Acest lucru permite runtimelor de limbaj funcțional să memoreze în cache rezultatele funcțiilor și să le apeleze într-o ordine nedeterminată de algoritm. (vezi Funcții pure mai jos)

λ-calcul este baza pentru programarea funcțională, multe limbaje funcționale pot fi considerate ca o „suprastructură” pe deasupra.

Puncte forte

[edit]Creșterea 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ă. Incapacitatea de a muta datele atunci când sunt utilizate în diferite locuri din program elimină apariția erorilor greu de detectat (cum ar fi, de exemplu, atribuirea accidentală a unei valori greșite unei variabile globale într-un program imperativ).

[edit]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 nici în interiorul domeniului, nici în exterior (spre deosebire de programele imperative, în care o funcție poate seta o variabilă externă care este citită de o a doua funcție). Singurul efect al evaluării unei funcții este rezultatul pe care îl returnează, iar singurul factor care influențează rezultatul este valorile argumentelor.

Astfel, este posibil să se testeze 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 cu privire la apelarea funcțiilor în ordinea corectă sau la formarea corectă a stării externe. Dacă orice funcție dintr-un program trece testele unitare, atunci puteți avea încredere în 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 trebuie făcut în programele funcționale.

[edit]Opțiuni de optimizare în timpul compilării

O caracteristică pozitivă menționată în mod tradițional a programării funcționale este aceea că vă permite să descrieți un program în așa-numita formă „declarativă”, atunci când succesiunea 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 [sursa] nespecificat 1064 zile] Această împrejurare, precum și absența stărilor, face posibilă aplicarea unor metode de optimizare automată destul de complexe la programele funcționale.

[edit]Capacitățile de concurență

Un alt avantaj al programelor funcționale este că oferă oportunități extinse pentru paralelizarea automată a calculelor. Deoarece absența efectelor secundare este garantată, în orice apel de funcție este întotdeauna posibil să se evalueze doi parametri diferiți în paralel - ordinea în care sunt evaluați nu poate afecta rezultatul apelului.

[edit]Dezavantaje

Dezavantajele programării funcționale provin din aceleași caracteristici. Absența atribuirilor și înlocuirea lor cu generarea de date noi duce la necesitatea alocării constante și eliberării automate a memoriei, prin urmare, în sistemul de execuție al unui program funcțional, un colector de gunoi foarte eficient devine o componentă obligatorie. Un model de calcul slab are ca rezultat o ordonare 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ă (cum ar fi getchar din biblioteca standard C) nu sunt curate, deoarece pot returna valori diferite pentru aceleași argumente, iar acest lucru necesită unele trucuri pentru a depăși.

Pentru a depăși deficiențele programelor funcționale, deja primele limbaje de programare funcționale includeau nu numai instrumente pur funcționale, ci și mecanisme de programare imperative (atribuirea, bucla, „PROGN implicit” erau deja în LISP). Folosirea unor astfel de instrumente vă permite să rezolvați unele probleme practice, dar înseamnă să vă îndepărtați de ideile (și avantajele) de programare funcțională și de a scrie programe imperative în limbaje funcționale [sursa nespecificată 1064 zile] În limbaje funcționale pure, aceste probleme sunt rezolvate de alte mijloace, de exemplu, în limbajul Haskell I/O sunt implementate folosind monade, un concept non-trivial împrumutat din teoria categoriilor.

Recursiunea coadă este un caz special de recursivitate în care apelul recursiv al unei funcții este ultima operație. Acest tip de recursivitate este remarcabil prin faptul că poate fi înlocuit cu ușurință prin iterație, care este implementată în multe compilatoare de optimizare. Când o funcție este apelată, computerul trebuie să-și amintească locația din care a fost apelată funcția (adresa de retur) pentru a reveni după finalizarea acesteia și a continua executarea programului. De obicei, adresa de retur este stocată pe stivă. Uneori, ultima acțiune a unei funcții după ce toate celelalte operațiuni s-au finalizat este pur și simplu apelarea funcției, poate ea însăși, și returnarea unui rezultat. În acest caz, nu este nevoie să vă amintiți adresa de returnare, noua funcție apelată va returna rezultatul direct în locul în care a fost apelată funcția inițială. Recursiunea cozii este adesea folosită în programele din limbaje de programare funcționale. Este firesc să exprimăm multe calcule în astfel de limbi sub formă de funcții recursive, iar capacitatea traducătorului de a înlocui automat recursiunea coadă cu iterație înseamnă că, din punct de vedere al eficienței de calcul, este egal cu codul echivalent scris în formă iterativă.

Creatorii limbajului funcțional Scheme, unul dintre dialectele Lisp, au apreciat atât de mult importanța recursiunii cozii încât în ​​specificația limbajului au prescris ca fiecare traducător al acestui limbaj să implementeze optimizarea recursiunii cozii.

Funcție de ordin superior- o funcție care ia alte funcții ca argumente sau returnează o altă funcție ca rezultat. Uneori, funcțiile de ordin superior sunt numite funcționale, deși acest lucru nu este complet corect, un echivalent mai precis este un operator.

În limbajele de programare funcționale, toate funcțiile sunt funcții de ordin superior.

Funcțiile sunt abstracții, în care detaliile de implementare ale unei acțiuni sunt ascunse în spatele unui nume separat. Un set bine scris de funcții le permite să fie utilizate de mai multe ori. Biblioteca standard Python vine cu o multitudine de funcții pre-construite și depanate, dintre care multe sunt suficient de versatile pentru a gestiona o mare varietate de intrări. Chiar dacă o anumită secțiune de cod nu este folosită de mai multe ori, dar în ceea ce privește datele de intrare și ieșire este destul de autonomă, poate fi separată în siguranță într-o funcție separată.

Această prelegere este mai orientată spre considerații practice decât spre teoria programării funcționale. Cu toate acestea, acolo unde este necesar, termenii relevanți vor fi utilizați și explicați.

În continuare, ne vom uita în detaliu la descrierea și utilizarea funcțiilor în Python, recursiunea, funcțiile de trecere și returnare ca parametri, procesarea secvenței și iteratoare, precum și conceptul de generator. Se va demonstra că în Python, funcțiile sunt obiecte (și, prin urmare, pot fi trecute ca parametri și returnate ca rezultat al executării funcțiilor). În plus, vom vorbi despre cum puteți implementa unele mecanisme de programare funcțională care nu au suport sintactic direct în Python, dar sunt răspândite în limbaje de programare funcționale.

Ce este programarea funcțională?

Programare functionala este un stil de programare care utilizează numai compoziţii de funcţii. Cu alte cuvinte, asta programareîn expresii mai degrabă decât în ​​comenzi imperative.

După cum subliniază David Mertz în articolul său despre programarea funcțională în Python, „functional programare - programareîn limbaje funcționale (LISP, ML, OCAML, Haskell, ...)", ale căror principale atribute sunt:

• „Prezența funcțiilor de primă clasă” (funcțiile, ca și alte obiecte, pot fi transferate în interiorul funcțiilor).
• Recursiunea este principala structură de control dintr-un program.
• Prelucrarea listelor (secvente).
• Interzicerea efectelor secundare în funcții, ceea ce înseamnă în primul rând absența atribuirii (în limbaje funcționale „pure”)
• Operatorii sunt interziși și se pune accent pe expresii. În loc de operatori, întregul program este în mod ideal o expresie cu definiții însoțitoare.
• Întrebare cheie: Ce trebuie calculat, nu Cum.
• Utilizarea funcțiilor de ordin superior (funcții peste funcții peste funcții).

Program funcțional

În matematică, o funcție afișează obiecte din același set ( seturi de definiții de funcție) altcuiva ( set de valori ale funcției). Funcții matematice (se numesc curat) „mecanic”, ei calculează fără ambiguitate rezultatul din argumentele date. Funcțiile pure nu ar trebui să stocheze date între două apeluri. Te poți gândi la ele ca la cutii negre, despre care știi doar ce fac, dar deloc cum.

Programele de stil funcțional sunt concepute ca compoziţie funcții. În acest caz, funcțiile sunt înțelese aproape în același mod ca și în matematică: ele mapează un obiect cu altul. În programare, funcțiile „pure” sunt un ideal care nu este întotdeauna realizabil în practică. Funcțiile practice utile au de obicei prin efect: Salvați starea între apeluri sau modificați starea altor obiecte. De exemplu, este imposibil să ne imaginăm funcții I/O fără efecte secundare. De fapt, astfel de funcții sunt folosite de dragul acestor „efecte”. În plus, funcțiile matematice funcționează cu ușurință cu obiecte care necesită o cantitate infinită de informații (de exemplu, numere reale). În general, computerul

Mulțimea X se numește domeniul de definire al funcției P, iar mulțimea Y ​​este domeniul valorilor funcției P. Valoarea x în P(x), care reprezintă orice element din mulțimea X, se numește variabilă independentă, iar valoarea y din mulțimea Y, definită de ecuația y = P(x ) se numește variabilă dependentă. Uneori, dacă o funcție f nu este definită pentru tot x din X, se vorbește despre o funcție parțial definită, altfel înseamnă o definiție completă.

O proprietate foarte importantă a definiției matematice a unei funcții este că, având în vedere un argument x, acesta determină întotdeauna aceeași valoare deoarece nu are efecte secundare. Efectele secundare în limbajele de programare sunt asociate cu variabile care modelează celulele de memorie. O funcție matematică determină o valoare, mai degrabă decât să specifice o secvență de operații asupra numerelor stocate în locații de memorie pentru a calcula o anumită valoare. Nu există variabile în sensul dat în limbajele de programare imperative, deci nu pot exista efecte secundare.

Într-un limbaj de programare bazat pe conceptul matematic de funcție, pot fi reprezentate programe, proceduri și funcții. În cazul unui program, x corespunde datelor de intrare, iar y corespunde rezultatelor. În cazul unei proceduri sau funcție, x caracterizează parametrii, iar y caracterizează valorile returnate. În ambele cazuri, x poate fi denumit „intrări” și y ca „ieșiri”. Prin urmare, în abordarea funcțională a programării, nu există nicio distincție între program, procedură și funcție. Pe de altă parte, cantitățile de intrare și de ieșire sunt întotdeauna diferite.

Limbajele de programare au o separare foarte clară între definirea unei funcții și utilizarea unei funcții. O definiție a funcției descrie modul în care o cantitate poate fi calculată pe baza parametrilor formali. O aplicație de funcție este să apeleze o anumită funcție folosind parametri reali. Rețineți că în matematică diferența dintre un parametru și o variabilă nu este întotdeauna evidentă. Foarte des termenul „parametru” este înlocuit cu termenul „variabilă independentă”. De exemplu, la matematică puteți scrie definiția funcției de pătrat: pătrat(x) = x * x

Să presupunem că x satisface pătrat(x) + 2 . . .

Principala diferență dintre programarea imperativă și cea funcțională este interpretarea conceptului de variabilă. În matematică, variabilele sunt reprezentate ca valori reale, iar în limbajele de programare imperative, variabilele se referă la locațiile de memorie în care sunt stocate valorile lor. Atribuțiile vă permit să schimbați valorile în aceste zone de memorie. În schimb, în ​​matematică nu există concepte de „zonă de stocare” și „atribuire”, deci un operator precum x = x + 1

nu are sens. Programarea funcțională se bazează pe o abordare matematică a conceptului de „variabilă”. În programarea funcțională, variabilele sunt asociate cu valori, dar nu au nimic de-a face cu locațiile de memorie. După legarea unei variabile la o valoare, valoarea variabilei se modifică

String reverse(String arg) ( if(arg.length == 0) ( return arg; ) else ( return reverse(arg.substring(1, arg.length)) + arg.substring(0, 1); ) )
Această funcție este destul de lentă, deoarece se autoapelează în mod repetat. Este posibil să existe o scurgere de memorie aici, deoarece obiectele temporare sunt create de multe ori. Dar acesta este un stil funcțional. S-ar putea să vi se pare ciudat cum oamenii pot programa astfel. Ei bine, tocmai voiam să-ți spun.

Beneficiile programării funcționale

Probabil vă gândiți că nu pot face un argument pentru a justifica caracteristica monstruoasă de mai sus. Când am început să învăț programarea funcțională, am crezut și eu. M-am înșelat. Există argumente foarte bune pentru acest stil. Unele dintre ele sunt subiective. De exemplu, programatorii susțin că programele funcționale sunt mai ușor de înțeles. Nu voi face astfel de argumente, pentru că toată lumea știe că ușurința de a înțelege este un lucru foarte subiectiv. Din fericire pentru mine, există încă o mulțime de argumente obiective.

Testarea unitară

Deoarece fiecare simbol din FP este imuabil, funcțiile nu au efecte secundare. Nu puteți modifica valorile variabilelor, iar o funcție nu poate schimba o valoare în afara domeniului său de aplicare și, prin urmare, nu poate afecta alte funcții (cum se poate întâmpla cu câmpurile de clasă sau variabilele globale). Aceasta înseamnă că singurul rezultat al execuției funcției este valoarea returnată. Și singurul lucru care poate afecta valoarea returnată sunt argumentele transmise funcției.

Iată-l, visul albastru al testerilor de unitate. Puteți testa fiecare funcție dintr-un program folosind doar argumentele necesare. Nu este nevoie să apelați funcții în ordinea corectă sau să recreați starea externă corectă. Tot ce trebuie să faceți este să transmiteți argumente care se potrivesc cu cazurile marginale. Dacă toate funcțiile din programul dvs. trec testele unitare, atunci puteți fi mult mai încrezător în calitatea software-ului dvs. decât în ​​cazul limbajelor de programare imperative. În Java sau C++, verificarea valorii returnate nu este suficientă - funcția poate schimba starea externă, care este, de asemenea, supusă verificării. Nu există o astfel de problemă în FP.

Depanare

Dacă un program funcțional nu se comportă așa cum vă așteptați, atunci depanarea este o simplă simplă. Puteți reproduce întotdeauna problema deoarece eroarea din funcție nu depinde de codul străin care a fost executat anterior. Într-un program imperativ, eroarea apare doar pentru o perioadă. Va trebui să parcurgeți o serie de pași non-bug din cauza faptului că funcționarea funcției depinde de starea externă și de efectele secundare ale altor funcții. În FP, situația este mult mai simplă - dacă valoarea returnată este incorectă, atunci va fi întotdeauna incorectă, indiferent ce bucăți de cod au fost executate înainte.

Odată ce reproduci bug-ul, găsirea sursei sale este o sarcină trivială. E chiar frumos. De îndată ce opriți programul, veți avea în față întreaga stivă de apeluri. Puteți vizualiza argumentele fiecărui apel de funcție, la fel ca într-un limbaj imperativ. Cu diferența că într-un program imperativ acest lucru nu este suficient, deoarece funcțiile depind de valorile câmpurilor, variabilelor globale și stărilor altor clase. O funcție în FP depinde doar de argumentele sale, iar această informație este chiar în fața ochilor tăi! Chiar mai mult, într-un program imperativ, verificarea valorii returnate nu este suficientă pentru a spune dacă o bucată de cod se comportă corect. Va trebui să vânați zeci de obiecte în afara funcției pentru a vă asigura că totul funcționează corect. În programarea funcțională, tot ce trebuie să faci este să te uiți la valoarea returnată!

Pe măsură ce parcurgeți stiva, acordați atenție argumentelor transmise și valorilor returnate. Odată ce valoarea returnată se abate de la normă, detaliați funcția și continuați. Acest lucru se repetă de mai multe ori până când găsiți sursa erorii!

Multithreading

Programul funcțional este imediat gata pentru paralelizare fără modificări. Nu trebuie să vă faceți griji cu privire la blocaje sau condițiile de cursă pentru că nu aveți nevoie de încuietori! Nici o singură bucată de date dintr-un program funcțional nu este schimbată de două ori de același fir sau de altele diferite. Aceasta înseamnă că puteți adăuga cu ușurință fire de execuție la programul dvs. fără a fi vreodată să vă faceți griji cu privire la problemele inerente limbilor imperative.

Dacă acesta este cazul, atunci de ce sunt limbajele de programare funcționale atât de rar utilizate în aplicațiile multithreaded? De fapt, mai des decât crezi. Ericsson a dezvoltat un limbaj funcțional numit Erlang pentru utilizare pe comutatoarele de telecomunicații scalabile și tolerante la erori. Mulți au remarcat avantajele Erlang și au început să-l folosească. Vorbim despre telecomunicații și sisteme de control al traficului, care nu sunt nici pe departe la fel de ușor scalabile ca sistemele tipice dezvoltate pe Wall Street. De fapt, sistemele scrise în Erlang nu sunt la fel de scalabile și de încredere ca sistemele Java. Sistemele Erlang sunt pur și simplu super fiabile.

Povestea multithreading-ului nu se termină aici. Dacă scrieți o aplicație în esență cu un singur thread, compilatorul poate optimiza în continuare programul funcțional pentru a utiliza mai multe procesoare. Să ne uităm la următoarea bucată de cod.

Un compilator de limbaj funcțional poate analiza codul, clasifica funcțiile care produc liniile s1 și s2 ca funcții consumatoare de timp și le poate rula în paralel. Acest lucru este imposibil de realizat într-un limbaj imperativ, deoarece fiecare funcție poate schimba starea externă, iar codul imediat după apel poate depinde de aceasta. În FP, analiza automată a funcțiilor și căutarea candidaților potriviți pentru paralelizare este o sarcină banală, cum ar fi automat inline! În acest sens, stilul de programare funcțional este pregătit pentru viitor. Dezvoltatorii de hardware nu mai pot face CPU-ul să funcționeze mai repede. În schimb, cresc numărul de nuclee și pretind o creștere de patru ori a vitezei de calcul multi-threaded. Desigur, ei uită să spună la timp că noul tău procesor va arăta doar câștiguri în programele concepute având în vedere paralelizarea. Există foarte puține dintre acestea printre software-ul imperativ. Dar 100% dintre programele funcționale sunt gata pentru multithreading din cutie.

Implementare la cald

Pe vremuri, trebuia să reporniți computerul pentru a instala actualizările Windows. Multe ori. După instalarea unei noi versiuni a playerului media. Au existat schimbări semnificative în Windows XP, dar situația este încă departe de a fi ideală (am rulat Windows Update la serviciu astăzi și acum memento-ul enervant nu mă va lăsa în pace până când nu repornesc). Sistemele Unix au avut un model de actualizare mai bun. Pentru a instala actualizări, a trebuit să opresc unele componente, dar nu întregul sistem de operare. Deși situația arată mai bine, încă nu este acceptabilă pentru o clasă mare de aplicații server. Sistemele de telecomunicații trebuie să fie pornite 100% din timp, deoarece dacă o actualizare împiedică o persoană să cheme o ambulanță, se pot pierde vieți. De asemenea, firmele de pe Wall Street nu doresc să închidă serverele în weekend pentru a instala actualizări.

În mod ideal, trebuie să actualizați toate secțiunile necesare ale codului fără a opri sistemul în principiu. În lumea imperativă acest lucru este imposibil [trad. în Smalltalk este foarte posibil]. Imaginați-vă că descărcați o clasă Java din mers și reîncărcați o nouă versiune. Dacă am face acest lucru, atunci toate instanțele clasei ar deveni nefuncționale, deoarece starea pe care au stocat-o s-ar pierde. Ar trebui să scriem un cod complicat pentru controlul versiunilor. Ar trebui să serializăm toate instanțele create ale clasei, apoi să le distrugem, să creăm instanțe ale unei clase noi, să încercăm să încărcăm datele serializate în speranța că migrarea va decurge fără probleme și noile instanțe vor fi valabile. Și în plus, codul de migrare trebuie scris manual de fiecare dată. Și codul de migrare trebuie să păstreze legăturile dintre obiecte. În teorie este în regulă, dar în practică nu va funcționa niciodată.

Într-un program funcțional, toate stările sunt stocate pe stivă ca argumente ale funcției. Acest lucru face implementarea la cald mult mai ușoară! În esență, tot ce trebuie să faceți este să calculați diferența dintre codul de pe serverul de producție și noua versiune și să instalați modificările în cod. Restul se va face automat de instrumentele lingvistice! Dacă crezi că asta este science fiction, gândește-te de două ori. Inginerii care lucrează cu Erlang și-au actualizat sistemele de ani de zile fără a-și opri munca.

Probe și optimizări asistate de mașini

O altă proprietate interesantă a limbajelor de programare funcționale este că pot fi învățate din punct de vedere matematic. Deoarece un limbaj funcțional este o implementare a unui sistem formal, toate operațiile matematice utilizate pe hârtie pot fi aplicate programelor funcționale. Compilatorul, de exemplu, poate converti o bucată de cod într-o bucată echivalentă, dar mai eficientă, justificând în același timp matematic echivalența lor. Bazele de date relaționale fac astfel de optimizări de ani de zile. Nimic nu vă împiedică să utilizați tehnici similare în programele obișnuite.

În plus, puteți folosi matematica pentru a demonstra corectitudinea secțiunilor programelor dvs. Dacă doriți, puteți scrie instrumente care să vă analizeze codul și să creați automat teste unitare pentru cazurile marginale! Această funcționalitate este de neprețuit pentru sistemele solide. Atunci când se dezvoltă sisteme de monitorizare a stimulatorului cardiac sau de management al traficului aerian, astfel de instrumente sunt obligatorii. Dacă dezvoltările tale nu sunt în domeniul aplicațiilor critice, atunci instrumentele automate de verificare îți vor oferi în continuare un avantaj imens față de concurenții tăi.

Funcții de ordin superior

Amintiți-vă, când am vorbit despre beneficiile FP, am observat că „totul arată frumos, dar este inutil dacă trebuie să scriu într-un limbaj stângaci în care totul este definitiv”. Aceasta a fost o concepție greșită. Utilizarea finalului peste tot pare stângace doar în limbaje de programare imperative, cum ar fi Java. Limbajele de programare funcționale operează cu alte tipuri de abstracții, care te fac să uiți că ți-a plăcut vreodată să schimbi variabile. Un astfel de instrument este funcțiile de ordin superior.

În FP, o funcție nu este același lucru cu o funcție în Java sau C. Este un superset - ei pot face același lucru ca funcțiile Java și chiar mai mult. Să presupunem că avem o funcție în C:

Int add(int i, int j) ( return i + j; )
În FP, aceasta nu este același lucru cu o funcție C obișnuită. Să extindem compilatorul nostru Java pentru a sprijini această notație. Compilatorul trebuie să transforme declarația funcției în următorul cod Java (rețineți că există o final implicită peste tot):

Clasa add_function_t ( int add(int i, int j) ( return i + j; ) ) add_function_t add = new add_function_t();
Simbolul de adăugare nu este cu adevărat o funcție. Aceasta este o clasă mică cu o singură metodă. Acum putem trece add ca argument altor funcții. O putem scrie într-un alt simbol. Putem crea instanțe de add_function_t în timpul execuției și acestea vor fi distruse de colectorul de gunoi dacă nu mai sunt necesare. Funcțiile devin obiecte de bază, la fel ca numerele și șirurile. Funcțiile care operează pe funcții (luați-le drept argumente) sunt numite funcții de ordin superior. Nu lăsa asta să te sperie. Conceptul de funcții de ordin superior este aproape același cu conceptul de clase Java care operează una pe cealaltă (putem trece clase altor clase). Le putem numi „clase de ordin superior”, dar nimeni nu se deranjează cu asta, deoarece Java nu are o comunitate academică riguroasă în spate.

Cum și când ar trebui să utilizați funcțiile de ordin superior? Mă bucur că ai întrebat. Îți scrii programul ca o bucată mare de cod monolitică fără să-ți faci griji cu privire la ierarhia claselor. Dacă vedeți că o bucată de cod se repetă în locuri diferite, o mutați într-o funcție separată (din fericire, școlile încă învață cum să facă acest lucru). Dacă observați că o parte din logica din funcția dvs. ar trebui să se comporte diferit în unele situații, atunci creați o funcție de ordin superior. Confuz? Iată un exemplu real din munca mea.

Să presupunem că avem o bucată de cod Java care primește un mesaj, îl transformă în diverse moduri și îl transmite către alt server.

Void handleMessage(Msg de mesaj) ( // ... msg.setClientCode("ABCD_123"); // ... sendMessage(msg); ) // ... )
Acum imaginați-vă că sistemul s-a schimbat și acum trebuie să distribuiți mesajele între două servere în loc de unul. Totul rămâne neschimbat, cu excepția codului client - al doilea server dorește să primească acest cod într-un format diferit. Cum putem face față acestei situații? Putem verifica unde ar trebui să meargă mesajul și putem seta codul client corect pe baza acestuia. De exemplu astfel:

Clasa MessageHandler ( void handleMessage(Message msg) ( // ... if(msg.getDestination().equals("server1") ( msg.setClientCode("ABCD_123"); ) else ( msg.setClientCode("123_ABC") ) // ... sendMessage(msg ) // ... )
Dar această abordare nu se extinde bine. Pe măsură ce se adaugă noi servere, caracteristica va crește liniar, iar efectuarea modificărilor va deveni un coșmar. Abordarea orientată pe obiect constă în izolarea unei superclase comune MessageHandler și subclasarea logicii pentru definirea codului client:

Clasa abstractă MessageHandler ( void handleMessage(Message msg) ( // ... msg.setClientCode(getClientCode()); // ... sendMessage(msg); ) abstract String getClientCode(); // ... ) clasa MessageHandlerOne extinde MessageHandler ( String getClientCode() ( returnează „ABCD_123”; ) ) clasa MessageHandlerTwo extinde MessageHandler ( String getClientCode() ( returnează „123_ABCD”; ) )
Acum pentru fiecare server putem crea o instanță a clasei corespunzătoare. Adăugarea de noi servere devine mai convenabilă. Dar există mult text pentru o schimbare atât de mică. A trebuit să creez două tipuri noi doar pentru a adăuga suport pentru cod de client diferit! Acum să facem același lucru în limba noastră cu suport pentru funcții de ordin superior:

Clasa MessageHandler ( void handleMessage(Message msg, Function getClientCode) ( // ... Message msg1 = msg.setClientCode(getClientCode()); // ... sendMessage(msg1); ) // ... ) String getClientCodeOne( ) ( returnează „ABCD_123”; ) String getClientCodeTwo() ( returnează „123_ABCD”; ) MessageHandler handler = new MessageHandler(); handler.handleMessage(someMsg, getClientCodeOne);
Nu am creat noi tipuri și nu am complicat ierarhia claselor. Pur și simplu am trecut funcția ca parametru. Am obținut același efect ca și în omologul orientat pe obiecte, dar cu unele avantaje. Nu ne-am legat de nicio ierarhie de clasă: putem trece orice alte funcții la runtime și le putem modifica oricând, menținând în același timp un nivel ridicat de modularitate cu mai puțin cod. În esență, compilatorul a creat lipici orientat pe obiecte pentru noi! În același timp, toate celelalte avantaje ale FP sunt păstrate. Desigur, abstracțiile oferite de limbajele funcționale nu se termină aici. Funcțiile de ordin superior sunt doar începutul

curry

Majoritatea oamenilor pe care i-am întâlnit au citit cartea Design Patterns by Gang of Four. Orice programator care se respectă va spune că cartea nu este legată de niciun limbaj de programare specific, iar tiparele sunt aplicabile dezvoltării software în general. Aceasta este o afirmație nobilă. Dar, din păcate, este departe de adevăr.

Limbile funcționale sunt incredibil de expresive. Într-un limbaj funcțional, nu veți avea nevoie de modele de design, deoarece limbajul este atât de înalt încât puteți începe cu ușurință programarea în concepte care elimină toate modelele de programare cunoscute. Unul dintre aceste modele este Adaptor (cu ce este diferit de Façade? Se pare că cineva a trebuit să ștampileze mai multe pagini pentru a îndeplini termenii contractului). Acest model se dovedește a fi inutil dacă limba acceptă curry.

Modelul Adaptor este cel mai adesea aplicat unității „standard” de abstractizare din Java - clasa. În limbajele funcționale, modelul este aplicat funcțiilor. Modelul ia o interfață și o transformă într-o altă interfață în funcție de anumite cerințe. Iată un exemplu de model de adaptor:

Int pow(int i, int j); int pătrat(int i) ( return pow(i, 2); )
Acest cod adaptează interfața unei funcții care ridică un număr la o putere arbitrară la interfața unei funcții care pune în pătrat un număr. În cercurile academice, această tehnică simplă se numește curry (după logicianul Haskell Curry, care a efectuat o serie de trucuri matematice pentru a formaliza totul). Deoarece funcțiile sunt folosite peste tot ca argumente în FP, currying-ul este folosit foarte des pentru a aduce funcții la interfața necesară într-un loc sau altul. Deoarece interfața unei funcții este argumentele sale, currying este folosit pentru a reduce numărul de argumente (ca în exemplul de mai sus).

Acest instrument este construit în limbaje funcționale. Nu trebuie să creați manual o funcție care include originalul. Un limbaj funcțional va face totul pentru tine. Ca de obicei, să ne extindem limba adăugând curry.

Pătrat = int pow(int i, 2);
Cu această linie creăm automat o funcție de pătrat cu un singur argument. Noua funcție va apela funcția pow, înlocuind 2 ca al doilea argument. Din perspectiva Java, ar arăta astfel:

Clasa square_function_t ( int square(int i) ( return pow(i, 2); ) ) square_function_t square = new square_function_t();
După cum puteți vedea, am scris pur și simplu un wrapper peste funcția originală. În FP, curry este doar o modalitate simplă și convenabilă de a crea ambalaje. Te concentrezi pe sarcină, iar compilatorul scrie codul necesar pentru tine! Este foarte simplu și se întâmplă de fiecare dată când doriți să utilizați modelul Adaptor (wrapper).

Evaluare leneșă

Evaluarea leneșă (sau amânată) este o tehnică interesantă care devine posibilă odată ce înțelegi filozofia funcțională. Am văzut deja următoarea bucată de cod când vorbim despre multithreading:

String s1 = somewhatLongOperation1(); String s2 = somewhatLongOperation2(); String s3 = concatenate(s1, s2);
În limbajele de programare imperative, ordinea calculului nu ridică întrebări. Deoarece fiecare funcție poate afecta sau depinde de starea externă, este necesar să se mențină o ordine clară a apelurilor: mai întâi somewhatLongOperation1 , apoi somewhatLongOperation2 și concatena la sfârșit. Dar nu totul este atât de simplu în limbaje funcționale.

După cum am văzut mai devreme, somewhatLongOperation1 și somewhatLongOperation2 pot fi rulate simultan, deoarece funcțiile sunt garantate să nu afecteze sau să depind de starea globală. Dar dacă nu vrem să le executăm simultan, ar trebui să le numim secvenţial? Raspunsul este nu. Aceste calcule ar trebui să fie executate numai dacă orice altă funcție depinde de s1 și s2. Nici măcar nu trebuie să le executăm până nu avem nevoie de ele în concatenate . Dacă în loc să concatenăm înlocuim o funcție care, în funcție de condiție, folosește unul dintre cele două argumente, atunci al doilea argument poate să nu fie calculat nici măcar! Haskell este un exemplu de limbaj de evaluare leneș. Haskell nu garantează niciun ordin de apel (deloc!), deoarece Haskell execută cod după cum este necesar.

Calculul leneș are o serie de avantaje, precum și unele dezavantaje. În secțiunea următoare vom discuta despre avantaje și vă voi explica cum să trăiți cu dezavantajele.

Optimizare

Evaluarea leneșă oferă un potențial enorm de optimizare. Un compilator leneș privește codul în același mod în care un matematician privește expresiile algebrice - poate anula lucruri, poate anula execuția anumitor secțiuni de cod, poate schimba ordinea apelurilor pentru o eficiență mai mare, poate chiar aranja codul în așa fel încât să reducă numărul de erori, asigurând totodată integritatea programului. Acesta este cel mai mare avantaj al descrierii unui program folosind primitive formale stricte - codul se supune legilor matematice și poate fi studiat folosind metode matematice.

Abstractizarea structurilor de control

Calculul leneș oferă un nivel atât de ridicat de abstractizare încât devin posibile lucruri uimitoare. De exemplu, imaginați-vă că implementați următoarea structură de control:

Cu excepția cazului în care(stocul.isEuropean()) (trimite laSEC(stoc); )
Dorim ca funcția sendToSEC să fie executată doar dacă stocul nu este european. Cum poți implementa dacă nu? Fără o evaluare leneșă, am avea nevoie de un sistem macro, dar în limbi precum Haskell acest lucru nu este necesar. Putem declara dacă nu ca funcție!

Nulă decât dacă(condiție booleană, cod Listă) (codul dacă(!condiție); )
Rețineți că codul nu va fi executat dacă condiția == true . În limbile stricte, acest comportament nu poate fi repetat deoarece argumentele vor fi evaluate înainte, dacă nu sunt apelate.

Structuri infinite de date

Limbile leneșe vă permit să creați structuri de date infinite, care sunt mult mai dificil de creat în limbi stricte. - doar nu în Python]. De exemplu, imaginați-vă șirul lui Fibonacci. Evident, nu putem calcula o listă infinită într-un timp finit și totuși să o stocăm în memorie. În limbaje stricte precum Java, am scrie pur și simplu o funcție care returnează un membru arbitrar al secvenței. În limbi precum Haskell, putem abstrage și pur și simplu declara o listă infinită de numere Fibonacci. Deoarece limbajul este leneș, vor fi calculate doar părțile necesare ale listei care sunt utilizate efectiv în program. Acest lucru vă permite să faceți abstracție dintr-un număr mare de probleme și să le priviți de la un nivel superior (de exemplu, puteți utiliza funcții pentru procesarea listelor pe secvențe infinite).

Defecte

Desigur, brânza gratuită vine doar într-o capcană pentru șoareci. Calculele leneși vin cu o serie de dezavantaje. Acestea sunt în principal neajunsuri ale lenei. În realitate, ordinea directă a calculelor este foarte des necesară. Luați de exemplu următorul cod:

Într-un limbaj leneș, nimeni nu garantează că prima linie va fi executată înainte de a doua! Aceasta înseamnă că nu putem face I/O, nu putem folosi funcțiile native în mod normal (la urma urmei, ele trebuie să fie apelate într-o anumită ordine pentru a lua în considerare efectele lor secundare) și nu putem interacționa cu exteriorul lume! Dacă introducem un mecanism de ordonare a execuției codului, vom pierde avantajul rigoarei matematice a codului (și atunci vom pierde toate beneficiile programării funcționale). Din fericire, nu totul este pierdut. Matematicienii s-au pus pe treabă și au venit cu mai multe tehnici pentru a se asigura că instrucțiunile au fost executate în ordinea corectă, fără a pierde spiritul funcțional. Avem ce este mai bun din ambele lumi! Astfel de tehnici includ continuări, monade și scrierea unicității. În acest articol vom lucra cu continuări și vom lăsa monade și tastarea fără ambiguitate până data viitoare. Este interesant că continuările sunt un lucru foarte util, care este folosit nu numai pentru a specifica o ordine strictă a calculelor. Vom vorbi și despre asta.

Continuări

Continuările în programare joacă același rol ca Codul lui Da Vinci în istoria omenirii: o revelație surprinzătoare a celui mai mare mister al umanității. Ei bine, poate nu chiar așa, dar cu siguranță rup copertele, așa cum ați învățat să luați rădăcina lui -1 în timpul zilei.

Când ne-am uitat la funcții, am aflat doar jumătate din adevăr, deoarece am presupus că o funcție returnează o valoare funcției care o apelează. În acest sens, continuarea este o generalizare a funcțiilor. O funcție nu trebuie să returneze controlul în locul din care a fost apelată, dar poate reveni în orice loc din program. „Continuare” este un parametru pe care îl putem transmite unei funcții pentru a indica un punct de întoarcere. Sună mult mai înfricoșător decât este de fapt. Să aruncăm o privire la următorul cod:

Int i = add(5, 10); int j = pătrat(i);
Funcția de adăugare returnează numărul 15, care este scris în i în locația în care a fost apelată funcția. Valoarea lui i este folosită atunci când se apelează la pătrat. Rețineți că un compilator leneș nu poate schimba ordinea calculelor, deoarece a doua linie depinde de rezultatul primei. Putem rescrie acest cod folosind un stil de trecere de continuare (CPS), unde add returnează o valoare funcției pătrate.

Int j = add(5, 10, square);
În acest caz, add primește un argument suplimentar - o funcție care va fi apelată după ce add se termină de rulat. În ambele exemple, j va fi egal cu 225.

Aceasta este prima tehnică care vă permite să specificați ordinea în care sunt executate două expresii. Să revenim la exemplul nostru I/O.

System.out.println("Vă rugăm să introduceți numele dvs.: "); System.in.readLine();
Aceste două linii sunt independente una de cealaltă, iar compilatorul este liber să-și schimbe ordinea după cum dorește. Dar dacă îl rescriem în CPS, vom adăuga astfel dependența necesară, iar compilatorul va trebui să efectueze calcule unul după altul!

System.out.println("Vă rugăm să introduceți numele dvs.: ", System.in.readLine);
În acest caz, println ar trebui să apeleze readLine , trecându-i rezultatul și să returneze rezultatul readLine la sfârșit. În această formă, putem fi siguri că aceste funcții vor fi apelate pe rând și că readLine va fi apelată deloc (la urma urmei, compilatorul se așteaptă să primească rezultatul ultimei operații). În cazul Java, println returnează void. Dar dacă ar fi returnată o valoare abstractă (care ar putea servi drept argument pentru readLine), asta ar rezolva problema noastră! Desigur, construirea unor astfel de lanțuri de funcții afectează foarte mult lizibilitatea codului, dar acest lucru poate fi rezolvat. Putem adăuga în limbajul nostru caracteristici sintactice care ne vor permite să scriem expresii ca de obicei, iar compilatorul va înlănțui automat calculele. Acum putem efectua calcule în orice ordine fără a pierde avantajele FP (inclusiv capacitatea de a studia programul folosind metode matematice)! Dacă acest lucru este confuz, amintiți-vă că funcțiile sunt doar instanțe ale unei clase cu un singur membru. Rescrieți exemplul nostru astfel încât println și readLine să fie instanțe ale claselor, acest lucru vă va face mai clar.

Dar beneficiile sequelelor nu se termină aici. Putem scrie întregul program folosind CPS, astfel încât fiecare funcție să fie apelată cu un parametru suplimentar, o continuare, la care se trece rezultatul. În principiu, orice program poate fi tradus în CPS dacă fiecare funcție este tratată ca un caz special de continuare. Această conversie se poate face automat (de fapt, mulți compilatori fac acest lucru).

De îndată ce convertim programul în formă CPS, devine clar că fiecare instrucțiune are o continuare, funcție căreia i se va trece rezultatul, care într-un program normal ar fi punctul de apel. Să luăm orice instrucțiune din ultimul exemplu, de exemplu add(5,10) . Într-un program scris în formă CPS, este clar care va fi continuarea - aceasta este funcția pe care add o va apela la finalizarea lucrării. Dar care va fi continuarea în cazul unui program non-CPS? Desigur, putem converti programul în CPS, dar este necesar?

Se pare că acest lucru nu este necesar. Aruncă o privire atentă la conversia noastră CPS. Dacă începeți să scrieți un compilator pentru acesta, veți descoperi că versiunea CPS nu are nevoie de o stivă! Funcțiile nu returnează niciodată nimic, în sensul tradițional al cuvântului „întoarcere”, ele numesc pur și simplu o altă funcție, înlocuind rezultatul calculului. Nu este nevoie să introduceți argumente în stivă înainte de fiecare apel și apoi să le faceți înapoi. Putem stoca pur și simplu argumentele într-o locație de memorie fixă ​​și să folosim jump în loc de un apel normal. Nu trebuie să stocăm argumentele originale, pentru că nu vor mai fi necesare niciodată, deoarece funcțiile nu returnează nimic!

Astfel, programele în stil CPS nu au nevoie de stivă, ci conțin un argument suplimentar, sub forma unei funcții, pentru a fi apelat. Programele în stil non-CPS nu au un argument suplimentar, dar folosesc o stivă. Ce este stocat pe stivă? Doar argumente și un pointer către locația de memorie unde ar trebui să revină funcția. Ei bine, ai ghicit deja? Stiva stochează informații despre continuări! Un pointer către un punct de întoarcere pe stivă este același cu funcția care trebuie apelată în programele CPS! Pentru a afla care este continuarea lui add(5,10), trebuie doar să luați punctul de întoarcere din stivă.

Nu a fost greu. O continuare și un pointer către un punct de întoarcere sunt de fapt același lucru, doar continuarea este specificată în mod explicit și, prin urmare, poate diferi de locul în care a fost apelată funcția. Dacă vă amintiți că o continuare este o funcție, iar o funcție în limba noastră este compilată într-o instanță a unei clase, atunci veți înțelege că un pointer către un punct de întoarcere din stivă și un pointer către o continuare sunt de fapt același lucru , deoarece funcția noastră (ca o instanță a unei clase) este doar un pointer. Aceasta înseamnă că în orice moment al programului dumneavoastră puteți solicita continuarea curentă (în esență informații din stivă).

Bine, acum înțelegem care este continuarea curentă. Ce înseamnă? Dacă luăm continuarea curentă și o salvăm undeva, salvăm astfel starea curentă a programului - o înghețăm. Acesta este similar cu modul de hibernare a sistemului de operare. Obiectul de continuare stochează informațiile necesare pentru a relua execuția programului din punctul în care a fost solicitat obiectul de continuare. Sistemul de operare face acest lucru programelor dvs. tot timpul când schimbă contextul între fire. Singura diferență este că totul este sub controlul sistemului de operare. Dacă solicitați un obiect de continuare (în Scheme acest lucru se face apelând funcția call-with-current-continuation), atunci veți primi un obiect cu continuarea curentă - stiva (sau în cazul CPS, următoarea funcție de apelare ). Puteți salva acest obiect pe o variabilă (sau chiar pe disc). Dacă decideți să „reporniți” programul cu această continuare, atunci starea programului dumneavoastră este „transformată” în starea la momentul în care obiectul de continuare a fost preluat. Este același lucru cu trecerea la un fir suspendat sau cu trezirea sistemului de operare după hibernare. Cu excepția că puteți face acest lucru de mai multe ori la rând. După ce sistemul de operare se trezește, informațiile de hibernare sunt distruse. Dacă acest lucru nu s-a făcut, atunci ar fi posibil să se restabilească starea sistemului de operare din același punct. Este aproape ca și cum ai călători în timp. Cu sequelele îți poți permite!

În ce situații vor fi utile continuarea? De obicei, dacă încercați să emulați starea în sisteme care sunt în mod inerent lipsite de stare. O utilizare excelentă pentru continuare a fost găsită în aplicațiile Web (de exemplu, în cadrul Seaside pentru limbajul Smalltalk). ASP.NET de la Microsoft face tot posibilul pentru a salva starea dintre solicitări pentru a vă ușura viața. Dacă C# acceptă continuări, complexitatea ASP.NET ar putea fi redusă la jumătate prin simpla salvare a continuării și restabilirea acesteia la următoarea solicitare. Din punctul de vedere al unui programator Web, nu ar exista o singură pauză - programul și-ar continua munca de la următoarea linie! Continuările sunt o abstractizare incredibil de utilă pentru rezolvarea unor probleme. Cu tot mai mulți clienți tradiționali care se mută pe Web, importanța continuărilor va crește doar în timp.

Potrivire de model

Potrivirea modelelor nu este o idee atât de nouă sau inovatoare. De fapt, are puțină legătură cu programarea funcțională. Singurul motiv pentru care este adesea asociat cu FP este că de ceva timp limbile funcționale au potrivire de modele, dar limbajele imperative nu.

Să începem introducerea noastră în potrivirea modelelor cu următorul exemplu. Iată o funcție pentru calcularea numerelor Fibonacci în Java:

Int fib(int n) ( dacă (n == 0) returnează 1; dacă (n == 1) returnează 1; returnează fib(n - 2) + fib (n - 1); )
Și iată un exemplu într-un limbaj asemănător Java cu suport pentru potrivirea modelelor

Int fib(0) ( return 1; ) int fib(1) ( return 1; ) int fib(int n) ( return fib(n - 2) + fib(n - 1); )
Care este diferența? Compilatorul implementează ramificarea pentru noi.

Gândește-te, este foarte important! Chiar nu este atât de important. Sa observat că un număr mare de funcții conțin structuri de comutare complexe (acest lucru este parțial adevărat pentru programele funcționale) și s-a decis să evidențiem acest punct. Definiția funcției este împărțită în mai multe variante și se stabilește un model în locul argumentelor funcției (aceasta amintește de supraîncărcarea metodei). Când are loc un apel de funcție, compilatorul compară argumentele cu toate definițiile din mers și o selectează pe cea mai potrivită. De obicei, alegerea cade pe cea mai specializată definiție a funcției. De exemplu, int fib(int n) poate fi apelat când n este 1, dar nu va fi, deoarece int fib(1) este o definiție mai specializată.

Potrivirea modelelor pare de obicei mai complicată decât în ​​exemplul nostru. De exemplu, un sistem complex de potrivire a modelelor vă permite să scrieți următorul cod:

Int f(int n< 10) { ... } int f(int n) { ... }
Când este utilă potrivirea modelelor? Lista acestor cazuri este surprinzător de lungă! De fiecare dată când utilizați constructe complexe imbricate if, potrivirea modelelor poate face o treabă mai bună cu mai puțin cod. Un bun exemplu care îmi vine în minte este funcția WndProc, care este implementată în fiecare program Win32 (chiar dacă este ascunsă de programator în spatele unui gard înalt de abstracții). De obicei, potrivirea modelelor poate verifica chiar și conținutul colecțiilor. De exemplu, dacă treceți o matrice unei funcții, atunci puteți selecta toate matricele al căror prim element este egal cu 1 și al căror al treilea element este mai mare de 3.

Un alt avantaj al potrivirii modelelor este că, dacă faceți modificări, nu va trebui să căutați o singură funcție uriașă. Tot ce trebuie să faceți este să adăugați (sau să modificați) unele definiții ale funcției. Astfel, scăpăm de un întreg strat de modele din celebra carte a Gang of Four. Cu cât condițiile sunt mai complexe și mai ramificate, cu atât va fi mai util să folosiți potrivirea modelelor. Odată ce începi să le folosești, te vei întreba cum te-ai descurcat vreodată fără ele.

Închideri

Până acum, am discutat despre caracteristicile FP în contextul limbajelor „pur” funcționale - limbaje care sunt implementări ale calculului lambda și nu conțin caracteristici care contrazic sistemul formal al Bisericii. Cu toate acestea, multe caracteristici ale limbajelor funcționale sunt utilizate în afara calculului lambda. Deși implementarea unui sistem axiomatic este interesantă din punct de vedere al programării din punct de vedere al expresiilor matematice, aceasta poate să nu fie întotdeauna aplicabilă în practică. Multe limbi preferă să folosească elemente ale limbilor funcționale fără a adera la o doctrină funcțională strictă. Unele astfel de limbi (de exemplu Common Lisp) nu necesită ca variabilele să fie definitive - valorile acestora pot fi modificate. Nici măcar nu necesită ca funcțiile să depindă doar de argumentele lor - funcțiilor li se permite să acceseze starea în afara domeniului lor. Dar, în același timp, includ caracteristici precum funcții de ordin superior. Transmiterea funcției într-un limbaj non-pur este puțin diferită de operația echivalentă din calculul lambda și necesită o caracteristică interesantă numită închidere lexicală. Să aruncăm o privire la următorul exemplu. Rețineți că, în acest caz, variabilele nu sunt finale și funcția poate accesa variabile în afara domeniului său de aplicare:

Funcția makePowerFn(int putere) ( int powerFn(int bază) ( return pow(bază, putere); ) return powerFn; ) Funcție pătrat = makePowerFn(2); pătrat(3); // returnează 9
Funcția make-power-fn returnează o funcție care ia un argument și îl ridică la o anumită putere. Ce se întâmplă când încercăm să evaluăm pătratul(3)? Puterea variabilă este în afara domeniului de aplicare a powerFn deoarece makePowerFn a fost deja finalizată și stiva sa a fost distrusă. Atunci cum funcționează pătratul? Limbajul trebuie să stocheze cumva sensul puterii pentru ca funcția pătrat să funcționeze. Ce se întâmplă dacă creăm o altă funcție cub care ridică un număr la a treia putere? Limbajul va trebui să stocheze două valori de putere pentru fiecare funcție creată în make-power-fn. Fenomenul de stocare a acestor valori se numește închidere. O închidere nu numai că păstrează argumentele funcției de sus. De exemplu, o închidere ar putea arăta astfel:

Funcția makeIncrementer() ( int n = 0; int increment() ( return ++n; ) ) Funcția inc1 = makeIncrementer(); Funcția inc2 = makeIncrementer(); inc1(); // returnează 1; inc1(); // returnează 2; inc1(); // returnează 3; inc2(); // returnează 1; inc2(); // returnează 2; inc2(); // returnează 3;
În timpul execuției, valorile lui n sunt stocate și contoarele au acces la ele. Mai mult, fiecare contor are propria sa copie a lui n, în ciuda faptului că ar fi trebuit să dispară după rularea funcției makeIncrementer. Cum reușește compilatorul să compileze asta? Ce se întâmplă în culisele închiderilor? Din fericire, avem un permis magic.

Totul se face destul de logic. La prima vedere, este clar că variabilele locale nu mai sunt supuse regulilor de aplicare și durata lor de viață este nedefinită. Evident, acestea nu mai sunt depozitate pe stivă - trebuie păstrate pe grămadă. Prin urmare, închiderea este făcută ca și funcția normală pe care am discutat mai devreme, cu excepția faptului că are o referință suplimentară la variabilele din jur:

Clasa some_function_t ( SymbolTable parentScope; // ... )
Dacă o închidere accesează o variabilă care nu se află în domeniul local, atunci ia în considerare domeniul părinte. Asta e tot! Închiderea conectează lumea funcțională cu lumea OOP. De fiecare dată când creați o clasă care stochează o anumită stare și o treceți undeva, amintiți-vă despre închideri. O închidere este doar un obiect care creează „atribute” din mers, scoțându-le din sfera de aplicare, astfel încât să nu fie nevoie să o faci singur.

Acum ce?

Acest articol atinge doar vârful aisbergului de programare funcțională. Poți să sapi mai adânc și să vezi ceva cu adevărat mare și, în cazul nostru, ceva bun. În viitor, intenționez să scriu despre teoria categoriilor, monade, structuri funcționale de date, sisteme de tip în limbaje funcționale, multithreading funcțional, baze de date funcționale și multe altele. Dacă pot să scriu (și să studiez în acest proces) chiar și jumătate din aceste subiecte, viața mea nu va fi în zadar. Între timp, Google- prietenul tău credincios.

Dacă sunteți un dezvoltator ca mine, probabil că ați studiat mai întâi paradigma OOP. Primul tău limbaj a fost Java sau C++ - sau, dacă ai noroc, Ruby, Python sau C# - așa că probabil știi ce sunt clase, obiecte, instanțe etc. Ceea ce cu siguranță nu înțelegeți prea multe sunt elementele de bază ale acelei paradigme ciudate numite programare funcțională, care diferă semnificativ nu numai de OOP, ci și de programare procedurală, orientată pe prototip și alte tipuri de programare.

Programarea funcțională devine populară - și din motive întemeiate. Paradigma în sine nu este nouă: Haskell este poate cel mai funcțional limbaj și a apărut în anii 90. Limbi precum Erlang, Scala, Clojure se încadrează și ele sub definiția funcționalului. Unul dintre principalele avantaje ale programării funcționale este abilitatea de a scrie programe care funcționează concomitent (dacă ați uitat deja ce este, reîmprospătați-vă memoria citind) și fără erori - adică blocările reciproce și siguranța firelor nu vă vor deranja. .

Programarea funcțională are multe avantaje, dar capacitatea de a maximiza resursele CPU prin comportamentul concurent este principalul său avantaj. Mai jos ne vom uita la principiile de bază ale programării funcționale.

Introducere: Toate aceste principii sunt opționale (multe limbi nu le respectă pe deplin). Toate sunt teoretice și sunt necesare pentru definirea cât mai exactă a paradigmei funcționale.

1. Toate funcțiile sunt curate

Această regulă este cu siguranță fundamentală în programarea funcțională. Toate funcțiile sunt pure dacă îndeplinesc două condiții:

1. O funcție apelată cu aceleași argumente returnează întotdeauna aceeași valoare.
2. Nu apar efecte secundare în timpul execuției funcției.

Prima regulă este clară - dacă apelez la funcția sum(2, 3), mă aștept ca rezultatul să fie întotdeauna 5. De îndată ce apelați funcția rand() sau accesați o variabilă care nu este definită în funcție, puritatea funcției este încălcată, iar acest lucru nu este permis în programarea funcțională.

A doua regulă - fără efecte secundare - este de natură mai largă. Un efect secundar este o modificare a altceva decât funcția care se execută în prezent. Schimbarea unei variabile în afara unei funcții, imprimarea pe consolă, aruncarea unei excepții, citirea datelor dintr-un fișier - toate acestea sunt exemple de efecte secundare care privează funcția de puritatea sa. Aceasta poate părea o limitare majoră, dar gândiți-vă din nou. Dacă sunteți sigur că apelarea unei funcții nu va schimba nimic „din exterior”, atunci puteți utiliza această funcție în orice scenariu. Acest lucru deschide calea pentru programarea concomitentă și aplicațiile multi-threaded.

2. Toate funcțiile sunt de primă clasă și de ordin superior

Acest concept nu este o caracteristică a FP (este folosit în Javascript, PHP și alte limbi) - dar este o cerință obligatorie. De fapt, Wikipedia are un articol întreg dedicat funcțiilor de primă clasă. Pentru ca o funcție să fie de primă clasă, trebuie să poată fi declarată ca variabilă. Acest lucru permite ca funcția să fie tratată ca un tip de date normal și să fie în continuare executată.

3. Variabilele sunt imuabile

Totul este simplu aici. În programarea funcțională, nu puteți modifica o variabilă după ce a fost inițializată. Puteți crea altele noi, dar nu le puteți modifica pe cele existente - și datorită acestui lucru, puteți fi sigur că nicio variabilă nu se va schimba.

4. Transparența relativă a funcțiilor

Este dificil de dat o definiție corectă a transparenței relative. Cred că cel mai precis este acesta: dacă puteți înlocui un apel de funcție cu o valoare returnată, iar starea nu se schimbă, atunci funcția este relativ transparentă. Acest lucru poate fi evident, dar voi da un exemplu.

Să presupunem că avem o funcție Java care adaugă 3 și 5:

Public int addNumbers() ( returnează 3 + 5; ) addNumbers() // 8 8 // 8

Evident, orice apel la această funcție poate fi înlocuit cu 8 - ceea ce înseamnă că funcția este relativ transparentă. Iată un exemplu de funcție opace:

Public void printText())( System.out.println("Hello World"); ) printText() // Nu returnează nimic, dar afișează "Hello World"

Această funcție nu returnează nimic, dar tipărește text, iar dacă înlocuiți apelul funcției cu nimic, starea consolei va fi diferită - ceea ce înseamnă că funcția nu este relativ transparentă.

5. Programarea funcțională se bazează pe calculul lambda

Programarea funcțională se bazează în mare măsură pe un sistem matematic numit calcul lambda. Nu sunt matematician, așa că nu voi intra în detalii - dar vreau să atrag atenția asupra două principii cheie ale calculului lambda care formează însuși conceptul de programare funcțională:

1. În calculul lambda, toate funcțiile pot fi anonime, deoarece singura parte semnificativă a antetului funcției este lista de argumente.
2. Când sunt apelate, toate funcțiile trec printr-un proces de curry. Este în felul următor: dacă este apelată o funcție cu mai multe argumente, atunci la început va fi executată doar cu primul argument și va returna o nouă funcție care conține 1 argument mai puțin, care va fi apelată imediat. Acest proces este recursiv și continuă până când toate argumentele au fost aplicate, returnând rezultatul final. Deoarece funcțiile sunt pure, aceasta funcționează.

După cum am spus, calculul lambda nu se termină aici - dar am acoperit doar aspectele cheie legate de FP. Acum, într-o conversație despre programarea funcțională, puteți arunca cuvântul „calcul lambda” și toată lumea va crede că vă încurcați :)