Programmazione funzionale
La programmazione funzionale è un paradigma diverso da quello procedurale, in contrapposizione a quello procedurale (o imperativa) e a quello orientato ad oggetti.
Premessa
La programmazione ad oggetti ha posto maggiore enfasi sullo stato del programma, consentendo di unire funzioni e dati in classi, in modo tale che ogni oggetto (istanza di una classe) abbia un proprio stato che può essere modificato per mezzo dei metodi pubblici messi a disposizione dalla classe. E' come se avessimo tante piccole cellule che gestiscono i propri dati e comunicano mediante i metodi dichiarati nella propria interfaccia pubblica.
La programmazione ad oggetti ha rappresentato un grande passo avanti perché ha reso possibile implementare l'information hiding a livello di linguaggio, cosa prima impossibile. Un'ulteriore innovazione è stata la possibilità di ereditare comportamenti da una o più classi base, per poter scrivere nuove classi senza dover riscrivere funzioni già presenti.
Tuttavia la possibilità di ereditare da più classi si è ben presto scoperto essere un'arma a doppio taglio, in cui la costruzione e l'uso delle istanze poli-ereditanti rappresentava un problema di non facile soluzione se non in casi molto semplici, ed è stata presto abbandonata.
A questi ed altri problemi si è fatto fronte ad esempio cercando di prediligere la composizione alla derivazione, e la dichiarazione di interfacce ai tipi classe, nei tipi usati nel programma. Molti design patterns sono stati sviluppati in tal senso e saranno oggetto di ulteriori post.
Lo unit testing di classi complesse si è rivelato essere spesso un problema di non facile risoluzione, specie quando queste dipendono da altre classi nella loro costruzione, e che a loro volta richiedono uno stato per poter essere invocate. Tali problemi sono stati risolti facendo uso delle interfacce, limitando e isolando l'istanziazione diretta di oggetti facendo invece affidamento a factory o a meccanismi di dependency injection (che saranno oggetto di altri post), o isolandone l'uso in metodi virtuali da poter derivare in fase di test. Tuttavia rappresentano un ostacolo spesso non banale da risolvere. Anche in questo caso i problemi derivano prevalentemente dallo stato necessario alla classe per la corretta esecuzione dei propri metodi, sia in produzione che in fase di test.
Functional programming
La programmazione funzionale rivolge il proprio focus sulle funzioni separandole nettamente dai dati su cui esse operano, eliminando del tutto il problemi sulla gestione dello stato evidenziati. Infatti non prevede alcuno stato ma semplicemente la trasformazione dei dati in input in (nuovi) dati di output oggetto di eventuali successive elaborazioni. Può risultare abbastanza sconcertante sulle prime rendersi conto che in questo nuovo paradigma, l'istruzione di assegnazione che modifica una varabile, semplicemente, almeno nella forma pura, non esiste.
Nella programmazione ad oggetti gli sviluppatori creano oggetti, via via più complessi, su cui operano con dei metodi, ed è cosi che si attua l'information-hiding. Nella programmazione funzionale ci sono un numero limitato di tipi di base (liste, dizionari, set), che vengono composti in strutture più complesse e su cui si accede con metodi specializzati.
Ogni funzione restituisce un set di nuovi dati e non modifica i dati in input. Questo fa si che non si siano più problemi di stato interno incoerente, non essendoci più uno stato, e lo unit testing diventi un gioco da ragazzi.
A differenza della programmazione imperativa, in cui di solito si usano dei cicli per filtrare/manipolare/eventualmente ricomporre i dati, nella programmazione funzionale ci sono delle funzioni apposite per realizzare gli stessi obiettivi.
Analizziamo alcune di queste funzioni, presenti (con sintassi diverse) in tutti i linguaggi funzionali. Una peculiarità dei linguaggi functional è certamente quella di trattare le funzioni come oggetti primitivi, quindi la possibilità di creare/manipolare funzioni alla stregua di tutti gli altri tipi gestiti dal linguaggio. Questa caratteristica mal si sposa con i linguaggi strongly typed, in cui ogni funzione deve avere un tipo e dei parametri ben definiti. A tale limite si è posto un parziale rimedio con le funzioni lambda (es. c#, java), ma il problema di fondo rimane. Pertanto meglio si prestano alla programmazione linguaggi interpretati come Javascript o Phyton, in cui i costrutti functional sono molto più semplici ed eleganti.
Per semplicità parlerò in termini di collezioni, ma più precisamente le funzioni si applicano di solito a oggetti genericamente iterabili. Non farò riferimento ad un particolare linguaggio di programmazione, ma queste funzioni sono presenti in tutti i linguaggi che possiedono caratteristiche funzionali.
Filter(collezione, funzione criterio)
Ad ogni elemento della collezione applica la funzione criterio data, e restituisce via via tutti gli elementi per cui questa restituisce "vero". Il risultato della Filter è una nuova collezione, o più in generale, un oggetto iterabile, dello stesso tipo del primo parametro
Simili a Filter sono Find, FindLast, con medesimi parametri, che però restituiscono solo, rispettivamente, il primo o l'ultimo elemento della collezione che rispetta un certo criterio.
Map(collezione, funzione di trasformazione)
Reduce(collezione, funzione binaria)
Itera la collezione prendendo prima i primi due elementi, usando essi come parametri per invocare la funzione binaria, e poi eseguendo la funzione binaria con tutti successivi elementi della collezione, con il risultato della precedente iterazione.
Ad esempio, dati gli elementi a1, a2, a3, a4, a5 e la funzione f, il risultato sarà
f ( f (f( f( f(a1,a2), a3), a4), a5 )
Essendo f una generica funzione, la reduce può essere usata per effettuare la somma di tutti gli elementi di un array ad esempio, ma anche per funzioni molto più complesse.
E' possibile che il linguaggio fornisca una versione ReduceRight ed una versione ReduceLeft in base all'ordine con cui debbano essere considerati i parametri.
Predicati su collezioni
Every(collezione, predicato)
Some(collezione, predicato)
Manipolazioni di liste
I linguaggi funzionali presentano di solito una vasta gamma di funzioni per manipolare liste. Ne elenco alcune:
Partition(collezione, predicato)
Range(inizio, fine passo)
Questo costrutto serve a creare una lista di interi da inizio a fine ad incrementi di "passo", ad esempio
Range(0,10,2) = [0,2,4,6,8,10]
Concat(collezione1, collezione2,..)
Tail(collezione)
Head(collezione)
Initial(collezione)
Last(collezione)
Union(collezione1, collezione2,..)
Zip(collezione1, collezione2, ...)
Rif. Lodash zip
Unzip(collezione)
Funzioni che restituiscono liste (yeld return , yeld break)
Manipolazione di funzioni
Currying
E' la trasformazione di una funzione con n parametri in una catena di funzioni a singolo parametro. La funzione risultante è invocabile solo quando tutti i parametri sono forniti, tuttavia è possibile che i vari parametri siano avvalorati in trasformazioni successive della funzione, in momenti diversi e punti diversi del programma. I parametri saranno avvalorati eseguendo le funzioni restituite dal curry.
Ad esempio prendiamo la funziona binaria prodotto(x,y) = x*y
f = curry(prodotto) è una funzione unaria che restituisce a sua volta una funzione unaria in modo che
(f(x))(y) =12
quindi f(3)= una funzione che accetta un parametro e restituisce suo triplo
ossia f(3)(x) = x*3
f(3)(4) = 12
Rif. Lodash curry
Partial application
E' la trasformazione di una funzione ad n parametri in una funzione con n-m parametri, di cui gli m sono forniti in anticipo. E' un concetto simile a quello del currying ma i parametri sono forniti in anticipo. Ad esempio,
se prodotto(x,y) = x*y
e f = partial(prodotto, 3)
f è la funzione f(x) = x*3
Ossia se confrontiamo con l'esempio precedente, è il risultato del curry invocato col valore 3.
La partial application è uno strumento comodo per realizzare lo strategy pattern, che sarà oggetto di un post a parte.
Rif. lodash partial
Memoization
E' la tecnica di memorizzazione dei risultati di una funzione, che si presuppone senza memoria. Il risultato è una nuova funzione che memorizza i risultati della funzione di partenza e li restituisce direttamente quando viene invocata con parametri già precedentemente utilizzati.
Lo scopo è quello di velocizzare le invocazioni successive, al costo di utilizzare dello spazio di memoria per salvare i risultati precedenti. Può essere molto utile nell'applicazione di alcune funzioni ricorsive o molto costose. Nel caso di funzioni ricorsive ha anche spesso il pregio di evitare un eccessivo annidamento su determinati rami di esecuzione.
Rif. memoizzazione
Caching
La memoizzazione è uno specifico tipo di caching, sul risultato di una funzione. Il caching è un concetto più generico che prevede l'allocazione di uno spazio di memoria (con una lista o un dizionario ad esempio) da usare per accedere al risultato di calcoli computazionalmente complessi oppure che sarebbero più lenti da leggere se presi dal disco o dal database.
Per esempio nei motori scacchistici, ci sono libri di aperture di finali, frutto di migliaia di ore di elaborazione da reti di computer, che vanno a comporre degli alberi poi consultati rapidamente nei calcoli delle varianti.
Oppure si può pensare al caching dei primi livelli di un indice b-tree di una tabella di un database relazionale. I dati soggetti a cache possono trovarsi in liste o più tipicamente alberi o dizionari.
Lazy Invocation
Il calcolo "lazy" è una strategia di valutazione delle funzioni, detta anche "call by need" o esecuzione differita, e si pone l'obiettivo di ritardare il calcolo di espressioni / esecuzione di funzioni sin quando non sia effettivamente necessario. Di solito non ci sono istruzioni che esplicitamente creano la lazyness di una funzione, che invece è insita nella progettazione e/o nel linguaggio.
I vantaggi dell'esecuzione differita sono la maggiore velocità di esecuzione, la possibilità di utilizzare strutture potenzialmente di cardinalità infinita, evitare la creazione di strutture intermedie per il passaggio di parametri e ridurre il numero di chiamate complessive.
La lazy invocation è presente anche in linguaggi non funzionali, come il c#, per esempio con gli operatori short circuit && e || ed è agevolata dagli oggetti iterabili (vedi c# enumerables).
Ma nella programmazione funzionale la potenzialità della lazy invocation è maggiore potendo più agevolmente passare come parametri delle funzioni che restituiscono liste potenzialmente infinite, i cui elementi non sono calcolati se non quando sono effettivamente necessari nel calcolo.
La lazy invocation è un vero e proprio design pattern e può essere anche implementato in proprietà read only nella programmazione object oriented, quindi non solo nel paradigma della programmazione funzionale. Ad esempio potremmo avere una classe che espone una proprietà che viene calcolata solo al momento del primo accesso in lettura, ed in quel caso poi memorizza il risultato (applicando di fatto un caching) per restituirlo direttamente nelle letture successive.
Ma la lazy invocation non implica necessariamente un caching, per esempio supponendo di avere una funzione molto complessa da eseguire f ed una funzione che debba moltiplicare tutti i valori di f calcolati usando come parametri x1,.... xn,
Un'invocazione "non lazy" potrebbe consistere nel calcolo di tutti i valori f(x1), ... f(xn) e poi un ciclo che moltiplica tutti i valori ottenuti. Se invece man mano calcoliamo gli f(xi) e moltiplichiamo il risultato con il prodotto precedentemente ottenuto, abbiamo un'invocazione lazy di f. A proposito abbiamo già analizzato il currying.
Possiamo affermare quindi che lazy invocation, memoization, currying, operazioni su oggetti iterabili sono i pilastri della programmazione funzionale.
Conclusione
In generale è bene acquisire dimestichezza con tutti i paradigmi di programmazione, dal procedurale all'OOP al funzionale, ed utilizzare ognuno di essi con cognizione di causa, con l'obiettivo di rendere il codice semplice, manutenibile ed efficiente.
Riferimenti, bibliografia
Issues in the Design of anObject Oriented Programming Language
Functional thinking di Neal Ford, O Reilly
Nessun commento:
Posta un commento