Stack di Chiamata in Linguaggio C

Una delle proprietà fondamentali del linguaggio C è la capacità di definire e invocare funzioni. Le funzioni permettono di suddividere un programma in parti più piccole e più gestibili, rendendo il codice più leggibile e più manutenibile.

Una funzione può, a sua volta, invocare altre funzioni creando, così, delle catene di chiamata. Per implementare questo meccanismo, ogni processo in memoria dispone di uno Stack di Chiamata o Call Stack. In questa lezione vedremo come funziona lo Stack di Chiamata e come viene utilizzato per gestire le chiamate di funzioni in un programma scritto in linguaggio C.

Funzioni che invocano altre funzioni

Abbiamo visto, nelle precedenti lezioni, che una funzione scritta in linguaggio C può, a sua volta, invocare un'altra funzione. Quest'ultima può, a sua volta, invocare un'altra funzione e così via.

Per capire meglio, prendiamo un esempio pratico. Supponiamo di voler realizzare un programma che calcola l'area di un cerchio. Possiamo realizzare questo programma scomponendolo in tre funzioni:

• main: funzione principale del programma, che si occupa di chiedere all'utente il raggio del cerchio e di stampare a video l'area calcolata;
• calcola_area_cerchio: funzione che calcola l'area del cerchio, data la misura del raggio;
• quadrato: funzione che calcola il quadrato di un numero.

Il programma potrebbe essere scritto in questo modo:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <stdio.h>

// Prototipi delle funzioni
double calcola_area_cerchio(double raggio);
double quadrato(double n);

int main() {
    double raggio, area;

    printf("Inserisci il raggio del cerchio: ");
    scanf("%lf", &raggio);

    area = calcola_area_cerchio(raggio);

    printf("L'area del cerchio di raggio %.2f è %.2f\n", raggio, area);

    return 0;
}

double calcola_area_cerchio(double raggio) {
    double risultato = 3.14159 * quadrato(raggio);
    return risultato;
}

double quadrato(double n) {
    double risultato = n * n;
    return risultato;
}

In questo esempio, la funzione main invoca la funzione calcola_area_cerchio, che a sua volta invoca la funzione quadrato. Abbiamo, in pratica, una catena di chiamate di funzioni.

Proviamo a vedere, in pratica, cosa accade quando il programma viene eseguito:

1. La funzione main viene invocata dal sistema operativo.
2. La funzione main invoca la funzione calcola_area_cerchio alla riga 13;
3. La funzione calcola_area_cerchio invoca la funzione quadrato alla riga 21;
4. La funzione quadrato calcola il quadrato del raggio e restituisce il risultato alla funzione calcola_area_cerchio;
5. La funzione calcola_area_cerchio riprende la propria esecuzione nel punto in cui era stata interrotta, moltiplica il risultato ottenuto dalla funzione quadrato per il valore di π e restituisce il risultato alla funzione main;
6. La funzione main riprende la propria esecuzione nel punto in cui era stata interrotta, assegna il risultato ottenuto dalla funzione calcola_area_cerchio alla variabile area e stampa il risultato a video.

Osservando bene la sequenza di passi appena descritta notiamo che, in qualche modo, il programma, ogniqualvolta invoca una funzione, deve ricordarsi il punto in cui si trova all'interno della funzione chiamante.

Ad esempio, al punto 2, quando la funzione main invoca la funzione calcola_area_cerchio, il programma deve ricordarsi che, una volta terminata l'esecuzione della funzione calcola_area_cerchio, deve riprendere l'esecuzione dalla riga 14 della funzione main. Se non memorizzasse questa informazione, il programma non saprebbe come proseguire al punto 6.

Analogamente, il programma deve, in qualche modo, memorizzare l'informazione al punto 3, in modo da poter riprendere l'esecuzione della funzione calcola_area_cerchio al punto 5.

Come fa il nostro programma a memorizzare queste informazioni?

Per rispondere a questa domanda riprendiamo lo schema che abbiamo introdotto nella lezione sui programmi e processi. In quella lezione abbiamo detto che ad un processo in memoria vengono assegnate quattro aree di memoria o meglio segmenti di memoria.

Finora ne abbiamo visti due: il segmento Testo che contiene le istruzioni del programma, e il segmento Dati che contiene le variabili globali.

Il terzo segmento di memoria è il Segmento Stack o Stack di Chiamata. Questo segmento di memoria è utilizzato proprio per memorizzare le informazioni necessarie a riprendere l'esecuzione di una funzione chiamante, una volta terminata l'esecuzione di una funzione chiamata.

In questa lezione ci occuperemo proprio di questo segmento di memoria, il Segmento Stack in quanto è fondamentale per capire come funzionano le chiamate di funzioni in linguaggio C.

Ma prima di poter capire come funziona, dobbiamo chiarire un concetto fondamentale: cos'è uno Stack?.

Cos'è uno Stack?

Uno Stack, in italiano Pila, è una struttura dati fondamentale in Informatica. Uno Stack è una struttura dati dinamica che permette di memorizzare e recuperare dati in modo particolare.

Essa è alla base di molti algoritmi più complessi e, in particolare, è utilizzata per gestire le chiamate di funzioni in un programma. Il linguaggio C sfrutta sotto il cofano uno Stack per gestire le chiamate di funzioni.

Per capire come funziona dobbiamo uno scaffale verticale dove possiamo impilare degli oggetti. Questo scaffale è inizialmente vuoto:

Su questo scaffale sono possibili solo due operazioni:

• Push: inserisce un nuovo oggetto in cima allo scaffale;
• Pop: rimuove l'oggetto dalla cima dello scaffale.

Quando si inserisce un oggetto in cima allo scaffale, si dice che si è effettuato un Push. Quando si rimuove l'oggetto dalla cima dello scaffale, si dice che si è effettuato un Pop.

Supponiamo di voler inserire tre oggetti in uno Stack, nell'ordine A, B e C.

Prima effettuiamo un Push dell'oggetto A:

Poi effettuiamo un Push dell'oggetto B:

Come si può vedere, l'oggetto B si posiziona subito sopra l'oggetto A. In altre parole si impila sopra l'oggetto A. Da qui il nome Stack o Pila.

Infine effettuiamo un Push dell'oggetto C:

Adesso abbiamo una pila di tre oggetti. Tra questi, l'oggetto C si trova in cima. Proprio come quando si ha una pila di libri o una pila di piatti, l'oggetto che si trova in cima è l'ultimo inserito.

A questo punto, se effettuiamo un Pop, ossia andiamo a rimuovere un elemento dallo Stack, l'elemento che verrà estratto non sarà il primo che avevamo inserito, ossia A, ma quello in cima che in questo caso è C.

Se ci pensiamo, anche quando prendiamo un libro da una pila di libri, non possiamo rimuovere un elemento in mezzo o in fondo... Altrimenti la pila rischia di cascare. Possiamo rimuovere solo partendo dall'elemento in cima.

Se effettuiamo un altro Pop, verrà estratto l'elemento B.

Se, a questo punto effettuiamo il Push di un nuovo elemento, ad esempio D, otteniamo:

E se effettuiamo un Pop, verrà estratto l'elemento D che è l'ultimo inserito.

Per riassumere, uno Stack è una struttura dati che permette di memorizzare e recuperare dati in modo LIFO (Last In First Out), ossia L'ultimo ad entrare è il primo ad uscire.

Stack di Chiamata

Adesso che sappiamo cos'è, in generale, uno Stack, possiamo analizzare come funziona lo Stack di Chiamata in linguaggio C.

Lo Stack di Chiamata o Call Stack è un'area di memoria dinamica che viene utilizzata per memorizzare le informazioni necessarie a gestire le chiamate a funzioni.

Riprendiamo l'esempio di sopra del programma che calcola l'area di un cerchio:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <stdio.h>

// Prototipi delle funzioni
double calcola_area_cerchio(double raggio);
double quadrato(double n);

int main() {
    double raggio, area;

    printf("Inserisci il raggio del cerchio: ");
    scanf("%lf", &raggio);

    area = calcola_area_cerchio(raggio);

    printf("L'area del cerchio di raggio %.2f è %.2f\n", raggio, area);

    return 0;
}

double calcola_area_cerchio(double raggio) {
    double risultato = 3.14159 * quadrato(raggio);
    return risultato;
}

double quadrato(double n) {
    double risultato = n * n;
    return risultato;
}

Quando il programma viene eseguito, il sistema operativo crea un processo in memoria e assegna un segmento di memoria Stack inizialmente vuoto al processo stesso.

Il processo inizia la propria esecuzione partendo dall'inizio della funzione main e, ad un certo punto, raggiunge la riga 13 dove invoca la funzione calcola_area_cerchio.

Per poter invocare la funzione area_cerchio, il processo deve memorizzare le informazioni necessarie a riprendere l'esecuzione a partire dalla riga 14. In realtà, a voler essere precisi, il processo dovrebbe riprendere l'esecuzione a partire dall'assegnamento della variabile area alla riga 13, ma tralasciamo questo dettaglio.

Per memorizzare questa informazione, il processo effettua un Push nello Stack di Chiamata. In particolare, il processo memorizza l'indirizzo dell'istruzione successiva alla chiamata di funzione, ossia l'indirizzo della riga 14. Quindi, lo Stack di Chiamata conterrà l'indirizzo della riga 14:

Fatto questo, il processo salta all'inizio della funzione calcola_area_cerchio e inizia l'esecuzione della funzione stessa.

Quando la funzione calcola_area_cerchio raggiunge la chiamata di funzione alla funzione quadrato, il processo deve memorizzare l'indirizzo dell'istruzione successiva alla chiamata di funzione, ossia l'indirizzo della riga 21. Quindi effettuerà una seconda Push nello Stack di Chiamata:

Il processo salta poi alla funzione quadrato. Questa funzione non ha chiamate a funzioni al proprio interno. Quindi effettua i suoi calcoli e raggiunge l'istruzione return alla riga 27.

Quando il processo raggiunge questa riga deve restituire il controllo alla funzione chiamante, ossia calcola_area_cerchio. Per fare ciò, il processo effettua un Pop dallo Stack di Chiamata. In particolare, il processo estrae l'indirizzo memorizzato nello Stack di Chiamata e salta a quell'indirizzo, ossia alla riga 21:

Fatto questo, la funzione calcola_area_cerchio riprende la propria esecuzione dalla riga 21 e calcola il risultato. Quando raggiunge l'istruzione return alla riga 17, il processo deve restituire il controllo alla funzione chiamante, ossia main.

Per fare ciò, il processo effettua una seconda Pop dallo Stack di Chiamata. In particolare, il processo estrae l'indirizzo memorizzato nello Stack di Chiamata e salta a quell'indirizzo, ossia alla riga 14:

Finalmente, la funzione main riprende la propria esecuzione dalla riga 14 e assegna il risultato ottenuto dalla funzione calcola_area_cerchio alla variabile area.

Infine, quando la funzione main raggiunge l'istruzione return alla riga 18, il processo termina la propria esecuzione e rilascia la memoria occupata.

Come si può osservare, le caratteristiche peculiari di uno Stack sono fondamentali per gestire le chiamate di funzioni in un programma. Grazie ad esso, anche se non viene manipolato direttamente da uno sviluppatore, è possibile innestare chiamate di funzione all'interno di altre chiamate di funzione in modo trasparente.

Quest'ultimo è un punto fondamentale e può essere riassunto in due concetti:

1. Ogni Processo in Memoria ha uno stack che gestisce le chiamate a funzioni;
2. Gli sviluppatori non accedono direttamente ad esso. La sua gestione è trasparente e automatica. Tuttavia, è fondamentale capire come funziona per scrivere programmi efficienti e corretti.

Stack Frame

Abbiamo visto che lo Stack di Chiamata viene adoperato per salvare, ad ogni chiamata di funzione, l'indirizzo dell'istruzione successiva alla chiamata di funzione. Ma non solo.

In realtà, lo Stack di Chiamata è molto potente e versatile. Esso permette di memorizzare molte altre informazioni utili per gestire le chiamate di funzioni.

In particolare, esso viene utilizzato per:

• Memorizzare i parametri passati alla funzione chiamata;
• Memorizzare le variabili locali della funzione chiamata.

Quindi, ogni volta che viene invocata una funzione, il processo salva sullo stack una serie di informazioni che prendono collettivamente il nome di Stack Frame o, in italiano, Record di Attivazione.

Per capire come è fatto uno Stack Frame, riprendiamo l'esempio dell'area del cerchio.

Inizialmente, lo stack di chiamata è vuoto. Quando il processo, dalla funzione main invoca la funzione calcola_area_cerchio, il processo deve salvare sullo stack dapprima l'indirizzo della riga 14:

Ma non solo. Deve anche salvare sullo stack il valore del parametro raggio passato alla funzione calcola_area_cerchio. In questo caso, il valore di raggio è 5. Quindi, lo Stack Frame conterrà anche il valore 5:

Fatto questo, il processo salta all'inizio della funzione calcola_area_cerchio e inizia l'esecuzione della funzione stessa.

La funzione calcola_area_cerchio però utilizza al proprio interno una variabile locale, ossia la variabile risultato. Questa variabile ha una durata di vita pari alla durata di esecuzione della funzione calcola_area_cerchio. In altre parole, esiste soltanto per tutto il tempo in cui la funzione calcola_area_cerchio è in esecuzione.

Quindi, il processo sfrutta lo Stack Frame anche per riservare lo spazio necessario per memorizzare la variabile risultato:

Fatto questo, per comodità il processo salva anche il cosiddetto Base Pointer o Frame Pointer. Questo puntatore punta all'indirizzo di ritorno memorizzato nello Stack Frame. In pratica, il Base Pointer punta all'inizio dello Stack Frame. Lo scopo del Base Pointer è quello di permettere l'accesso immediato all'indirizzo di ritorno quando la funzione chiamata termina la propria esecuzione:

Fatte queste operazioni, la funzione calcola_area_cerchio può cominciare la propria esecuzione.

Per cui, in generale, uno Stack Frame è composto da:

Analogamente, quando la funzione calcola_area_cerchio invoca la funzione quadrato, il processo creerà un secondo Stack Frame per la funzione quadrato:

Quando la funzione quadrato termina la propria esecuzione, il processo, sfruttando il Base Pointer, ricava subito l'indirizzo di ritorno e può cancellare o ripulire lo Stack Frame della funzione quadrato:

E così via, per ogni chiamata di funzione. Per cui anche quando esce dalla funzione calcola_area_cerchio, il processo può cancellare o ripulire lo Stack Frame della funzione calcola_area_cerchio:

Da ciò possiamo ricavare un'importante conseguenza:

Le variabili locali, quindi, risiedono sullo Stack di Chiamata a differenza delle variabili globali che risiedono nel Segmento Dati.

In Sintesi

In questa lezione abbiamo visto come funziona lo Stack di Chiamata in linguaggio C.

In particolare abbiamo studiato che:

• Lo Stack di Chiamata è un'area di memoria dinamica che viene utilizzata per memorizzare le informazioni necessarie a gestire le chiamate di funzioni;
• Esso viene utilizzato per memorizzare gli indirizzi delle istruzioni da cui riprendere l'esecuzione una volta che termina l'esecuzione di una funzione;
• Ogni chiamata di funzione crea uno Stack Frame che contiene le informazioni necessarie per gestire la chiamata di funzione, in particolare l'indirizzo di ritorno, i parametri passati alla funzione e le variabili locali della funzione;
• Le variabili locali di una funzione sono memorizzate nello Stack Frame della funzione stessa e vengono rimosse dalla memoria quando la funzione termina la propria esecuzione.

Inoltre, abbiamo visto che lo Stack di Chiamata è una struttura dati fondamentale per gestire le chiamate di funzioni in un programma. Anche se non viene manipolato direttamente da uno sviluppatore, è fondamentale capire come funziona per scrivere programmi efficienti e corretti.