Programarea funcțională este o paradigmă de programare care tratează calculul ca evaluare de funcții matematice și evită starea și datele mutabile. Se pune accent pe aplicarea de funcții, spre deosebire de programarea imperativă, care folosește în principal de schimbările de stare.
Modelul matematic al programării funcționale îl reprezintă calculul lambda. Limbajele funcționale moderne pot fi considerate extensii ale calculului lambda. Noțiunea de bază în această paradigmă este cea de funcțională sau funcție de nivel înalt, o funcție care poate accepta ca argument sau returna ca valoare o altă funcție.
Deși nu sunt complet funcționale, atât primele versiuni de Lisp cât și APL au fost importante în dezvoltarea programării funcționale. Versiunile mai recente de Lisp, cum sunt Scheme și unele variante de APL furnizează suport funcțional complet. Printre alte limbaje funcționale importante se numără Erlang, Haskell, și ML.
Limbajele de programare funcționale, mai ales cele pur funcționale, sunt promovate mai ales în mediile academice, fiind rar folosite în dezvoltarea de software comercial. Totuși, există limbaje funcționale folosite și în industrie și în aplicații comerciale, cum ar fi Erlang, OCaml, Haskell, Scheme (din 1986) și limbaje de programare specifice unor domenii, ca R (în statistică),Programul conferinței useR! 2006 include lucrări despre utilizarea comercială a limbajului R Mathematica (calcul simbolic), J și K (în analiza financiară), și XSLT (XML).
Multe limbaje de programare nefuncționale, cum sunt C, C++ și C# pot fi făcute să aibă un comportament funcțional prin utilizarea pointerilor la funcții, biblioteca <functional>, respectiv funcțiile lambda.
Istoric
Calculul lambda reprezintă contextul teoretic al descrierii și evaluării funcțiilor. Deși este mai mult o abstracție matematică decât un limbaj de programare, el formează baza aproape tuturor limbajelor de programare funcționale din prezent.
Logica combinatorică este o bază teoretică echivalentă, dezvoltată de Moses Schönfinkel și Haskell Curry. A fost dezvoltată inițial pentru a obține o abordare mai clară a bazelor matemaicii. Logica combinatorică este percepută ca fiind mai abstractă decât calculul lambda și a fost inventată înaintea acestuia.
Unul din primele limbaje cu caracteristici funcționale a fost LISP, dezvoltat de John McCarthy pe când lucra la MIT la seria de calculatoare științifice IBM 700/7000 spre sfârșitul anilor 1950. " The implementation of LISP began in Fall 1958." ('„Implementarea LISP a început în toamna lui 1958”') LISP a introdus multe funcționalități prezente astăzi în limbajele funcționale, deși LISP este un limbaj multi-paradigmă. Scheme și Dylan au reprezentat eforturi ulterioare în vederea simplificării și îmbunătățirii LISP.
Information Processing Language (IPL) este uneori numit primul limbaj funcțional de programare a calculatoarelor. Este un limbaj în stilul limbajelor de asamblare, folosit la manipularea listelor de simboluri. Conține noțiunea de "generator", care este similară cu cea de funcție care acceptă ca argument o altă funcție și, deoarece este un limbaj de nivel scăzut, codul poate fi folosit drept date, și astfel IPL poate fi privit ca un limbaj capabil să lucreze pe funcții de nivel înalt. Totuși, el se bazează mult pe modificare structurii listelor și pe alte caracteristici similare ale programării imperative.
Kenneth E. Iverson a dezvoltat limbajul de programare APL la începutul anilor 1960, și l-a descris în cartea sa A Programming Language. APL a fost sursa de inspirație a lui John Backus când a inventat limbajul de programare FP. La începutul anilor 1990, Iverson, împreună cu Roger Hui, au creat un successor al lui APL, limbajul de programare J. La jumătatea anilor 1990, Arthur Whitney, care lucrase anterior cu Iverson, a creat limbajul de programare K, utilizat comercial în domeniul financiar.
John Backus a descris limbajul de programare FP în prezentarea din 1977 de la decernarea Premiului Turing, prezentare intitulată („Poate fi programarea eliberată de stilul von Neumann? Un stil funcțional și algebra programelor aferentă acestuia”). El definește programele funcționale ca fiind constituite într-o manieră ierarhică, prin utilizarea „formelor combinante” care permit o „algebră de programe”; în limbajul modern, aceasta înseamnă că programele funcționale respectă principiul compoziționalității. Lucrarea lui Backus a popularizat cercetarea în domeniul limbajelor funcționale, deși a pus accent pe programarea la nivel funcțional, și nu pe stilul calculului lambda, stil ce a ajuns să fie asociat cu programarea funcțională.
În anii 1970, a fost creat limbajul de programare ML, de către Robin Milner la Universitea Edinburgh, iar David Turner a dezvoltat întâi limbajul SASL la Universitea St. Andrews și apoi Miranda la Universitatea Kent. ML a fost ulterior dezvoltat mai departe în mai multe dialecte, cele mai cunoscute astăzi fiind OCaml și Standard ML. Limbajul de programare Haskell a fost standardizat în 1998 la capătul a 10 ani de muncă, devenind de atunci limbajul standard de cercetare și producție în domeniul programării funcționale. Compilatorul de Haskell GHC este un proiect cu sursă deschisă și cu o licență tip BSD. Concepte
Există o serie de concepte și paradigme specifice programării funcționale, și care în general sunt străine programării imperative (inclusiv programării orientate obiect). Totuși, limbajele de programare sunt adesea hibrizi ale mai multor paradigme de programare, iar programatorii care utilizează limbaje "predominant imperative" ajung să utilizeze și unele dintre aceste concepte.
Funcționalele
Funcțiile sunt numite de nivel înalt, sau funcționale dacă pot primi ca argument alte funcții, și dacă pot returna ca valoare alte funcții. (astfel de exemple sunt derivata și primitiva din analiza matematică)
Noțiunea de funcțională este strâns legată de cea de funcție de clasa întâi, prin aceea că funcționalele și funcțiile de clasa întâi permit ambele primirea de funcții ca argument și returnarea de funcții ca valoare. Diferența între cele două este foarte subtilă: "funcționalele" descriu un concept matematic de funcții care operează pe alte funcții, iar "funcțiile de clasa întâi" este un termen din informatică ce descrie entități din limbajele de programare care nu au restricții la utilizare (astfel funcțiile de clasa întâi pot apărea oriunde într-un program unde pot apărea alte entități de clasa întâi, cum sunt numerele, inclusiv ca argumente ale altor funcții sau ca valori returnate de acestea).
Funcționalele permit currying-ul, o tehnică în care funcțiile sunt aplicate pe rând argumentelor lor, la fiecare aplicare returnându-se o nouă funcție care acceptă următorul argument.
Funcții pure Funcțiile sau expresiile pur funcționale nu au memorie sau efecte laterale, dacă nu se ia în considerare calcularea rezultatului ca efect lateral. Aceasta înseamnă că funcțiile pure au câteva proprietăți utile, dintre care multe pot fi folosite pentru optimizarea codului: Dacă nu se utilizează rezultatul unei expresii pure, el poate fi eliminat fără a afecta alte expresii. Dacă o funcție pură este apelată cu parametri care nu cauzează efecte laterale, rezultatul este constant în raport cu lista de parametri (fenomen numit uneori transparență referențială), adică dacă o funcție pură este apelată din nou cu aceiași parametri, ea va returna același rezultat (aceasta poate permite utilizarea de cache-uri). Dacă nu există dependențe de date între două expresii pure, atunci ordinea evaluării lor poate fi inversată, sau ele pot fi evaluate în paralel și nu pot interfera una cu cealaltă (cu alte cuvinte, evaluarea unei expresii pure este thread-safe). Dacă întregul limbaj nu permite efecte laterale, atunci se poate utiliza orice strategie de evaluare; aceasta dă compilatorului libertatea de a reordona sau combina evaluarea expresiilor dintr-un program (de exemplu, utilizând evaluarea lazy).
Deși multe compilatoare pentru limbaje de programare imperative detectează funcțiile pure, și efectuează eliminarea de subexpresii comune la apelul funcțiilor pure, ele nu pot să facă acest lucru întotdeauna pentru bibliotecile precompilate, care în general nu expun această informație, împiedicând astfel optimizările ce implică aceste funcții externe. Unele compilatoare, cum ar fi gcc, adaugă cuvinte cheie suplimentare pentru ca un programator să poată marca explicit funcțiile externe ca pure, permițând astfel aceste optimizări. Fortran 95 permite declararea funcțiilor ca fiind "pure".
Recursivitatea Iterarea, în limbajele funcționale, se realizează de regulă prin recursivitate. Funcțiile recursive se autoapelează, permițând efectuarea unei operații în mod repetat. Recursivitatea poate necesita reținerea unei stive, dar tail recursion poate fi recunoscută și optimizată de compilator prin transformarea ei într-un cod similar cu cel utilizat pentru iterații în limbajele imperative. Standardul limbajului Scheme necesită recunoașterea de către implementări și optimizarea tail recursion.
Șabloanele de recursivitate des întâlnite pot fi luate în considerare prin utilizarea de funcții de ordin superior, catamorfismele și anamorfismele fiind cele mai evidente exemple. Asemenea funcții de nivel înalt joacă un rol analog celui jucat de structurile de control cum ar fi buclele în limbajele imperative.
Evaluarea strictă și non-strictă Limbajele funcționale pot fi clasificate după utilizarea evaluării stricte sau non-stricte, concepte ce se referă la modul în care sunt prelucrate argumentele unei funcții la evaluarea expresiei.
Pe scurt, evaluarea strictă evaluează mereu complet argumentele funcțiilor înainte de invocarea funcției. Evaluarea non-strictă poate proceda altfel.
De exemplu, se consideră următoarele două funcții f și g:
f(x) := x^2 + x + 1 g(x, y) := x + y
În evaluare strictă, va trebui să se evalueze argumentele funcțiilor întâi, de exemplu: f(g(1, 4)) = f(1 + 4) = f(5) = 5^2 + 5 + 1 = 31
Evaluarea non-strictă nu trebuie să evalueze complet argumentele; în particular, poate trimite funcției argumentele neevaluate, urmând ca acestea să fie evaluate mai târziu. De exemplu, o strategie non-strictă de evaluare (apel după nume) ar putea funcționa astfel: f(g(1, 4)) = g(1, 4)^2 + g(1, 4) + 1 = (1 + 4)^2 + (1 + 4) + 1 = 5^2 + 5 + 1 = 31
O proprietate-cheie a evaluării stricte este că atunci când evaluarea unui argument nu se mai termină, întreaga expresie nu se termină. La evaluarea non-strictă, nu se întâmplă așa în mod necesar, deoarece argumentele ar putea să nu mai fie evaluate deloc.
Avantajele evaluării stricte
Parametrii sunt de regulă trimiși ca unități atomice simple, și nu ca expresii complexe. (De exemplu, întregul 5 poate fi trimis pe un registru, pe când expresia 1+4 necesită mai multe locații de memorie). Evaluarea strictă are implementări directe pe hardware.
Ordinea evaluării este clară pentru programator: fiecare argument trebuie să fie evaluat înainte de invocarea corpului funcției.
Avantajele evaluării non-stricte
Calculul lambda furnizează o bază teoretică mai puternică pentru limbajele ce folosesc evaluarea non-strictă.
Un evaluator non-strict poate recunoaște că o subexpresie nu mai trebuie să fie evaluată. De exemplu, se dă definiția: multiply(0, x) = 0; multiply(n, x) = x + multiply(n-1, x); f(0) = 1; f(n) = n * f(n-1); și expresia multiply(0, f(1000000)) Un evaluator strict va trebui să efectueze un număr de pași de ordinul a pentru a găsi valoarea lui f(1000000). Un evaluator non-strict poate utiliza definiția înmulțirii întâi, reducând întreaga expresie la 0 înainte de a încerca să calculeze f(1000000). Evaluarea non-strictă poate utiliza cele de mai sus pentru a permite structuri de date infinite. De exemplu, în Haskell, dată fiind definiția: evens n = n : evens (n+2) -- o "listă infinită" de numere pare începând cu n
-- Funcția "take n" întoarce primele n elemente ale argumentului