Esercizio - Hello world, variabili e funzioni (laboratorio 1)

Primo laboratorio del corso di Laboratorio di Programmazione, Ing. Informatica UniPD: compilazione da riga di comando, classi di memorizzazione misurate con size, funzioni con vector, durata delle variabili. Teoria: C++ - introduzione, compilazione e linkingC++ è un linguaggio compilato e standard che dà controllo totale sulla macchina (basso livello) e strumenti di astrazione (alto livello); un programma parte da main, usa gli stream (std::cout << ...) e le direttive del preprocessore (#include); il passaggio da sorgente a eseguibile ha tre fasi, preprocessore (espande #include e macro), compilatore (controlla sintassi e tipi e produce un file oggetto in codice macchina) e linker (unisce i file oggetto e le librerie risolvendo i nomi); gli errori di sintassi e di tipo sono del compilatore, i simboli dichiarati ma non definiti (undefined reference) sono del linker; si compila da riga di comando con g++ -o eseguibile sorgente.cpp -lLibreria.C++ - introduzione, compilazione e linking →, C++ - tipi, variabili, espressioni e dichiarazioniun tipo definisce contenuto, intervallo di valori e operazioni; un oggetto è una regione di memoria con un tipo, il valore è la configurazione di bit letta in base al tipo, una variabile è un oggetto con un nome; inizializzazione (dare il primo valore) e assegnamento (cambiare il valore) sono diversi; le conversioni verso un tipo più capiente sono sicure, quelle verso un tipo meno capiente (narrowing, double->int, int->char) non lo sono e il compilatore le segnala di rado, ma la notazione con graffe {} le vieta; un'espressione calcola un valore da operandi e operatori, un lvalue è ciò che può stare a sinistra di =, constexpr vuole un valore noto in compilazione mentre const solo un valore che non cambia; gli operatori con side effect (++, --, +=) non vanno mischiati con altri usi della stessa variabile nella stessa espressione perché l'ordine di valutazione non è definito; una dichiarazione introduce un nome e un tipo, una definizione fornisce anche l'entità (memoria per una variabile, corpo per una funzione).C++ - tipi, variabili, espressioni e dichiarazioni →, C++ - funzioni, reference e passaggio dei parametriuna funzione ha parametri formali (0 o più, input) e un valore di ritorno (0 o 1, output); in C++ gli argomenti si passano per valore, cioè il parametro è una variabile locale inizializzata con una copia dell'argomento, e modificarla non cambia l'originale; per oggetti grandi (vector, immagini) la copia costa, e si passa per reference (T&), un alias dell'oggetto del chiamante che permette lettura e scrittura, oppure per const reference (const T&), alias in sola lettura verificata dal compilatore, che accetta anche literal (oggetto temporaneo); regola: valore per oggetti piccoli, const T& per grandi da non modificare, T& solo se la funzione deve davvero modificare o produrre più di un output; il passaggio converte l'argomento nel tipo del parametro come in un'inizializzazione e un cast esplicito (static_cast) rende visibile l'intenzione.C++ - funzioni, reference e passaggio dei parametri →, C++ - chiamate a funzione e layout della memoriauna chiamata a funzione crea un record di attivazione (RA) con una copia dei parametri e le variabili locali, impilato nello stack (LIFO) e tolto all'uscita; la dimensione dipende dalle variabili locali e il tempo per inserirlo è costante; il processo ha cinque regioni di memoria: text (istruzioni, spesso read-only), initialized data (globali e statiche inizializzate), uninitialized data o BSS (globali e statiche non inizializzate, azzerate dal sistema), stack (RA) e heap (allocazione dinamica con new e delete); la durata (storage duration) di una variabile è diversa dallo scope: le globali e le static sono statiche (esistono per tutto il programma, inizializzate una volta), le locali sono automatiche (create all'entrata nel blocco, distrutte in ordine inverso all'uscita); le globali sono inizializzate prima del main ma l'ordine fra file diversi non è definito.C++ - chiamate a funzione e layout della memoria →.

Esercizio 1: Hello, world

Testo. Implementare "Hello, world", poi compilarlo ed eseguirlo da riga di comando Linux con il comando g++ visto a lezione. Per eseguirlo: ./<nome eseguibile>.

#include <iostream>

int main()
{
    std::cout << "Hello, World!\n";  // stampa "Hello, World!"
    return 0;
}

g++ -o hello hello.cpp        # preprocessore + compilatore + linker
./hello

Hello, World!

-o hello dà il nome all'eseguibile; senza -o GCC produce a.out. Se il file non compila, g++ indica la riga dell'errore; se compila ma il linker non trova qualcosa si ha un undefined reference (C++ - introduzione, compilazione e linkingC++ è un linguaggio compilato e standard che dà controllo totale sulla macchina (basso livello) e strumenti di astrazione (alto livello); un programma parte da main, usa gli stream (std::cout << ...) e le direttive del preprocessore (#include); il passaggio da sorgente a eseguibile ha tre fasi, preprocessore (espande #include e macro), compilatore (controlla sintassi e tipi e produce un file oggetto in codice macchina) e linker (unisce i file oggetto e le librerie risolvendo i nomi); gli errori di sintassi e di tipo sono del compilatore, i simboli dichiarati ma non definiti (undefined reference) sono del linker; si compila da riga di comando con g++ -o eseguibile sorgente.cpp -lLibreria.C++ - introduzione, compilazione e linking →).

Esercizio 2: variabili e sezioni di memoria

Testo. Partendo da #include <iostream> int main() { return 0; } aggiungere, uno alla volta: a. una variabile int locale automatica; b. una variabile int locale statica inizializzata a un valore diverso da 0; c. una variabile int locale statica non inizializzata; d. una variabile int globale (statica senza bisogno di dirlo) inizializzata a un valore diverso da 0; e. una variabile int globale non inizializzata.

Per ogni passaggio analizzare la dimensione di initialized data segment (data) e uninitialized data segment (BSS): compilare senza linkare con g++ -c <sorgente>.cpp e usare size <sorgente>.o. Rispondere: a) in quale sezione compare la variabile locale automatica, e perché? b) perché è "automatica"? c) cosa succede togliendo l'inizializzazione alle variabili statiche, e perché? d) qual è lo scope di ciascuna variabile?

Il programma finale

Le variabili vanno anche usate, altrimenti il compilatore le potrebbe scartare. La funzione usa() è definita a parte, in usa.cpp: così size misura solo main.o, senza il codice di iostream.

#include <iostream>

void usa(int valore);   // definita in usa.cpp: serve a "usare" le variabili

int g_init = 5;
int g_uninit;

int main()
{
    int a_auto = 1;
    static int s_init = 3;
    static int s_uninit;
    usa(a_auto);
    usa(s_init);
    usa(s_uninit);
    usa(g_init);
    usa(g_uninit);
    return 0;
}

#include <iostream>

void usa(int valore)
{
    std::cout << valore << '\n';
}

Si compila con g++ -o prog main.cpp usa.cpp e stampa i valori delle cinque variabili: 1 3 0 5 0.

1
3
0
5
0

Le misure

Ogni riga della tabella è il programma con le variabili fino a quel punto, compilato con -c (sull'architettura x86-64 Linux). I numeri sono quelli del comando size file.o, riprodotti da un piccolo script perché size non è disponibile in questo ambiente: la colonna text dipende dal compilatore e dal numero di istruzioni, le colonne data e bss sono quelle che interessano.

Il confronto tra passi consecutivi isola l'effetto di ciascuna variabile: ogni int è 4 byte, e finisce nella colonna giusta.

Risposte

a) In quale sezione compare la variabile locale automatica? Perché? In nessuna: dopo il passo 1 data e bss restano a 0 (cresce solo text, per le istruzioni che la inizializzano e la passano a usa). Una variabile automatica non occupa posto nel file oggetto: esiste solo a tempo di esecuzione, nel record di attivazione di main sullo stack (C++ - chiamate a funzione e layout della memoriauna chiamata a funzione crea un record di attivazione (RA) con una copia dei parametri e le variabili locali, impilato nello stack (LIFO) e tolto all'uscita; la dimensione dipende dalle variabili locali e il tempo per inserirlo è costante; il processo ha cinque regioni di memoria: text (istruzioni, spesso read-only), initialized data (globali e statiche inizializzate), uninitialized data o BSS (globali e statiche non inizializzate, azzerate dal sistema), stack (RA) e heap (allocazione dinamica con new e delete); la durata (storage duration) di una variabile è diversa dallo scope: le globali e le static sono statiche (esistono per tutto il programma, inizializzate una volta), le locali sono automatiche (create all'entrata nel blocco, distrutte in ordine inverso all'uscita); le globali sono inizializzate prima del main ma l'ordine fra file diversi non è definito.C++ - chiamate a funzione e layout della memoria →).

b) Perché si chiama "automatica"? Perché nasce e muore da sola: viene creata all'entrata nel blocco (alla chiamata della funzione) e distrutta all'uscita, senza che il programmatore faccia nulla; in pratica è il compilatore a riservarle spazio nel RA e a liberarlo quando il RA sparisce. La contrapposizione è con le variabili static e globali (durata pari a quella del programma) e con la memoria dinamica (new), che va liberata a mano.

c) Cosa succede togliendo l'inizializzazione alle variabili statiche? Perché? Nel programma finale, togliendo = 3 a s_init la variabile passa da data a bss: size dà data = 4 (resta solo g_init) e bss = 12 (s_init, s_uninit, g_uninit), invece di 8 e 8. Stesso risultato con static int s_init = 0;: un valore iniziale zero equivale a nessuna inizializzazione, e finisce nel BSS. Il motivo: nel file eseguibile il data segment deve contenere i valori iniziali; per il BSS basta ricordarne la dimensione, perché il sistema operativo lo azzera prima di partire. Quindi: le variabili statiche non inizializzate valgono 0, e non occupano spazio nel file.

d) Scope di ciascuna variabile.

Scope e durata sono concetti diversi (C++ - scope, namespace e librerielo scope è la regione di testo in cui un nome è valido, dal punto di dichiarazione alla fine dello scope; i tipi di scope sono globale (di file), di classe, locale (blocco o lista argomenti di una funzione), di statement (for) e di namespace; funzioni dentro funzioni sono illegali, le classi locali da evitare; i namespace raggruppano nomi senza creare un tipo e si accedono col nome qualificato namespace::membro oppure con using (la using directive va evitata negli header); un header file è un insieme di dichiarazioni che chi lo include può usare (<> per i file di sistema, "" per quelli del progetto), dev'essere protetto dalle include guard (#ifndef/#define/#endif) per non includere due volte le stesse definizioni; il linker unisce i file oggetto con le librerie, statiche (copiate in ogni eseguibile, self-contained) o dinamiche (una sola copia condivisa, .so su Linux, .dll su Windows, ricompilabili senza toccare gli eseguibili).C++ - scope, namespace e librerie →): la statica locale ha lo scope di una locale e la durata di una globale.

Esercizi 3, 4, 5: print, fibonacci e il massimo di un int

Testo. 3. Scrivere una funzione print() che stampa su cout uno std::vector di int, con due argomenti: una std::string che etichetta l'uscita e il vettore da stampare. 4. Creare un vettore di numeri di Fibonacci e stamparli con print(). Implementare fibonacci(x, y, v, n): x e y sono due int, v è uno std::vector<int> (output) che non si può assumere vuoto (vanno eliminati tutti gli elementi prima di scrivere) e n è il numero di elementi da inserire in v; v[0] è x e v[1] è y. Usare il passaggio per copia o per riferimento come si ritiene più appropriato. (push_back() aggiunge in coda, clear() elimina tutti gli elementi, [] legge e scrive.) 5. Un int può contenere interi solo fino a un valore massimo. Trovare un'approssimazione di tale massimo usando fibonacci().

Svolgimento

Scelta del passaggio, parametro per parametro:

Dentro fibonacci: si fa v.clear(), si inseriscono x e (se n > 1) y, poi ogni elemento è la somma dei due precedenti. Si guardano anche i casi limite n = 0 e n = 1, per non scrivere x o y quando non richiesti.

Per il punto 5 serve una somma che "si avvolga" invece di avere comportamento indefinito: si calcola in long long e si riporta in int (da C++20 la conversione è definita modulo $2^{32}$). La sequenza 1, 2, 3, 5, ... cresce finché il valore sta in un int; alla prima somma troppo grande il risultato diventa negativo, e il primo elemento che non cresce segnala l'overflow: l'elemento precedente è il massimo trovabile con la sequenza.

#include <climits>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

// Stampa l'etichetta e poi il vettore. Il vettore e' passato per const reference (non si copia, non si modifica);
// l'etichetta e' una stringa: stesso criterio.
void print(const string& label, const vector<int>& v)
{
    cout << label << ": {";
    for (size_t i = 0; i < v.size(); ++i) {
        cout << v[i];
        if (i + 1 != v.size()) cout << ", ";
    }
    cout << "}\n";
}

// Riempie v con n numeri della sequenza di Fibonacci che parte da x e y.
// v e' un parametro di OUTPUT: per reference non const. Non si assume vuoto, quindi lo si svuota.
void fibonacci(int x, int y, vector<int>& v, int n)
{
    v.clear();
    if (n > 0) v.push_back(x);
    if (n > 1) v.push_back(y);
    for (int i = 2; i < n; ++i) {
        // la somma si fa in long long e si riporta in int: se supera INT_MAX si "avvolge" (modulo 2^32, definito da C++20)
        long long somma = static_cast<long long>(v[i - 1]) + v[i - 2];
        v.push_back(static_cast<int>(somma));
    }
}

int main()
{
    vector<int> v {99, 99, 99};              // non vuoto: fibonacci() deve svuotarlo
    fibonacci(1, 2, v, 10);
    print("fibonacci(1, 2) con 10 elementi", v);

    // massimo di un int: si genera una sequenza lunga e si cerca il primo elemento che NON cresce piu'
    fibonacci(1, 2, v, 50);
    int ultimo_buono = v[0];
    for (size_t i = 1; i < v.size(); ++i) {
        if (v[i] < v[i - 1]) {               // la somma ha superato il massimo e si e' avvolta
            cout << "il primo elemento sbagliato e' v[" << i << "] = " << v[i] << '\n';
            break;
        }
        ultimo_buono = v[i];
    }
    cout << "ultimo numero di Fibonacci che sta in un int = " << ultimo_buono << '\n';
    cout << "valore vero del massimo (INT_MAX)           = " << INT_MAX << '\n';
    return 0;
}

fibonacci(1, 2) con 10 elementi: {1, 2, 3, 5, 8, 13, 21, 34, 55, 89}
il primo elemento sbagliato e' v[45] = -1323752223
ultimo numero di Fibonacci che sta in un int = 1836311903
valore vero del massimo (INT_MAX)           = 2147483647

Letto: v parte non vuoto ({99, 99, 99}) e fibonacci() lo svuota; i primi dieci numeri sono quelli attesi. Con 50 elementi il primo sbagliato è v[45] (negativo: la somma $1836311903 + 1134903170 = 2971215073$ supera $2^{31}-1$); l'ultimo corretto è $1836311903 \approx 1.84 \cdot 10^9$, che approssima bene il massimo vero $2^{31} - 1 = 2147483647 \approx 2.15 \cdot 10^9$. Il rapporto fra due Fibonacci consecutivi è circa $1.618$: per questo l'approssimazione è sempre entro quel fattore dal massimo. Il valore vero si legge anche da INT_MAX (<climits>).

Esercizio 6: call_counter

Testo. Implementare void call_counter(void); che a ogni chiamata stampa su cout un numero progressivo con il totale delle chiamate effettuate. Che tipo di variabile serve? Qual è la sua durata di memorizzazione? Qual è il suo scope?

#include <iostream>
using namespace std;

void call_counter(void)
{
    static int count = 0;          // durata statica, scope locale: inizializzata UNA volta sola
    ++count;
    cout << "chiamata numero " << count << '\n';
}

int main()
{
    for (int i = 0; i < 3; ++i) call_counter();
    call_counter();
    return 0;
}

chiamata numero 1
chiamata numero 2
chiamata numero 3
chiamata numero 4

Serve una variabile locale statica: static int count = 0;.

• Durata: statica. Esiste per tutta l'esecuzione del programma (nel data o nel bss — = 0 va nel BSS) e viene inizializzata una sola volta, non a ogni chiamata, così mantiene il valore tra una chiamata e l'altra.
• Scope: locale alla funzione: count non si vede da fuori.
• Una variabile automatica (int count = 0; senza static) ripartirebbe da 0 a ogni chiamata e stamperebbe sempre 1. Una variabile globale funzionerebbe ma esporrebbe il contatore a ogni funzione (cattiva pratica).