Quarta lezione

Soffermiamoci ancora un po' sul concetto di puntatore. Trattandosi di un tipo di dati intrinseco del linguaggio, è possibile applicare ad esso le operazioni aritmetiche. Come vengono interpretate?

   char *pointer;
   char *message="hello";

   pointer = message + 3;

Che cosa stamperebbe un printf("%s", pointer); ?

Possiamo allora interpretare l'accesso agli elementi di un array attraverso un'operazione aritmetica sui puntatori:

   int a[5] = { 0, 1, 2, 3, 4 };
   printf ("a[3] = %d\n",a[3]);
   printf ("a[3] = %d\n",*(a+3));

L'aritmetica dei puntatori "sa" qual è la dimensione del tipo di dati a cui il puntatore si riferisce, per cui "sa" di quanto incrementare il puntatore stesso.

Gli array a più di una dimensione:

Anche in C, come in altri linguaggi, si possono definire ed utilizzare array con più di una dimensione:

int a[5][10];

a[1][3] = 12345;

I dati di un array a più di una dimensione vengono immagazzinati in memoria in una tabella contigua di dimensione pari al prodotto delle dimensioni dell'array (esattamente come faceva il Fortran).

Nel precedente esempio, questo vuol dire che a non è una collezione di 5 puntatori a vettori di 10 interi (int **), ma piuttosto un puntatore ad una collezione di serie di 10 interi. In altre parole, per poter accedere agli elementi di un array multidimensionale occorre conoscere tutte le sue dimensioni salvo la prima.

Proviamo a tradurre l'operazione di espansione del riferimento ad un array multidimensionale in termini di puntatori applicando due volte l'equivalenza sopra descritta:

a[1][3]

equivale a

*(a[1] + 3)

che equivale a

*(*(a + 1) + 3)

Il compilatore sa come calcolare a + 1 perché conosce la seconda dimensione dell'array.

Qual è l'inghippo? Per passare ad una funzione un array a più di una dimensione non basta utilizzare puntatori a puntatori, ma occorre specificare tutte le dimensioni dell'array salvo la prima:

int function(int a[][10]);

int a[5][10];

function(a);

Una piccola parentesi: il linguaggio C è piuttosto tollerante nella conversione fra tipi diversi (ad esempio abbiamo visto che non è necessario specificare in modo diverso le costanti intere e reali). Di fatto la conversione fra tutti i tipi numerici scalari viene effettuata silenziosamente - anche nel caso in cui un tipo con più cifre significative (come un int) viene convertito in un tipo con meno cifre significative (come uno short), con possibile troncamento e perdita di significato. Le regole implicite per la conversione di espressioni dove compaiono vari tipi sono le seguenti (è meglio averle viste almeno una volta nella vita):

1. Tutte le costanti e le variabili intere di dimensione minore di un int vengono convertite in int. Tutte le variabili float vengono convertite in double.
2. Se un operando di un operatore binario è double, anche l'altro operando viene convertito a double, e l'operazione viene eseguita.
3. Se nessuno dei due operandi di un operatore binario è double, ma uno dei due è long, l'altro operando viene convertito a long e l'operazione viene eseguita.
4. Se nessuno dei due operandi di un operatore binario è double o long, ma uno dei due è unsigned, l'altro operando viene convertito a unsigned e l'operazione viene eseguita.
5. Se ambedue gli operandi di un operatore binario sono int, l'operazione viene eseguita senza alcuna conversione.

Queste regole sono piuttosto difficili da memorizzare: in caso di dubbio, è quindi consigliabile scrivere le conversioni in modo esplicito. A tale scopo il linguaggio offre la possibilità di fare type casting, cioè di imporre una conversione ad un altro tipo (ammesso che la stessa sia possibile). Per effettuare il cast di una espressione di un tipo ad un altro tipo, basta farla precedere dal nuovo tipo racchiuso fra parentesi. Ecco un esempio di arrotondamento di un reale all'intero più vicino (in questo caso il cast non sarebbe necessario, ma risulterebbe difficile capire cosa fa il codice):

   float a = 3.579821;
   int b;

   b = (int)(a + 0.5); 

Ecco invece un esempio in cui il cast è necessario:

   unsigned long seconds;
   unsigned long microseconds;
   double time;

   time = seconds + ((double)microseconds) / 1000000;

Un'altra caratteristica qualificante del C è quella di comprendere in modo nativo il supporto per la gestione dinamica della memoria.

Per allocazione dinamica della memoria s'intende la possibilità di riservare, mentre il programma è in esecuzione, un'area di memoria che non era stata riservata all'avviamento del programma.
Molto spesso infatti, non è possibile determinare in fase di compilazione la quantità di dati che un programma deve gestire, e la soluzione di riservare la massima quantità di memoria possibile non è certo ottimale.
Altrettanto spesso, nel corso dell'esecuzione di un programma, si pone il problema di liberare la memoria utilizzata da strutture di dati che sono state utilizzate solo temporaneamente.

Descrivendo la chiamata delle funzioni, abbiamo visto che le variabili locali di una funzione vengono allocate quando la funzione viene chiamata. Questo vuol dire che nella memoria libera deve essere identificato un certo spazio, che viene riservato, utilizzato e poi liberato all'uscita della funzione. Questo avviene in modo dinamico per sua natura: si tratta solo di rendere accessibile al programmatore questo stesso meccanismo, in modo che l'allocazione e la liberazione della memoria non debbano necessariamente coincidere con l'ingresso e l'uscita dalle funzioni.

Le funzioni della libreria C che si occupano di allocare dinamicamente e liberare la memoria sono malloc, realloc e free.

• void *malloc(size_t size); alloca un blocco di memoria di dimensione size byte. (Nota: size_t è un tipo di dati derivato, e di solito è uguale ad un int).
• void *realloc(void *pointer, size_t size); estende il blocco di memoria già allocato a cui punta pointer fino alla dimensione size. Se la nuova dimensione è più piccola di quella richiesta in precedenzai, non succede nulla. Se pointer è uguale a NULL il blocco viene allocato ex-novo (come in malloc). Questa funzione è utile per definire aree di memoria che possono venire riutilizzate, e rende più difficile la creazione involontaria di memory leak.
• void free(void *pointer); libera il blocco di memoria a cui punta pointer, rendendo possibile il riutilizzo della memoria stessa.

Che cosa sono i memory leak ?

Supponiamo di avere una funzione che alloca un blocco di memoria, mette il puntatore in una variabile locale e poi esce senza chiamare free(). Sappiamo che la variabile locale viene persa all'uscita della funzione. Un blocco di memoria di cui si sia perso il puntatore non può più essere liberato, ed ovviamente non può neanche essere utilizzato... Se una funzione di questo tipo viene chiamata parecchie volte, la dimensione della memoria virtuale del programma cresce a dismisura.

E' solitamente molto difficile rintracciare la causa di un memory leak. Bisogna dunque fare attenzione a liberare sempre con free la memoria dinamica che non si usa più. La funzione realloc può essere di aiuto nel prevenire queste "fughe".

L'insieme di alcune caratteristiche del linguaggio che abbiamo finora esaminato (passaggio alle funzioni del valore delle variabili nello stack, e allocazione dinamica delle variabili locali) rende possibile la scrittura di funzioni ricorsive. Le funzioni ricorsive non sono altro che funzioni che chiamano se stesse, e possono essere utili per codificare problemi che risulterebbe problematico (o illeggibile) codificare utilizzando cicli nidificati.
E' infatti sempre possibile e generalmente più efficiente (anche se talvolta arduo) trasformare una funzione ricorsiva in una non ricorsiva, aggiungendo un opportuno numero di cicli.

Esistono alcuni problemi che possono essere facilmente definiti in modo ricorsivo. Ad esempio sappiamo che il fattoriale di un numero è definito dalle seguenti proprietà:

1. 1! = 1
2. n! = n*(n-1)!

Questo però è un problema fin troppo semplice, e la sua implementazione con una funzione ricorsiva, sebbene elegante, potrebbe non essere un'idea molto astuta. Le funzioni ricorsive, nella vita reale, si prestano bene all'uso nell'analisi lessicale (pensiamo ad esempio al pre-processore C), oppure per problemi dove la ricorsione è multipla (come la procedura di quicksort, che vedremo più avanti, oppure come il classico, anche se non molto utile, esempio delle Torri di Hanoi, di cui, per chi lo desidera (ma solo per gioco), ecco un .

Esercizio: Scrivere o immaginare una funzione ricorsiva per il calcolo del fattoriale.