Un rasoio per diminuire la complessità ciclomatica dei programmi
Reduce, conosciuta in alcuni linguaggi come fold o accumulate, è una funzione di ordine superiore, cioè in grado di accettare un’altra funzione come parametro. Costituisce, assieme a map, uno dei pilastri della programmazione funzionale, nonostante sia largamente utilizzata anche nella maggior parte dei linguaggi basati sulla programmazione orientata agli oggetti o procedurali.
Il suo compito è di ridurre una struttura di dati ricorsiva (solitamente un array) a un solo risultato, tramite l’applicazione di una o più operazioni a ogni suo membro. Array (o vettore) è il termine che indica un insieme di elementi, tipicamente rappresentato con una sintassi del tipo x = [1, 2, 3, 4, 5]. In questo caso, x è un array che contiene i numeri interi da uno a cinque.
Immaginando di voler sviluppare (in pseudo-codice) un programma che ritorni la somma dei numeri contenuti nella lista, si è abituati a scrivere in questo modo:
function sumElements(Array arr): Int {
sum = 0
for(i in arr){
sum += arr[i]
}
return sum
}
print(sumElements([1,2,3,4,5]))
Note per i meno pratici:
– La prima riga definisce la funzione dandole un nome, indicando tra parentesi cosa accetta in ingresso e dopo i due punti cosa ritorna in uscita.
– Il costrutto “for” cicla tra tutti i membri dell’array.
– Il simbolo “+=” somma il valore a sinistra con quello di destra e lo assegna alla variabile di sinistra.
Abbiamo “ciclato” tutti gli elementi, aggiornando di volta in volta la variabile sum, che alla fine viene restituita. Con l’ultima operazione stampiamo il risultato della funzione applicata all’esempio di poco fa.
Avremmo potuto scrivere una funzione equivalente (immaginiamo di usare un linguaggio nel quale si possono applicare funzioni direttamente all’array) in questo modo:
function sum(Int a, Int b): Int {
return a+b
}
print([1,2,3,4,5].reduce(sum))
Oltre all’evidente riduzione delle righe necessarie alla scrittura del codice, abbiamo diversi vantaggi nell’utilizzo di questo costrutto.
La somma è applicata a ogni singolo elemento dell’array, permettendoci di tipizzare (definire il tipo di dato: Int(ero), String(a), Array, …) entrambi i parametri e ridurre la possibilità di comportamenti indesiderati.
Proviamo a immaginare cosa accadrebbe a passare un array misto, come [1,2,’a’] alle due funzioni?
Nel primo caso potremmo avere un risultato indesiderato nonostante il lampante errore (quanto fa la somma fra l’intero tre e il carattere a? Va ignorata la stringa, così da avere tre come risultato, oppure va valutato il codice del carattere unicode inserito?).
Nel secondo avremmo istantaneamente un errore, poiché abbiamo specificato direttamente nella dichiarazione della funzione che esigiamo due interi come parametri.
Ovviamente non c’è nessun bisogno di nominare una funzione per eseguire un’operazione così semplice, per cui è possibile passare direttamente una lambda function al nostro reduce.
print([1,2,3,4,5].reduce(function (Int a, Int b): Int { return a+b }))
Abbiamo risolto il problema utilizzando una sola linea (attenzione: questo non è per forza un vantaggio, mantenete il vostro codice leggibile e ordinato!), utilizzando una funzione anonima non dichiarata (è questo il significato di lambda function) e senza inizializzare nessuna variabile. Dopo l’esecuzione di questa riga non rimarrà nulla in memoria… hurrà!
Internamente è come se venisse eseguito un normale loop, all’interno del quale viene chiamata la funzione su ogni singolo elemento, trasportando il risultato dei cicli precedenti. Alla prima interazione il primo parametro ha valore nullo, oppure va impostato, a seconda del linguaggio utilizzato. Il secondo parametro contiene il primo valore della lista, cioè 1. Viene eseguita l’operazione e si passa al giro successivo, dove vengono passati, rispettivamente, il risultato precedentemente calcolato e il prossimo membro dell’array, quindi 2. Si procede così fino all’esaurimento della lista, dove avremo in ritorno il risultato finale. Per questo motivo il primo parametro è normalmente chiamato accumulator. Proviamo a utilizzare il riduttore in un esempio più complesso:
colors = ['giallo','blu','giallo','
rosso','blu','verde','blu']
countedColors = colors.reduce(function(
Array accumulator, String color)
{
if(!accumulator.has(color)){
accumulator[color] = [
'name' => color,
'votes' => 0
]
}
accumulator[color]['votes']++
return accumulator
}, [])
mostVotedColor = countedColors.reduce(
function(Array accumulator, Array
color){
if(accumulator['votes'] > co
lor['votes'])
return accumulator
return color
}, ['name' => 'nessuno', 'votes' =>
0])
sprintf('il colore più votato è il %s,
con %i voti', mostVotedColor['name'],
mostVotedColor['votes'])
Note per i meno pratici:
– Il punto esclamativo serve a negare una condizione, per cui verifichiamo se l’accumulator possiede già un membro di quel colore e, in caso negativo, lo creiamo.
– L’operatore > verifica se il primo valore è maggiore del secondo.
– L’operatore ++ aumenta di un intero il valore.
Avete capito cosa succede qui? Facciamo un paio di precisazioni prima della spiegazione. Abbiamo utilizzato per comodità un linguaggio che permette di utilizzare le stringhe come chiavi degli array e abbiamo impostato un valore iniziale per gli accumulator, rispettivamente un array vuoto e un default per il colore non votato.
Il programma calcola quale colore ha la frequenza maggiore nella lista data. La prima funzione di riduzione viene utilizzata per trasformare questa lista in un altro array che includa anche la sua frequenza. La seconda restituisce l’elemento con il numero più alto di voti, confrontando di volta in volta il valore del colore rispetto a quello nell’accumulatore. È importante a questo punto notare che l’accumulator può portarsi dietro i vecchi valori, cambiare a ogni esecuzione, oppure venire modificato soltanto al verificarsi di alcune condizioni.
Wall of Code. Ph. Anna Laviosa, © 2017
La riduzione del numero di cicli presenti nel codice grazie a questo tipo di funzioni permette di diminuire la complessità ciclomatica del programma. Presentata nel periodico IEEE Transactions on Software Engineering da Thomas J. McCabe nel 1976, questa complessità viene tuttora utilizzata (talvolta modificata) per calcolare contando il numero di “deviazioni” che il programma deve eseguire rispetto al flusso lineare del codice. Partendo da un punteggio di uno per il percorso standard, si aggiunge un punto per ogni struttura di controllo (alternative if o switch, cicli while o for, …), poiché a ognuna di esse si aprono due o più strade differenti, le quali vanno capite e testate dallo sviluppatore poiché raddoppiano le possibilità di errore.
In matematica questo viene rappresentato tramite un grafo di controllo di flusso orientato, dove ogni ciclo è rappresentato da due nodi di entrata e uscita, intervallati da tre nodi per ogni struttura, con i due archi che tornano verso l’alto per il ciclo e verso il basso per le strutture condizionali. La formula semplice (ne esistono varianti più articolate) per il calcolo della complessità è M = E – N, dove M è la complessità, E gli archi (edges) e N i nodi. Ne consegue che un grafo senza strutture di controllo corrisponde a un punteggio di 1 (2 nodi e 1 arco), mentre si aggiungono 3 nodi e 4 archi per ogni ciclo o condizione, quindi un punto. Nell’algebra lineare, si dice che i vari percorsi che si possono seguire per collegare l’entrata all’uscita sono linearmente indipendenti. La complessità aumenta con l’aumentare delle strade possibili per raggiungere il nodo finale.
Ci troviamo nella versione informatica e ridotta del rasoio di Ockham: mantenere la semplicità del codice, favorire la riusabilità delle funzioni, “non moltiplicare gli elementi più del necessario” sono pratiche utili per ridurre la possibilità di eccezioni e favorire la leggibilità del codice, per quanto a prima vista esso sembri complicarsi. L’utilizzo di funzioni di ordine superiore nei linguaggi orientati agli oggetti permette di avvicinarsi a un mondo in apparenza complesso come quello della programmazione funzionale, prendendo in prestito alcune pratiche che possono migliorare lo sviluppo. Può sembrare poco intuitivo utilizzare funzioni che accettano funzioni come parametri, o che a loro volta ritornano altre funzioni, oppure non riuscire a seguire riga per riga lo sviluppo di una variabile, ammesso che esse non siano addirittura del tutto assenti. La diminuzione di cicli e variabili in favore di piccole funzioni permette di suddividere il codice in porzioni più piccole, più facili da testare unitariamente (il che significa preparare dei test automatici che utilizzano la funzione con dei parametri definiti da noi, facendo delle asserzioni per confrontare il risultato con ciò che ci aspettiamo). La qualità del codice non risiede soltanto nel buon funzionamento o nelle performance, ma anche nella possibilità di essere letto e testato facilmente, nonché di essere mantenuto nel tempo, favorendo le estensioni e le correzioni.
