Elementi Fondamentali 1

Scritto da

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…

Purezza

Scritto da

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.

Immutabilità

Scritto da

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.