Programare funcțională

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ă), 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. 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 (ISBN 978-0-471-43014-8, publicată în 1962). 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ă Can Programming Be Liberated From the von Neumann Style? A Functional Style and its Algebra of Programs Arhivat în 21 iunie 2007, la Wayback Machine. („Poate fi eliberată programarea de stilul Von Neumann? Un stil funcțional și algebra sa de programe”). 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 Objective Caml ș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 si productie in din domeniul programării funcționale. Compilatorul de Haskell GHC este un proiect cu sursa deschisa si cu o licenta tip BSD. Odată cu apariția unor cărti cum este Real World Haskell el a intrat definitiv în practica producției profesionale de software.

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 curryingul, 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 1.000.000 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
take 0 (list)   = []                  -- când n este 0, întoarce o listă vidă
take n (x:list) = x : (take (n-1) list) -- altfel, întoarce primul element și n-1 dintre următoarele elemente

expresia

take 4 (evens 0)

returnează rapid [0,2,4,6]. În evaluarea strictă, evens ar trebui să fie complet evaluat pentru a se apela take, dar deoarece evens este recursiv, nu se va termina niciodată. Cu evaluarea non-strictă, funcția take 4 forțează doar evaluarea a patru elemente din evens 0 celelalte elemente nemaifiind inspectate sau evaluate.

Evaluarea lazy

Nevoia de o formă mai eficientă de evaluare non-strictă a condus la dezvoltarea evaluării lazy, un tip de evaluare non-strictă, în care evaluarea inițială a unui argument este partajată de-a lungul secvenței de evaluare. În consecință, un argument (cum ar fi g(1, 4) în exemplul de mai sus) nu este evaluat decât o dată. În cazul evaluării lazy, expresiile se trimit funcțiilor subordonate ca referințe la arbori de expresii ale căror valori nu au fost calculate încă. Când unul dintre arborii de expresie trebuie expandat, arborele de expresie își reține rezultatul, evitând astfel recalcularea aceleiași expresii a doua oară. În exempul inițial, aceasta ar funcționa după cum urmează:

= f(g(1, 4))
= g(1, 4)^2 + g(1, 4) + 1

Apoi trebuie evaluat g(1, 4). Acesta se poate calcula o singură dată, rezultând:

  g(1, 4)
  = 1 + 4
  = 5

Apoi, fiindcă ambele referințe la g(1, 4) sunt referințe la aceeași expresie pură, ambele își cunosc valoarea ca fiind 5. Aceasta înseamnă că valoarea lor este calculată o singură dată, deși ele sunt transmise funcției f simbolic.

= 5^2 + 5 + 1
= 25 + 5 + 1
= 31

Evaluarea lazy tinde să fie utilizată implicit în limbajele funcționale pure, ca Miranda, Clean și Haskell.

Programarea funcțională în limbajele nefuncționale

Se poate folosi un stil funcțional de programare și în limbaje care nu sunt tradițional considerate funcționale. Unele limbaje nefuncționale au împrumutat unele caracteristici, cum ar fi funcțiile de nivel înalt de la limbajele funcționale. Astfel, este mai ușor să se adopte un stil funcțional la utilizarea acestor limbaje. Construcțiile funcționale cum sunt funcțiile de nivel înalt sau listele lazy pot fi obținute în C++ cu ajutorul bibliotecilor. În C se pot utiliza pointeri pentru a obține efectele funcțiilor de nivel înalt, de exemplu se poate implementa funcția map cu ajutorul pointerilor. Unele limbaje declarative specifice unor domenii, cum sunt SQL sau Lex/Yacc, deși nu sunt mereu Turing-complete, folosesc unele elemente de programare funcțională, mai ales prin evitarea valorilor muabile.

Comparație cu programarea imperativă

Programarea funcțională este foarte diferită de programarea imperativă. Cele mai semnificative diferențe provin din faptul că programarea funcțională evită efectele laterale, care sunt utilizate în programarea imperativă pentru implementarea stării și intrărilor și ieșirilor. Programarea funcțională pură interzice efectele laterale, ceea ce îi aduce transparența referențială, care face mai ușor de verificat, optimizat, și paralelizat programele, și mai ușor de scris unelte automate de efectuare a acestor taskuri.

Functionalele sunt rareori folosite în programarea imperativă. Acolo unde un program imperativ ar utiliza o buclă pentru parcurgerea unei liste, un stil funcțional folosește adesea o funcțională, map, care primește ca argumente o funcție și o listă, aplicând funcția pe fiecare element al listei, returnând o listă cu rezultatele.

Simularea stării

Există taskuri pentru, de exemplu, menținerea balanței unui cont bancar, care adesea par cel mai natural de implementat folosind stări. Programarea funcțională pură efectuează aceste taskuri, precum și cele de intrare/ieșire cum ar fi citirea de date de la utilizator sau afișarea pe ecran în alt mod.

Limbajul funcțional pur Haskell le implementează utilizând monadele, un concept provenit din teoria categoriilor. Monadele sunt puternice și oferă o metodă intuitivă de modelare a stării (și alte efecte lateral cum ar fi I/E) într-o manieră imperativă fără a pierde puritatea. În timp ce monadele existente sunt ușor de utilizat, mulți găsesc dificil de înțeles modul de definire a unor noi monade (ceea ce este necesar uneori pentru unele tipuri de biblioteci).

Probleme de eficiență

Limbajele funcționale au devenit mai eficiente de-a lungul timpului. Pentru programe care efectuează calcule numerice intensive, limbajele funcționale ca OCaml și Clean sunt similare în viteză cu C. Pentru programe care efectuează operații pe matrice și pe baze de date multidimensionale, au fost proiectate limbajele funcționale vectoriale (ca J și K), cu atenție sporită pentru optimizări.

Limbajele de programare funcțională au fost percepute ca fiind mai puțin eficiente în utilizarea procesorului și a memoriei decât cele imperative. Totuși, imuabilitatea datelor poate, în multe cazuri, să conducă la eficiență a execuției, deoarece permite compilatorului să facă presupuneri care nu pot fi făcute cu certitudine într-un limbaj imperativ. Cea mai gravă pierdere de performanță este exponențială. Situații în care asemenea pierderi de performanță apar foarte rar în practică.

Stiluri de codificare

Programele imperative tind să pună accent pe seria de pași efectuați de un program în executarea unei acțiuni, iar cele funcționale tind să pună accent pe compoziția și aranjamentul funcțiilor, adesea fără a specifica explicit pașii. Un exemplu simplu de două soluții ale aceluiași scop (utilizând același limbaj multiparadigmă Python) ilustrează acest aspect.

# imperative style
target = [] # create empty list
for item in source_list: # iterate over each thing in source
    trans1 = G(item) # transform the item with the G() function
    trans2 = F(trans1) # second transform with the F() function
    target.append(trans2) # add transformed item to target

Versiunea funcțională are un cu totul alt aspect:

# functional style
# FP-oriented languages often have standard compose()
compose2 = lambda F, G: lambda x: F(G(x))
target = map(compose2(F, G), source_list)

Spre deosebire de stilul imperativ care descrie pașii implicați în compunerea lui target, stilul funcțional descrie relația matematică dintre source_list și target.