Elementi Fondamentali 1

In questo secondo articolo della serie dedicata alla programmazione funzionale ci dedichiamo ad introdurre gli elementi fondamentali che caratterizzano i linguaggi di programmazione che adottano il paradigma funzionale.

Articolo Precedente

Caratteristiche dei linguaggi funzionali

Immutabilità

Non ci sono variabili nella programmazione funzionale.
I valori immagazzinati sono comunque chiamati variabili, per un discorso di continuità, ma di fatto si tratta di costanti. Una volta assegnato un valore ad una variabile esso è per sempre.
In realtà il problema è molto minore anche perché le variabili sono quasi tutte locali e hanno quasi sempre una vita estremamente corta.
Ma come possiamo programmare senza variabili? Quando i linguaggi funzionali hanno bisogno di modificare un valore semplicemente ne fanno una copia, lasciando quindi intatto il valore nella variabile originale e restituendoci una copia modificata.
Altro punto cruciale nella programmazione funzionale è la mancanza di loop. Non esiste niente come for, while, do, repeat eccetera.
Questo non significa che non possiamo in assoluto fare dei loop nella programmazione funzionale, significa solo che non ci sono costrutti di linguaggio che ci permettano di farlo. Questo per un semplice motivo, tutti i cicli dei linguaggi imperativi si basano sul modificare ripetutamente il valore di una o più variabili e questo sarebbe in contrasto con l’immutabilità.
Scommetto che avete già intuito la soluzione al nostro problema dei loop. Basta usare un algoritmo ricorsivo.
Questo perché, come è facile capire, gli algoritmi ricorsivi non modificano il valore delle variabili ma effettuano i calcoli sulle copie di valori che vengono passati di chiamata in chiamata.
Lo so, inizialmente è piuttosto sconcertante, ma si tratta prevalentemente della paura di uscire dalla nostra comfort zone e avventurarci nell’ignoto. Mano a mano che ne farete uso scoprirete di apprezzare sempre di più le chiamate ricorsive.
L’immutabilità garantisce tantissimi vantaggi, pensate ad esempio a cosa succede quando si programma un software multi-threaded che fa chiamate a funzioni con side-effect. La chiamata di una funzione in un thread potrebbe cambiare il valore su cui una funzione di un’altro thread sta per fare dei calcoli, causando un errore imprevisto, intermittente e difficilissimo da debuggare.

Purezza

Quando parliamo di purezza, negli elementi fondamentali della programmazione funzionale, ci riferiamo alle funzioni pure.
Si tratta di funzioni che agiscono solamente sui parametri che gli vengono passati come input. Questo implica, ad esempio, che una funzione pure senza parametri debba restituire sempre un valore costante. Questo perché, potendo agire solamente sui parametri passati alla funzione, quindi non su variabili globali o di altro tipo, non avendo parametri in input non può che restituire sempre lo stesso valore.
Questa caratteristica porta al determinismo, che vedremo più nel dettaglio più avanti.
Le funzioni non pure sono tutte quelle funzioni che includono nei propri calcoli variabili non locali, quindi variabili esistenti al di fuori della funzione. Questo implica un comportamento non determinabile a priori perché il risultato restituito dalla funzione dipenderà da una variabile il cui valore potrebbe essere modificato esternamente.
Di fatto la conseguenza principale è che potremmo chiamare la funzione più volte con gli stessi parametri ottenendo però risultati diversi. Questo può essere la causa di alcuni dei bug più insidiosi e difficili da scovare.
Un’altra categoria di funzioni non pure è quella che produce side-effects. Vale a dire che non si limita a ricevere dei parametri in input e restituire un valore come output, ma modifica durante la propria esecuzione, il valore delle variabili passate come parametri o di altri elementi del programma.
Per quanto sia impossibile evitare del tutto le funzioni con side-effects, fanno infatti parte di questa categoria tutte le funzioni di I/O, di scrittura su database o via web, lo scopo della programmazione funzionale è segregarle ed utilizzarle solamente il minimo indispensabile. Questo perché sono spesso fonte di bug veri e proprio se non di errori logici dell’algoritmo.
Di fatto una delle ragioni per la quale i programmi funzionali sono tra i più sicuri, robusti ed efficienti è che i programmatori sono solitamente tanto disciplinati e rigorosi quanto il linguaggio che usano li obbliga ad essere.
Il problema dei linguaggi imperativi è che le funzioni con side-effects sono ovunque e quando c’è un bug andare a capire quale dei tanti effetti collaterali delle migliaia di chiamate di funzione del programma l’ha generato potrebbe essere molto complesso.

First Class Functions

Si dice che un linguaggio di programmazione implementa le First Class Functions se le funzioni vengono trattate nello stesso modo delle altre variabili e possono quindi essere passate come parametri ad altre funzioni o restituite come risultato della chiamata ad una funzione.
Inoltre questo implica che le funzioni possano essere assegnate ad una variabile.
La diretta conseguenza dell’avere, tra le altre caratteristiche del linguaggio, le First Class Functions è la possibilità di avere quelle che vengono definite High order functions ovvero funzioni di ordine superiore.
Le funzioni di ordine superiore sono appunto funzioni che accettano come parametri altre funzioni.
Chi di voi ha qualche esperienza di programmazione in un moderno linguaggio, come ad esempio javascript, sarà familiare con questo tipo di comportamento. Lo sfruttate ad esempio ogni volta che chiamate una funzione che accetta una callback function.
Quando ad esempio usate funzioni come map e passate tra gli argomenti anche una funzione che determinerà la trasformazione fatta sugli elementi della lista, o array, che volete mappare.

Tail call optimisation

Innanzitutto chiariamo di cosa parliamo quando diciamo Tail Call.
Tail call si riferisce a quella situazione in cui la chiamata di un metodo o una funzione è l’ultima istruzione di un altro metodo o funzione.
Questo capita spesso, ad esempio con una chiamata come la seguente:
int bar(int a) {
a = a * 3;
return foo(a);
}
La chiamata a foo è l’ultima istruzione della funzione bar, pertanto è una tail call.
Ovviamente avete già capito dove stiamo andando a parare. Quando scriviamo una funzione ricorsiva tutte le chiamate ricorsive sono di questo tipo.
Ora, cerchiamo di capire cosa esattamente possiamo ottimizzare. In ogni tail call, non solo nelle chiamate ricorsive è possibile ottimizzare la chiamata, trasformando in quello che di fatto è un (AAAAAAH) goto. Questo significa che tutto il lavoro che viene fatto dal compilatore per creare lo stack prima della chiamata e rimuoverlo in seguito può essere saltato.
Facciamo un esempio, questa funzione:

int func_a(int data) {
data = do_this(data);
return do_that(data);
}

genera un codice assembly che, più o meno, avrà questo aspetto:

… ! executing inside func_a()
push EIP ! push current instruction pointer on stack
push data ! push variable ‘data’ on the stack
jmp do_this ! call do_this() by jumping to its address
… ! executing inside do_this()
push EIP ! push current instruction pointer on stack
push data ! push variable ‘data’ on the stack
jmp do_that ! call do_that() by jumping to its address
… ! executing inside do_that()
pop data ! prepare to return value of ‘data’
pop EIP ! return to do_this()
pop data ! prepare to return value of ‘data’
pop EIP ! return to func_a()
pop data ! prepare to return value of ‘data’
pop EIP ! return to func_a() caller

Fate attenzione a come le chiamate POP, sia per data che per il registro EIP (fatte per restituire il valore di data e ripristinare il puntatore dell’istruzione), si ripetono in successione. Un set di queste chiamate può essere eliminato e rimpiazzato da una semplice istruzione JMP.

Per fare questo è necessario che la funzione do_that esegua il codice di epilogo della funzione func_a.

Questo tipo di ottimizzazione è sicuro perché la funzione func_a non esegue nessuna operazione dopo la chiamata alla funzione do_that.

Ed ecco il risultato:

… ! executing inside func_a()
push EIP ! push current instruction pointer on stack
push data ! push variable ‘data’ on the stack
jmp do_this ! call do_this() by jumping to its address
… ! executing inside do_this()
push EIP ! push current instruction pointer on stack
push data ! push variable ‘data’ on the stack

jmp do_that ! call do_that() by jumping to its address
… ! executing inside do_that()
pop data ! prepare to return value of ‘data’
pop EIP ! return to do_this()
pop data ! prepare to return value of ‘data’
pop EIP ! return to func_a() caller
pop data ! prepare to return value of ‘data’
pop EIP ! return to func_a() caller…

Immutabilità

Non ci sono variabili nella programmazione funzionale.
I valori immagazzinati sono comunque chiamati variabili, per un discorso di continuità, ma di fatto si tratta di costanti. Una volta assegnato un valore ad una variabile esso è per sempre.
In realtà il problema è molto minore anche perché le variabili sono quasi tutte locali e hanno quasi sempre una vita estremamente corta.
Ma come possiamo programmare senza variabili? Quando i linguaggi funzionali hanno bisogno di modificare un valore semplicemente ne fanno una copia, lasciando quindi intatto il valore nella variabile originale e restituendoci una copia modificata.
Altro punto cruciale nella programmazione funzionale è la mancanza di loop. Non esiste niente come for, while, do, repeat eccetera.
Questo non significa che non possiamo in assoluto fare dei loop nella programmazione funzionale, significa solo che non ci sono costrutti di linguaggio che ci permettano di farlo. Questo per un semplice motivo, tutti i cicli dei linguaggi imperativi si basano sul modificare ripetutamente il valore di una o più variabili e questo sarebbe in contrasto con l’immutabilità.
Scommetto che avete già intuito la soluzione al nostro problema dei loop. Basta usare un algoritmo ricorsivo.
Questo perché, come è facile capire, gli algoritmi ricorsivi non modificano il valore delle variabili ma effettuano i calcoli sulle copie di valori che vengono passati di chiamata in chiamata.
Lo so, inizialmente è piuttosto sconcertante, ma si tratta prevalentemente della paura di uscire dalla nostra comfort zone e avventurarci nell’ignoto. Mano a mano che ne farete uso scoprirete di apprezzare sempre di più le chiamate ricorsive.
L’immutabilità garantisce tantissimi vantaggi, pensate ad esempio a cosa succede quando si programma un software multi-threaded che fa chiamate a funzioni con side-effect. La chiamata di una funzione in un thread potrebbe cambiare il valore su cui una funzione di un’altro thread sta per fare dei calcoli, causando un errore imprevisto, intermittente e difficilissimo da debuggare.

Introduzione alla programmazione funzionale

Riparti da zero

L’approccio alla programmazione funzionale può essere inizialmente molto faticoso.
Il problema principale è legato al fatto che solitamente non è il primo tipo di linguaggio che si studia, e gli utenti cercano di ricondurre le nuove nozioni alle tecniche di programmazione che conoscono. Tendenzialmente questa non è una buonissima idea, un po’ come se per imparare ad andare in biciclette si cercasse di associare la pedalata alla camminata o alla corsa.
Si tratta si sempre di due metodi per deambulare, ma la pratica è molto diversa. Andando in bici bisogna usare le mani per regolare la direzione ed effettuare un movimento rotatorio con le game per andare avanti, molto poco in comune con la camminata.
Lo stesso vale per la programmazione funzionale. Questo perché il programmatore medio che ci si approccia non è al suo primo cambio di linguaggio. Imparare il primo linguaggio di programmazione è inizialmente dura, bisogno imparare a ragionare per algoritmi, a suddividere i problemi complessi in una composizione di problemi più semplici.
Quando però si passa ad apprendere un altro linguaggio il tutto è molto più semplice. Un po’ come quando si impara a guidare e in seguito si cambia automobile, è necessario del tempo per regolarsi, capire quale leva attiva i tergicristalli e quale i fari, ma dopo un poco di adattamento si può continuare ad applicare la propria forma mentis in modo sostanzialmente invariato.

La cosa importante quando ci si approccia alla programmazione funzionale è partire dal presupposto che sia necessario ripartire da zero.
Bisogna imparare a pensare, a risolvere i nostri puzzles, in modo diverso.

Ma cos’è la programmazione funzionale?

Wikipedia definisce la programmazione funzionale così:
In informatica la programmazione funzionale è un paradigma di programmazione in cui il flusso di esecuzione del programma assume la forma di una serie di valutazioni di funzioni matematiche. Il punto di forza principale di questo paradigma è la mancanza di effetti collaterali (side-effect) delle funzioni, il che comporta una più facile verifica della correttezza e della mancanza di bug del programma e la possibilità di una maggiore ottimizzazione dello stesso. Un uso particolare del paradigma, per l’ottimizzazione dei programmi, è quello di trasformare gli stessi per utilizzarli nella programmazione parallela.

La programmazione funzionale pone maggior accento sulla definizione di funzioni, rispetto ai paradigmi procedurali e imperativi, che invece prediligono la specifica di una sequenza di comandi da eseguire. In questi ultimi, i valori vengono calcolati cambiando lo stato del programma attraverso delle assegnazioni; un programma funzionale, invece, è immutabile: i valori non vengono trovati cambiando lo stato del programma, ma costruendo nuovi stati a partire dai precedenti.

Cerchiamo di fare un po’ di chiarezza, o meglio, poniamo l’accento su ciò che in questa definizione è realmente importante. Tutte le guide, i libri e i tutorial che trattano un’introduzione alla programmazione funzionale iniziano elencando, e spiegando, i principali paradigmi del linguaggio.
Ovviamente questo è un passaggio importante e ci arriveremo anche in questa guida, ma trovo che ci sia un paradigma, o meglio una caratteristica strutturale dei linguaggi funzionali che di fatto è la radice da cui germogliano gli altri paradigmi che caratterizzano il linguaggio.

La programmazione funzionale non ha side-effects
Anche se molti di voi sanno già benissimo di cosa parlo, ad alcuni il termine potrebbe risultare sconosciuto, trovo quindi importante fare un piccolo approfondimento per chiarire di cosa parliamo.
In informatica si dice che una funzione (o un metodo) produce un effetto collaterale quando modifica un valore o uno stato al di fuori del proprio scope.
Una funziona senza side-effect si limita a ricevere dei parametri in input e restituire uno o più valori in output. Questo significa che non modifica il valore di variabili globali o statiche, e che i parametri sono passati per valore e non per referenza. Vale a dire che la funzione lavora sui valori delle variabili che vengono passate senza modificare i valori all’interno delle variabili stesse.

Manca tutto

Nella programmazione funzionale non sono presenti le variabili, non in senso stretto quantomeno. Rimane possibile associare un valore ad un nome, ma non è possibile successivamente modificare questo nome.

x = 2
x = 3

Questo non è un comando lecito nei linguaggi funzionali, anche perché siete forse dei bugiardi? avete appena detto che x è 2 e poi mi dite che x è 3? Mmmm… non me la raccontate giusta voi.
Per abitudine all’interno del paradigma funzionale vengono comunque chiamate variabili quelle che in realtà sono delle costanti.

Non sono inoltre presenti i nostri cari e amati loop, non si possono usare né while for. L’unico modo per creare un loop è usare la ricorsione.

Lo so, siete sconcertati. Vi starete domandando “come cavolo faccio a scrivere un programma senza variabili né cicli?” . Ciò che troverete sorprendente mentre diventate via via più familiari con il paradigma funzionale, è che in realtà non vi servono a nulla. Anzi, sono più spesso fonte di errori e imprecisioni che veramente utili.

Come vedremo nel prossimo articolo, nel quale esamineremo tutte le pietre angolari del paradigma funzionale, è che tutte le limitazioni, all’apparenza insormontabili e che sembrano rendere estremamente esoterica e complessa questa tecnica di programmazione, in realtà rendono i software scritti con questi linguaggi più robusti, semplici, leggibili e manutenibili. Inoltre sono molto più performanti.

Articolo Successivo