Sintesi e sfide: funzioni

Riepilogo

Questa lezione chiude la quinta unità del corso, dedicata alle funzioni. Ricostruisce la catena dei concetti che va dalla dichiarazione di una funzione alla ricorsione, passando per lo stack delle chiamate, il contratto, il passaggio dei parametri, l’ambito di visibilità e la durata delle variabili e la progettazione per raffinamento successivo; separa ciò che di tutto questo vale in qualsiasi linguaggio da ciò che è proprio di C++; raccoglie il comportamento indefinito dell’unità, con ciò che il compilatore segnala, ciò che il sanitizer ferma e ciò che nessuno segnala; ripete nella sua valutazione d’uscita le abilità della valutazione d’ingresso; e termina con sei sfide che combinano l’intera unità.

Obiettivi di apprendimento

Scomporre un problema in funzioni, ciascuna con la sua interfaccia e il suo contratto (precondizione e postcondizione), e testarle separatamente.
Scegliere il modo di passaggio di ciascun parametro e la forma di restituire i risultati, e giustificare la scelta.
Risolvere un problema per ricorsione e dimostrarne la correttezza per induzione e la terminazione con una misura che decresce, stimandone il costo in chiamate.
Riconoscere il comportamento indefinito dell’unità (il percorso senza return, il riferimento pendente, il risultato che va in overflow, lo stack esaurito) e riscrivere il programma senza di esso.
Separare, in ciò che si è appreso nell’unità, ciò che vale in qualsiasi linguaggio da ciò che è proprio di C++.

Ciò che l’unità ha ottenuto

L’unità si era proposta di insegnare a scomporre un problema in parti con un nome, ciascuna con un’interfaccia e un contratto, e a risolvere problemi per ricorsione. Lo scopo è stato raggiunto appoggiandosi solo su ciò che l’introduzione ha dichiarato di dare per scontato: i cicli dell’unità 4, con il loro invariante e la loro variante, la specifica della lezione 1.1 e il modello della memoria dell’unità 2. Il programma dei numeri amicabili, il cui ciclo copiato sommava i divisori del numero sbagliato, si scrive ora con una sola funzione, verificata una volta rispetto al suo contratto.

Funzioni

La lezione Funzioni ha insegnato a dichiarare, definire e chiamare una funzione, e ha separato tre momenti: in compilazione, ogni chiamata si controlla rispetto a una dichiarazione vista prima; in fase di collegamento, si cerca la definizione; in esecuzione, si calcolano gli argomenti, si crea un frame nello stack delle chiamate e il controllo salta al corpo. Ha mostrato che arrivare alla fine di una funzione che non è void senza un return è comportamento indefinito, e si è chiusa con il contratto, la precondizione e la postcondizione, che ripartisce le responsabilità tra chi chiama e la funzione.

Parametri e ambito di visibilità

La lezione Parametri e ambito di visibilità ha studiato per quali vie entrano i dati ed escono i risultati: il parametro per valore è una copia; il parametro per riferimento, un secondo nome per la cella di chi chiama; il riferimento costante legge senza copiare. Ne segue la regola di scelta (valore per ciò che è piccolo, riferimento costante per ciò che è grande e si legge soltanto, riferimento solo se modificare è lo scopo) e, per più risultati, std::pair e std::tuple con i binding strutturati. Ha distinto l’ambito di visibilità di un nome, proprietà del testo, dalla durata di una variabile, proprietà dell’esecuzione, e si è chiusa con il riferimento che sopravvive alla sua cella.

Progettare con le funzioni

La lezione Progettare con le funzioni ha insegnato a decidere quali funzioni scrivere, per raffinamento successivo: un main breve che chiama funzioni soltanto dichiarate e la discesa in ciascuna di esse, in modo che la scomposizione si disegni come un albero. Ha fissato i criteri di una buona interfaccia e la regola «una funzione, un compito», con i suoi segnali (la congiunzione nel nome, la funzione che non sta in uno schermo, il flag) e gli effetti nascosti, come la variabile globale; ha presentato l’overloading, con il suo ordine di preferenza e la chiamata ambigua; e ha riscritto gli algoritmi dell’unità 4 come funzioni testate separatamente.

Ricorsione

La lezione Ricorsione ha insegnato che una funzione può chiamare sé stessa per risolvere un’istanza più piccola del problema. Ha dimostrato la correttezza per induzione, supponendo corretta la chiamata più piccola, e la terminazione con una misura naturale che decresce; ha seguito con lo stack i frame che si impilano e si disfano, e ha mostrato come lo stack si esaurisce; ha avvertito che il tipo del risultato va in overflow molto prima dello stack; e ha confrontato Fibonacci ricorsivo e iterativo: $2\,692\,537$ chiamate contro 29 somme per $F_{30}$ .