Ce este programarea funcțională. O abordare a calculării argumentelor. Sintaxă în două minute

Programarea funcțională combină diferite abordări pentru definirea proceselor de calcul bazate pe concepte abstracte destul de stricte și metode de prelucrare a datelor simbolice.

O caracteristică a limbajelor de programare funcționale este că textele programelor în limbaje de programare funcționale descriu „cum se rezolvă o problemă”, dar nu prescriu o secvență de acțiuni pentru rezolvarea acesteia. Principalele proprietăți ale limbajelor de programare funcționale: concizie, simplitate, tastare puternică, modularitate, prezența calculelor leneșe.

Limbajele de programare funcționale includ: Lisp, Miranda, Gofel, ML, Standard ML, Objective CAML, F#, Scala, Pythagoras etc.

Limbaje de programare procedurale

Un limbaj de programare procedural permite programatorului să definească fiecare pas în procesul de rezolvare a unei probleme. Particularitatea unor astfel de limbaje de programare este că sarcinile sunt împărțite în pași și rezolvate pas cu pas. Folosind un limbaj procedural, programatorul definește constructe de limbaj pentru a efectua o secvență de pași algoritmici.

Limbaje de programare procedurale: Ada, Basic, C, COBOL, Pascal, PL/1, Rapier etc.

Stiva limbaje de programare

Un limbaj de programare stivă este un limbaj de programare care utilizează modelul stivă de mașini pentru a transmite parametri. Limbaje de programare bazate pe stivă: Forth, PostScript, Java, C# etc. Când utilizați stiva ca canal principal pentru transferul parametrilor între cuvinte, elementele de limbaj formează în mod natural fraze (înlănțuire secvențială). Această proprietate aduce aceste limbi mai aproape de limbile naturale.

Limbaje de programare orientate pe aspecte 5) Limbaje de programare declarative 6) Limbaje de programare dinamice 7) Limbi educaționale programare 8) Limbaje de descriere a interfeței 9) Limbaje de programare prototip 10) Limbaje de programare orientate pe obiecte 11) Limbaje de programare logice 12) Limbaje de programare scripting 13) Limbaje de programare ezoterice

Standardizarea limbajelor de programare. Paradigma de programare

Conceptul de limbaj de programare este indisolubil legat de implementarea sa. Pentru a se asigura că compilarea aceluiași program de către diferiți compilatori dă întotdeauna același rezultat, sunt dezvoltate standarde de limbaj de programare. Organizații implicate în probleme de standardizare: American National Standards Institute ANSI, Institute of Electrical and Electronics Engineers IEEE, ISO International Standards Organization.

Când o limbă este creată, este lansat un standard privat, determinat de dezvoltatorii limbii. Dacă o limbă devine răspândită, atunci în timp versiuni diferite compilatoare care nu respectă strict un standard privat. În cele mai multe cazuri, există o extindere a capabilităților fixate inițial ale limbii. Un standard de consens este în curs de dezvoltare pentru a aduce cele mai populare implementări ale limbajului în conformitate unele cu altele. Foarte factor important Standardizarea unui limbaj de programare este oportunitatea apariției standardului - înainte de distribuirea pe scară largă a limbajului și crearea multor implementări incompatibile. În procesul dezvoltării limbajului, pot apărea noi standarde, reflectând inovațiile moderne.

Paradigme de programare

Paradigmă- un set de teorii, standarde și metode care împreună reprezintă un mod de organizare a cunoștințelor științifice - cu alte cuvinte, un mod de a vedea lumea. Prin analogie, este general acceptat că o paradigmă în programare este o modalitate de conceptualizare care definește modul în care trebuie efectuate calculele și modul în care ar trebui să fie structurată și organizată munca efectuată de un computer.

Există mai multe paradigme de programare de bază, dintre care cele mai importante sunt acest moment timpul sunt paradigmele programării directive, orientate pe obiecte și funcțional-logic. Pentru a sprijini programarea în conformitate cu o anumită paradigmă, au fost dezvoltate limbaje algoritmice speciale.

C și Pascal sunt exemple de limbaje concepute pentru programarea prescriptivă, în care dezvoltatorul de program utilizează un model orientat pe proces, adică încearcă să creeze cod care funcționează pe date în mod corespunzător. În această abordare, principiul activ este considerat a fi un program (cod) care trebuie să efectueze toate acțiunile necesare asupra datelor pasive pentru a obține rezultatul dorit.

Tehnologia de programare ca proces de dezvoltare a produselor software create ca un întreg inextricabil sub formă de programe bine testate și materiale didactice, descriind scopul și utilizarea acestora.

Programare- procesul de creație programe de calculator. În mai mult în sens larg: gamă de activități asociate cu crearea și întreținerea muncii. starea programelor – software de calculator.

Tehnologia de programare- un set de metode și instrumente utilizate în procesul de dezvoltare software.

Tehnologia de programare este un set de instrucțiuni tehnologice, inclusiv:

· indicarea succesiunii operaţiilor tehnologice;

· enumerarea condițiilor în care se realizează cutare sau cutare operațiune;

· descrieri ale operațiunilor în sine, unde pentru fiecare operație sunt definite datele inițiale, rezultatele, precum și instrucțiunile, regulamentele, standardele, criteriile etc.

Tehnologia modernă de programare - abordarea componentelor, care implică construirea de software din componente individuale - bucăți de software separate fizic care interacționează între ele prin interfețe binare standardizate. În prezent criterii de calitate un produs software este considerat a fi: − funcţionalitate; − fiabilitate;− ușurință în utilizare;− eficienţă(raportul dintre nivelul serviciilor oferite de un produs software unui utilizator în condiții date și volumul resurselor utilizate); mentenabilitatea(caracteristicile unui produs software care permit reducerea la minimum a eforturilor de a face modificări pentru a elimina erorile din acesta și pentru a-l modifica în conformitate cu nevoile în schimbare ale utilizatorilor); mobilitate(capacitatea unui sistem software de a fi transferat dintr-un mediu în altul, în special, de la un computer la altul).

O etapă importantă crearea unui produs software. testare și depanare.

Depanare− aceasta este o activitate care vizează detectarea și corectarea erorilor dintr-un produs software folosind procesele de executare a programelor acestuia.

Testare− este procesul de executare a programelor sale pe un anumit set de date, pentru care rezultatul aplicării este cunoscut în prealabil sau sunt cunoscute regulile de comportare ale acestor programe.

Există următoarele metode de testare PS:

1) Testarea statică - testarea manuală a programului la masă.

2) Testare deterministă – cu diverse combinații de date sursă.

3) Stochastic – ref. Datele sunt selectate aleatoriu, iar rezultatul este determinat de calitatea rezultatelor sau de o estimare aproximativă.

Stiluri de programare.

Un stil de programare este un set de tehnici sau metode de programare pe care programatorii le folosesc pentru a produce programe care sunt corecte, eficiente, ușor de utilizat și ușor de citit.

Există mai multe stiluri de programare:

Programare procedurală este programarea în care un program este o succesiune de instrucțiuni. Folosit în limbi de nivel înalt Basic, Fortran etc.
Programare functionala este programarea în care un program este o secvență de apeluri de funcții. Folosit în Lisp și în alte limbi.
Programare logica – aceasta este programarea în care programul este un set de determinare a relațiilor dintre obiecte. Folosit în Prolog și în alte limbi.

Programare orientată pe obiecte– aceasta este programarea în care baza programului este un obiect care este o colecție de date și reguli pentru transformarea lor. Folosit in Limbi Turbo-Pascal, C++ etc.

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, obținem î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 modifica datele atunci când le utilizați în locuri diferite x al programului 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ă 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 cu privire la apelarea funcțiilor În ordinea corectă, nici despre formarea corectă starea externă. 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ă cele mai largi oportunități 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 schemei de limbaj funcțional, unul dintre dialectele Lisp, au apreciat atât de mult importanța recursiunii cozii încât în specificația limbii au prescris fiecărui traducător al acestei limbi să obligatoriu implementați 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ții de ordin superior sunt numite funcționale, deși acest lucru nu este în întregime adevărat; un echivalent mai precis este un operator.

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

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. Există posibilitatea unei scurgeri 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ă, așa credeam ș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 cod 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 ați reprodus eroarea, găsiți sursa acesteia - sarcină banală. 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! 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ă nicio modificare. 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 fire diferite. Acest lucru î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 limbajele de programare funcționale sunt 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 fiabile ca sisteme 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 îndeplinește cerințele Mâine. Dezvoltatorii de hardware nu mai pot face CPU să funcționeze mai repede. În schimb, cresc numărul de nuclee și pretind o creștere de patru ori a vitezei de calcul cu mai multe fire. Desigur, ei uită să spună la timp că dvs procesor nou va prezenta o creștere doar a programelor dezvoltate ținând cont de paralelizare. 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 pentru a instala Actualizări Windows A trebuit să repornesc computerul. 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ă (azi am lansat Windows Update la serviciu și acum mementoul enervant nu mă va lăsa în pace până când nu repornesc). ÎN sisteme Unix modelul de actualizare a fost 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. Baze de date relaționale datele au fost supuse unor 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 esențiale. Dacă dezvoltările dvs. nu sunt în domeniul aplicațiilor critice, atunci instrumentele verificare automată vă va oferi în continuare un avantaj gigantic față de concurenții dvs.

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 de caractere. 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 în functie separata(Din fericire, școlile încă învață cum să facă asta). 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ă căi diferiteși îl transferă pe 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, în funcție de aceasta, să setăm codul corect client. 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. Obiect abordare orientată 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 niciunul limbaj specific programare, iar modelele 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 Facade? Se pare că cineva trebuie 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 tehnică interesantă ceea ce devine posibil odată ce ai stăpânit 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ți 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, chiar aranja codul în așa fel încât să reducă numărul a erorilor asigurând în același timp integritatea programului. Exact asta mare avantaj atunci când descrie un 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()) ( trimitToSEC(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ă, cu excepția cazului în care (condiție booleană, cod Listă) ( dacă (! condiție) cod; )
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ță smulg 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 ultima operatie). Î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 forma CPS, devine clar că fiecare instrucțiune are o continuare, o funcție căreia i se va trece rezultatul, care în program regulat ar fi un punct de provocare. 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 adăugarea 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 acest lucru?

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 pur și simplu să stocăm argumentele într-o locație fixă de memorie și să folosim jump în schimb apel obișnuit. 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), este suficient să luăm 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. sistem 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ă” la 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 faptului că poți face asta 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 lucrul cu rândul următor! Continuările sunt o abstractizare incredibil de utilă pentru rezolvarea unor probleme. Cu tot mai mulți clienți grasi 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. S-a remarcat că un numar mare de funcțiile conțin constructe 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 Potrivirea 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ă transmiteț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, vei fi surprins 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. Ține minte că în în acest caz, variabilele nu sunt finale și o funcție 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ă. Deci, 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 în grămada. 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.

Întotdeauna mi-am dorit să scriu o serie de articole despre programarea funcțională pentru această revistă și mă bucur foarte mult că în sfârșit am avut ocazia. Chiar dacă seria mea despre analiza datelor este încă departe de a fi încheiată :). Nu voi anunța conținutul întregii serii, voi spune doar că astăzi vom vorbi despre diferite limbaje de programare care suportă stilul funcțional și tehnicile de programare corespunzătoare.

Limbaje de programare pe care nu le cunoaște toată lumea

Am început să programez în copilărie, iar la vârsta de douăzeci și cinci de ani mi s-a părut că știu și înțeleg totul. Programarea orientată pe obiecte a devenit parte a creierului meu, fiecare carte imaginabilă despre programarea industrială a fost citită. Dar tot am avut senzația că am scăpat ceva, ceva foarte subtil și incredibil de important. Cert este că, ca mulți în anii nouăzeci, la școală am fost învățat să programez în Pascal (o da, glorie Turbo Pascal 5.5! - Ed.), apoi C și C++. La universitate, Fortran și apoi Java ca instrument principal la locul de muncă. Știam Python și alte câteva limbi, dar totul era greșit. Dar nu am avut o educație serioasă în domeniul Informaticii. Într-o zi, în timpul unui zbor peste Atlantic, nu am putut să dorm și am vrut să citesc ceva. Cumva, ca prin magie, aveam la îndemână o carte despre limbajul de programare Haskell. Mi se pare că atunci am înțeles adevăratul sens al expresiei „frumusețea necesită sacrificiu”.

Acum, când oamenii mă întreabă cum l-am învățat pe Haskell, spun asta: într-un avion. Acest episod mi-a schimbat atitudinea față de programare în general. Bineînțeles, după prima cunoaștere, multe lucruri mi s-au părut neclare. A trebuit să mă încordez și să studiez problema cu mai multă atenție. Și știi, au trecut zece ani, mulți elemente functionale a devenit parte a limbilor industriale, funcții lambda există deja chiar și în Java, inferență de tip- în C++, potrivire de model- la Scala. Mulți oameni cred că acesta este un fel de descoperire. Și în această serie de articole vă voi vorbi despre tehnicile de programare funcțională folosind limbi diferiteși trăsăturile lor.

Utilizatorii de internet alcătuiesc adesea tot felul de liste și topuri pentru amuzamentul publicului. De exemplu, „o listă de cărți pe care ar trebui să le citiți înainte de a împlini treizeci de ani”. Dacă mi s-ar da sarcina de a face o listă de cărți despre programare pe care ar trebui să le citești înainte de a fi mai în vârstă, atunci primul loc ar merge cu siguranță la cartea lui Abelson și Sussman. „Structura și interpretarea programelor de calculator”. Uneori chiar mi se pare că compilatorul sau interpretul orice limba ar trebui să oprească pe oricine nu a citit această carte.

Prin urmare, dacă există un limbaj cu care trebuie să începi să înveți programarea funcțională, acesta este Lisp. În general, aceasta este o întreagă familie de limbi, care include un limbaj acum destul de popular pentru JVM numit Clojure. Dar nu este deosebit de potrivit ca prim limbaj funcțional. Pentru aceasta este mai bine să folosiți limbajul Sistem, care a fost dezvoltat la MIT și până la mijlocul anilor 2000 a servit drept limbaj principal pentru predarea programării. Deși cursul introductiv cu același titlu ca și cartea menționată a fost acum înlocuit cu un curs despre Python, el încă nu și-a pierdut relevanța.

Voi încerca să vorbesc pe scurt despre limbajul Scheme și, în general, despre ideea din spatele limbilor acestui grup. În ciuda faptului că Lisp este foarte vechi (dintre toate limbajele de nivel înalt, doar Fortran este mai vechi), în el au devenit disponibile pentru prima dată multe metode de programare folosite astăzi. În cele ce urmează, voi folosi numele Lisp, adică o implementare specifică - Scheme.

Sintaxă în două minute

Sintaxa din Lisp este, hmm, puțin controversată. Cert este că ideea care stă la baza sintaxei este extrem de simplă și este construită pe baza așa-numitelor S-expresii. Aceasta este o notație de prefix în care expresia familiară 2 + 3 este scrisă ca (+ 2 3) . Acest lucru poate părea ciudat, dar în practică oferă ceva caracteristici suplimentare. Apropo, funcționează și (+ 2 10 (* 3.14 2)) :). Astfel, întregul program este o colecție de liste care folosesc notația de prefix. În cazul limbajului Lisp, programul în sine și arborele de sintaxă abstractă - „dacă știi ce vreau să spun” 😉 - nu sunt în esență diferite. Un astfel de record face analizare Programele Lisp sunt foarte simple.
Deoarece vorbim despre un limbaj de programare, ar trebui să vorbim despre cum să definim funcțiile în acest limbaj.

Aici trebuie să facem o mică digresiune. Există o subtilitate, a cărei semnificație este subestimată în literatura modernă. Este încă necesar să separăm o funcție în sens matematic și o funcție așa cum o înțelegem în programarea funcțională. Cert este că, în matematică, funcțiile sunt obiecte declarative, iar în programare sunt folosite pentru a organiza procesul de calcul, adică, într-un sens, ele reprezintă mai degrabă cunoștințe imperative, cunoștințe care răspunde la întrebarea „cum?” Acesta este motivul pentru care Abelson și Sussman în cartea lor separă foarte atent acest lucru și apelează funcții în procedurile de programare. Acest lucru nu este acceptat în literatura modernă de programare funcțională. Dar totuși recomand cu tărie să separați aceste două sensuri ale cuvântului „funcție” cel puțin în capul vostru.

Cel mai simplu mod de a defini o funcție este să scrieți următorul cod. Să începem cu ceva indecent de simplu:

(definiți (rădăcini pătrate a b c) (fie ((D (- (* b b) (* 4 a c)))) (dacă (< D 0) (list) (let ((sqrtD (sqrt D))) (let ((x1 (/ (- (- b) sqrtD) (* 2.0 a))) (x2 (/ (+ (- b) sqrtD) (* 2.0 a)))) (list x1 x2))))))

Da, este exact ceea ce ați crezut - rezolvarea unei ecuații pătratice în Scheme. Dar acest lucru este mai mult decât suficient pentru a vedea toate caracteristicile sintaxei. Aici sq-roots este numele funcției din trei parametri formali.

La prima vedere, constructul let, care este folosit pentru a defini variabilele locale, are prea multe paranteze. Dar acest lucru nu este adevărat, pur și simplu definim mai întâi o listă de variabile și apoi o expresie în care sunt utilizate aceste variabile. Aici (lista) este o listă goală pe care o returnăm când nu există rădăcini și (lista x1 x2) este o listă de două valori.

Acum despre expresii. În funcția noastră sq-roots am folosit un construct if. Aici intervine programarea funcțională.

Ideea este că, spre deosebire de limbajele imperative precum C, în limbajele funcționale dacă este o expresie, nu o declarație. În practică, aceasta înseamnă că nu poate avea o altă ramură. Pentru că o expresie trebuie să aibă întotdeauna un sens.

Nu poți vorbi despre sintaxă fără să vorbești despre zahăr sintactic. În limbajele de programare, zahărul sintactic se referă la constructe care nu sunt necesare, ci doar fac codul mai ușor de citit și reutilizat. Pentru început, să dăm un exemplu clasic din limbajul C Mulți oameni știu că tablourile nu sunt un mijloc de exprimare necesar, deoarece există pointeri. Da, într-adevăr, tablourile sunt implementate prin pointeri, iar a[i] pentru limbajul C este același cu *(a + i) . Acest exempluîn general destul de neobișnuit, are asociat un efect amuzant: deoarece operația de adunare rămâne comutativă în cazul pointerilor, ultima expresie este aceeași cu *(i + a) , iar aceasta se poate obține prin eliminarea zahărului sintactic din expresia i [a] ! Operația de îndepărtare a zahărului sintactic în Limba engleză numit un cuvânt special dezahărarea.

Revenind la limbajul Scheme, ar trebui să aducem exemplu important zahăr sintactic. Pentru a defini variabile, ca în cazul funcțiilor, folosiți cuvânt cheie(în Lisp și Scheme acest lucru se numește formă specială) defini . De exemplu, (definiți pi 3.14159) definește variabila pi. În general, puteți defini funcțiile exact în același mod:

(definiți pătratul (lambda (x) (* x x)))

este la fel ca

(definiți (pătrat x) (* x x))

Ultima linie pare puțin mai ușor de citit în comparație cu versiunea care folosește o expresie lambda. Cu toate acestea, este clar că este suficient să aveți prima variantă, iar a doua este opțională. De ce este primul mai important? Pentru că una dintre cele mai multe proprietăți de bază limbaje funcționale - care funcționează în ele sunt obiecte de primă clasă. Acesta din urmă înseamnă că funcțiile pot fi transmise ca argument și returnate ca valoare.

Dacă te uiți la let din punctul de vedere al unei expresii lambda, poți observa cu ușurință următoarea corespondență:

(permite ((x 5) (y 2)) (* x y)) (se aplică (lambda (x y) (* x y)) (lista 5 2))

Programare functionala

Există limbaje funcționale curatȘi necurat. Limbile funcționale pure sunt relativ rare, ele includ în primul rând HaskellȘi Curat. Limbile pure nu au efecte secundare. În practică, aceasta înseamnă că nu există nicio alocare sau I/O așa cum suntem obișnuiți. Acest lucru creează o serie de dificultăți, deși în limbile menționate deja acest lucru este rezolvat destul de inteligent, iar în aceste limbi ei scriu cod cu o cantitate mare I/O Limbi precum Lisp, OCaml sau Scala permit funcții cu efecte secundare, iar în acest sens aceste limbaje sunt adesea mai practice.

Sarcina noastră este să învățăm tehnicile de bază ale programării funcționale în Scheme. Prin urmare, vom scrie cod pur funcțional, fără a folosi un generator numere aleatorii, I/O și setați! , care vă va permite să modificați valorile variabilelor. Puteți citi despre toate acestea în carte SICP. Acum să ne concentrăm asupra celor mai importante pentru noi.

Primul lucru care derutează un începător despre programarea funcțională este lipsa buclelor. Dar ce ar trebui să facem? Mulți dintre noi suntem învățați că recursiunea este rea. Acest lucru este argumentat de faptul că recursiunea în limbajele de programare convenționale este de obicei implementată ineficient. Ideea este că în caz general Ar trebui să distingem între recursivitate ca tehnică tehnică, adică apelarea unei funcții din ea însăși, și recursivitate ca proces. Limbajele funcționale acceptă optimizarea recursiunii cozii sau, așa cum se numește uneori, recursiunea acumulatorului. Acest lucru poate fi ilustrat cu un exemplu simplu.

Să presupunem că avem două funcții - succ și prev. Primul returnează un număr cu 1 mai mare decât argumentul, iar al doilea returnează cu 1 mai puțin. Acum să încercăm să definim operația de adăugare în două moduri:

(definiți (adăugați x y) (dacă (echivalentul? y 0) x (adăugați (succ x) (anterior y)))) (definiți (adăugați-1 x y) (dacă (echivalentul? y 0) x (succ (adăugați- 1 x (anterior)))))

Care este diferența dintre primul și al doilea caz? Faptul este că dacă luăm în considerare metoda de calcul pentru primul caz pas cu pas, putem vedea următoarele:

(adăugați 3 4) => (adăugați 4 3) => (adăugați 5 2) => (adăugați 6 1) => (adăugați 7 0) => 7

În al doilea caz vom avea ceva de genul:

(add-1 3 4) => (succ (adăugare-1 3 3)) => (succ (succ (adăugare-1 3 2)))) => (succ (succ (succ (adăugare-1 3 1))) )) => (succ (succ (succ (succ (succ (adăugați-1 3 0))))) => (succ (succ (succ (succ (succ 3)))) => (succ (succ (succ (succ 4)))) => (succ (succ 5)) => (succ 6) => 7

În ciuda faptului că în ambele cazuri rezultatul este același, procesul de calcul este radical diferit. În primul caz, cantitatea de memorie utilizată nu se modifică, dar în al doilea crește liniar. Primul proces este iterativși al doilea - recursiv. Da, pentru scris programe eficienteÎn limbajele funcționale, trebuie să utilizați recursiunea coadă pentru a evita supraîncărcarea stivei.

Liste

Unul dintre cele mai importante elemente ale programării funcționale, împreună cu recursiunea, este liste. Ele oferă baza pentru structuri complexe de date. Ca și în alte limbi funcționale, listele sunt pur și simplu legate într-un mod cap-coadă. Funcția cons este folosită pentru a crea o listă, iar funcțiile car și cdr sunt folosite pentru a accesa capul și, respectiv, coada listei. Deci, lista (lista 1 2 3) nu este altceva decât (cons 1 (cons 2 (cons 3 "()))). Aici „() este o listă goală. Deci, o funcție tipică de procesare a listei arată astfel:

(definiți (sum lst) (dacă (null? lst) 0 (+ (car lst) (sum (cdr lst)))))

Această funcție însumează pur și simplu elementele unei liste. Așa arată multe funcții de procesare a listelor, într-una dintre ele articolele urmatoareÎți voi spune de ce. Deocamdată, voi observa doar că dacă înlocuim primul argument în plus cu 1, obținem o funcție care calculează lungimea listei.

Funcții de ordin superior

Deoarece funcțiile pot fi transmise ca argumente și returnate ca valoare, ar fi bine să găsiți o utilizare pentru aceasta. Luați în considerare următorul exemplu clasic:

(definiți (harta f lst) (dacă (null? lst) lst (contra (f (car lst)) (harta f (cdr lst)))))

Funcția map aplică funcția f fiecărui element din listă. Oricât de ciudat ar părea, acum putem exprima funcția de calcul a lungimii unei liste în termeni de sumă și hartă:

(definiți (lungime lst) (sumă (hartă (lambda (x) 1) lst)))

Dacă ați decis brusc că toate acestea sunt oarecum prea simple, atunci să ne gândim la asta: cum să implementați liste folosind funcții de ordin superior?

Adică trebuie să implementați funcțiile cons , car și cdr astfel încât acestea să satisfacă următoarea relație: pentru orice listă lst este adevărat că valoarea (cons (car lst) (cdr lst)) coincide cu lst . Acest lucru se poate face după cum urmează:

(definiți (cons x xs) (lambda (alegeți) (dacă (echivalentul? alegeți 1) x xs))) (definiți (car f) (f 1)) (definiți (cdr f) (f 2))

Cum functioneaza? Aici funcția cons returnează o altă funcție care are un parametru și, în funcție de acesta, returnează fie primul, fie al doilea argument. Este ușor să verificați dacă relația necesară este valabilă pentru aceste funcții.

Folosind citate și metaprogramare

O caracteristică plăcută a limbajului Lisp este că este extrem de convenabil pentru a scrie programe care convertesc alte programe. Ideea este că un program constă din liste, iar o listă este structura principală de date în limbaj. Există o modalitate de a „cita” pur și simplu textul unui program, astfel încât acesta să fie perceput ca o listă de atomi.

Atomi sunt pur și simplu expresii de caractere, de exemplu ("hello "world) , care este același cu "(hello world) , sau în forma completă (quote (hello world)) . Deși majoritatea dialectelor Lisp au șiruri de caractere , uneori puteți obține Mai important, folosind această abordare puteți simplifica generarea de cod și procesarea programului.

În primul rând, să încercăm să înțelegem calculele simbolice. Acesta este de obicei înțeles ca sisteme de algebră computerizată care sunt capabile să manipuleze obiecte simbolice, formule, ecuații și alte obiecte matematice complexe (există multe astfel de sisteme, exemplele principale fiind sistemele). arțarȘi Mathematica).

Puteți încerca să implementați diferențierea simbolică. Cred că toți cei care sunt aproape de a termina școala își imaginează regulile de diferențiere (deși în realitate totul este puțin mai complicat - aici vom calcula derivata parțială prin simpla numărare a altor variabilele sunt constante, dar asta nu complică deloc problema).

Așa că voi da doar un exemplu de cod care ar arăta esența problemei, lăsând detaliile cititorului (care, sper, va studia cu atenție cartea „Structura și interpretarea programelor de calculator”).

(definiți (deriva exp var) (cond ((număr? exp) 0) ((variabilă? exp) (dacă (aceeași variabilă? exp var) 1 0)) ((suma? exp) (suma-suma (deriv ( addend exp) var) (deriv (augend exp) var))) ((produs? exp) (fabricare-suma (fabricare-produs (multiplicator exp) (deriv (multiplicand exp) var)) (fabricare-produs (deriv (multiplicator) exp) var) (multiplicand exp)))) (altfel (eroare „tip expresie necunoscută - DERIV” exp))))

Aici funcția deriv este o implementare a algoritmului de diferențiere așa cum este predat în școală. Această funcție necesită implementarea funcțiilor de număr? ,variabil? și așa mai departe, care ne permit să înțelegem ce natură are acest sau acel element de expresie. De asemenea, trebuie să implementați funcții suplimentare make-produs și make-sum. Aici folosim condiția de construcție, care ne este încă necunoscută - acesta este un analog declarație switchîn limbaje de programare precum C și Java.

Înainte de a trece la implementarea caracteristicilor lipsă, este de remarcat faptul că programarea funcțională folosește destul de des o abordare de dezvoltare de sus în jos. Acesta este momentul în care sunt scrise mai întâi funcțiile cele mai generale, iar apoi funcțiile mici care sunt responsabile pentru detaliile implementării.

(definiți (variabilă? x) (simbolul? x)) (definiți (aceeași variabilă? v1 v2) (și (variabilă? v1) (variabilă? v2) (echivalentul? v1 v2))) (definiți (suma-a1) a2) (lista "+ a1 a2)) (definiți (produsul de fabricație m1 m2) (lista "* m1 m2)) (definiți (suma? x) (și (perechea? x) (echivalentul? (mașină x) "+ ))) (definiți (adăugați s) (cadr s)) (definiți (augend s) (caddr s)) (definiți (produs? x) (și (pereche? x) (echivalent? (car x) "*)) ) (definiți (multiplicator p) (cadr p)) (definiți (multiplicand p) (caddr p))

Implementarea acestor funcții nu necesită comentarii speciale, cu posibila excepție a funcțiilor cadr și caddr. Acestea nu sunt altceva decât funcții care returnează al doilea și, respectiv, al treilea element al unei liste.

Dacă utilizați interpretul interactiv Scheme, puteți verifica cu ușurință dacă codul rezultat funcționează corect, dar fără a simplifica expresiile:

(deriv "(+ x 3) "x) => (+ 1 0) (deriv "(* (* x y) (+ x 3)) "x) => (+ (* (* x y) (+ 1 0) )) (* (+ (* x 0) (* 1 y)) (+ x 3)))

Pentru cazuri banale (de exemplu, înmulțirea cu 0), problema simplificării se rezolvă destul de ușor. Această întrebare este lăsată la latitudinea cititorului. Majoritatea exemplelor din acest articol sunt preluate din cartea SICP, așa că dacă aveți dificultăți, puteți pur și simplu să vă referiți la sursă (cartea este în domeniul public).

Ca orice dialect, Lisp are capacități mari de metaprogramare, în principal legate de utilizarea macrocomenzilor. Din păcate, această problemă necesită o analiză într-un articol separat.

Să scriem o funcție care va elimina zahărul sintactic din definiția funcției așa cum am discutat mai devreme:

(definiți (desugar-define def) (let ((fn-args (cadr def)) (corp (caddr def))) (let ((nume (mașină fn-args))) (args (cdr fn-args))) (lista "definiți numele (lista "lambda args body)))))

Această funcție funcționează excelent cu definiții de funcții bine formate:

(desugar-define "(definiți (succ x) (+ x 1)))) => (definiți succ (lambda (x) (+ x 1)))

Cu toate acestea, acest lucru nu funcționează pentru definiții obișnuite precum (define x 5) .
Dacă vrem să eliminăm zahărul sintactic în program mare care conțin multe definiții diferite, atunci trebuie să implementăm verificare suplimentară:

(definiți (sugared? def) (și (eq? (car def) "definiți) (listă? (cadr def))))

O astfel de verificare poate fi integrată direct în funcția de definire a desugarului, asigurându-vă că, dacă definiția nu trebuie să elimine zahărul sintactic, pur și simplu nu se schimbă (acest exercițiu banal este lăsat la latitudinea cititorului). Apoi puteți include întregul program într-o listă și puteți utiliza harta:

(hartă desugar-define prog)

Concluzie

În acest articol, nu mi-am propus să vorbesc despre Scheme în detaliu. În primul rând, am vrut să arăt câteva caracteristici interesante ale limbajului și să atrag cititorul să studieze programarea funcțională. Acest limbaj minunat, în ciuda simplității sale, are propriul farmec și caracteristici care fac programarea în el foarte interesantă. În ceea ce privește instrumentul de lucru cu Scheme, cei cu voință puternică se pot întoarce MIT-Scheme, iar restul - bucurați-vă de un mediu de învățare excelent Dr. Rachetă. Într-unul dintre următoarele articole vă voi spune cu siguranță cum să vă scrieți propriul interpret Scheme.

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 folosite de mai multe ori. Biblioteca standard Python vine cu o mulțime de funcții gata făcute și bine 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, vor fi utilizați și explicați termeni relevanț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.
Prelucrare liste (secvențe).
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ă. Practic caracteristici 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