Torna alla pagina di Programmazione degli Elaboratori
:: Capitolo 3: Programmazione strutturata ::
1 Principi della programmazione strutturata
2 I linguaggi di alto livello
La programmazione strutturata rappresenta la naturale estensione dell'approccio top-down al processo di scrittura del codice.
I compiti elementari di un programma strutturato sono le attività di processo, mentre i requisiti non elementari sono le attività di gestione.
In generale, ciascuna attività di gestione comprende un costrutto di controllo applicato ad un'attività di livello più basso. Se un'attività di gestione contiene più di un costrutto di controllo, allora dovrebbe essere scomposta in almeno due attività di livello inferiore. L'idea è quella di scomporre il codice in parti più semplici, senza lasciare che i dettagli di ciascuno interferiscano con lo sviluppo del programma nel suo complesso. Tra i costrutti di controllo fondamentali, quelli ammessi sono:
Una volta effettuata la scomposizione è necessario integrare tutte le attività in componenti funzionali chiamati moduli. Gli elementi da tenere in considerazione per la scelta delle attività da integrare nello stesso modulo sono:
I linguaggi di alto livello sono linguaggi che non richiedono al programmatore di “abbassarsi” al livello della macchina, ma cercano di fornire uno strumento di programmazione che mascheri i suoi dettagli specifici e di avvicinarsi, per quanto possibile, al modo di ragionare del programmatore stesso.
Un programma di alto livello dovrà essere comunque tradotto nel linguaggio macchina per essere eseguito. Si possono quindi distinguere linguaggi interpretati e linguaggi compilati a seconda che questa operazione venga svolta da un interprete o da un compilatore. Vi sono anche casi intermedi, come quello di Java, nei quali il codice viene prima compilato in un linguaggio intermedio di più basso livello (bytecode) e quindi interpretato da un apposito interprete (Java Virtual Machine).
Alcuni vantaggi dei linguaggi di programmazione di alto livello sono:
Un linguaggio di programmazione di alto livello strutturato è caratterizzato da:
Un paradigma di programmazione definisce il modo in cui il programmatore concepisce e percepisce il programma. I principali tipi di paradigmi di programmazione per i linguaggi di alto livello sono:
È molto importante nella programmazione la classificazione delle variabili in base alle loro caratteristiche rilevanti, in quanto le operazioni che si possono effettuare su un tipo di dato non sono in generale altrettanto possibili su altri tipi. Per questo motivo nella maggior parte dei linguaggi di alto livello si presuppone che ogni dato, variabile, espressione e funzione appartenga ad un certo tipo.
Il tipo di un dato caratterizza e definisce l'insieme dei valori a cui può appartenere una costante, o dei valori che può assumere una variabile o un'espressione o che può restituire una funzione.
Nei linguaggi di programmazione è necessario ricorrere a metodi espliciti e inequivocabili per identificare il tipo di un dato. La soluzione più largamente adottata è che ogni entità venga manipolata dal programma debba essere prima di tutto dichiarata. Una dichiarazione introduce esplicitamente una nuova costante, variabile, funzione, ecc. assegnandole un nome univoco e un tipo tra quelli disponibili, predefiniti dal linguaggio o definiti dal programmatore.
Abbiamo già detto come i linguaggi di alto livello abbiano tra i loro compiti quello di mascherare al programmatore i dettagli della macchina, permettendogli in questo modo di concentrarsi sul codice.
Uno di questi dettagli è la gestione della memoria. Se per i “dati statici” (quelli dichiarati al momento della scrittura del programma) la gestione viene svolta in modo automatico da tutti i linguaggi di alto livello, per i “dati dinamici” (quelli allocati durante l'esecuzione, secondo una logica non prevedibile al momento della scrittura) i vari linguaggi differiscono spesso per il supporto che offrono.
In questo capitolo verranno fornite alcune conoscenze di base per C, C++ e Java.
Per corredare il codice di commenti, è sufficiente delimitare questi ultimi tra i due simboli: /* e */. In C++ e Java è possibile inserire commenti di un'unica riga precedendoli con: //.
In un linguaggio fortemente tipato (come C, C++ e Java) ogni variabile o espressione ha un tipo che è già noto al momento della compilazione, e quindi prima dell'esecuzione. Questa caratteristica aiuta il programmatore ad evitare errori comuni e ad effettuare controlli sulla compatibilità dei tipi nelle espressioni e negli assegnamenti.
Tipi e variabili hanno identificatori, costituiti da una qualsiasi sequenza di lettere alfabetiche, simbolo “_” e cifre. Gli identificatori non possono però avere una cifra come primo carattere, né possono coincidere con una parola chiave o riservata del linguaggio. Identificatori validi possono essere ad esempio: parola, numero, c4s4, _return, a3_sei.
Ogni variabile deve essere dichiarata prima di essere usata, con questa forma:
<id_tipo> <id_variabile>;
dove id_tipo è il tipo predefinito o definito dal programmatore, mentre id_variabile è l'identificatore. Esempi di tipi predefiniti in C, C++ e Java sono int, char e double.
L'assegnamento consiste nell'attribuire un valore ad una variabile. Ha questa forma:
<id_variabile> = <espressione>;
Un'espressione è costruita combinando costanti, identificatori di variabili, invocazioni di funzioni o metodi, operatori e parentesi tonde, queste ultime necessarie per specificare la priorità degli operatori. È importante che ogni operatore sia applicato a sottoespressioni del tipo appropriato, e che gli argomenti delle funzioni siano del tipo giusto o compatibile.
Un assegnamento restituisce il valore assegnato alla sua variabile al membro sinistro, e in virtù di questo fatto può essere utilizzato a sua volta all'interno di un'espressione. Sono dunque possibili assegnamenti come i seguenti:
x = y = z = 0.0;
d = (e = (top – bottom)/2) + 1
Esistono poi una serie di operatori combinati con l'assegnamento della forma “(operatore)=” (come “+=”, “*=” o “-=”), che permettono di abbreviare certi tipi di assegnamenti che modificano il valore di una variabile in funzione del suo valore precedente. Ad esempio “x += 3” significa “x = x + 3”.
Un'ulteriore abbreviazione sono gli operatori di incremento “+ +” e di decremento “- -”, che possono essere prefissi o suffissi a un identificatore di variabile intera a seconda che si voglia effettuare l'incremento (o il decremento) prima o dopo la fine dell'istruzione.
I vettori (o array) sono delle entità analoghe alle tabelle, definibili e gestibili da tutti i linguaggi di alto livello. Sono caratterizzati da una dimensione, corrispondente al numero di componenti di cui il vettore è formato, specificata tra parentesi quadre.
I linguaggi C, C++ e Java permettono di costruire vettori costituiti da tipi di base o definiti dal programmatore. Per esempio un vettore di dieci interi si definisce come: int x[10];
Da notare che gli indici dei componenti del vettore partono da 0, il che significa che se un array ha dimensione n, la sua ultima componente ha indice n-1.
È possibile definire vettori multidimensionali semplicemente aggiungendo tra quadre la grandezza della dimensione successiva. Per esempio una tabella di interi di quattro righe e sei colonne avrà come dichiarazione: int x[4][6];
Tutti i linguaggi di alto livello permettono la gestione dei sottoprogrammi, distinguendoli in:
Quindi: le funzioni restituiscono un valore, le procedure no.
Le funzioni si dichiarano con la seguente sintassi:
<tipo> <nome_funzione> (<argomenti>) {
<corpo>
}
dove <tipo> è il tipo del risultato della funzione (o la parola chiave void, per le procedure) e <argomenti> è una lista di zero o più dichiarazioni di argomenti separate da virgole.
I costrutti di controllo permettono di combinare tra loro istruzioni elementari creando così istruzioni complesse o blocchi di istruzioni. In questo capitolo verranno analizzati quelli di C, C++ e Java.
L'esecuzione in sequenza consiste nell'esecuzione di un'istruzione dopo l'altra. È possibile creare una sequenza o blocco di istruzioni scrivendole in successione e racchiudendole tra parentesi graffe: { } .
I costrutti iterativi permettono l'esecuzione di un ciclo, ovvero la ripetizione in modo controllato di un determinato blocco di istruzioni.
Il tipo di iterazione più semplice è la while:
while (<condizione>)
La condizione viene controllata all'inizio di ogni iterazione e l'istruzione viene eseguita solo se la condizione è verificata. Nel momento in cui la condizione non è più verificata l'esecuzione dell'iterazione viene interrotta.
Il do...while permette l'esecuzione dell'istruzione prima del controllo della condizione, quindi almeno una volta:
do
while (<condizione>)
Se il numero di iterazioni è noto a priori, è possibile utilizzare il costrutto for:
for (<inizializzazione>; <condizione>; <incremento>)
Il for è semanticamente equivalente ad un ciclo while così strutturato:
<inizializzazione> while (<condizione>) {
}
Il for viene considerato zucchero sintattico, ovvero un costrutto che non aggiunge di per sé nulla alla potenza espressiva di un linguaggio, ma che abbrevia la scrittura di determinati costrutti molto comuni e ricorrenti, rendendo più chiari i programmi.
Esistono due istruzioni di salto controllate:
I costrutti di selezione possono essere di due tipi fondamentali:
condizione binaria;
di un'espressione scalare. Sono il corrispondente della tecnica delle tabelle di salto.
La sintassi della selezione binaria è la seguente:
if (<condizione>)
else
Se la condizione è verificata viene eseguita l'istruzione1 (o il blocco di istruzioni1), altrimenti viene eseguita l'istruzione2 (o il blocco di istruzioni2). Se non è prevista un'alternativa, il ramo else può anche essere omesso.
La sintassi della selezione tra n alternative ha invece la seguente sintassi:
switch (<espressione>) {
}
Il Teorema di Böhm-Jacopini (o “di struttura”) costituisce una giustificazione matematica all'abbandono di uno stile di programmazione che faceva uso dei salti a favore della programmazione strutturata.
Tale teorema dimostra che è possibile realizzare qualsiasi algoritmo senza utilizzare alcuna istruzione di salto, disponendo dei tre soli costrutti di controllo: sequenza, iterazione e selezione.
Unico “contro” della programmazione strutturata è che in alcuni casi un programma senza salti può essere meno efficiente di un equivalente programma con salti.
Una dimostrazione alternativa del Teorema di Böhm-Jacopini è la trasformazione di Ashcroft e Manna.
L'idea che sta alla base di tale dimostrazione è che è sempre possibile trasformare un qualsiasi programma con salti in un unico ciclo while contenente tanti if.
Il Teorema di Böhm-Jacopini dimostra che è possibile realizzare qualsiasi algoritmo utilizzando i tre soli costrutti di esecuzione in sequenza, iterazione e selezione, ma in realtà sono sufficienti i primi due. Una selezione può essere infatti trasformata in un costrutto di iterazione in cui l'iterazione viene effettuata al massimo una volta, sempre che la condizione di entrata sia verificata.
Una struttura dati è un modo sistematico di organizzare i dati utilizzati da un algoritmo e di accedere ad essi.
Così come una struttura dati dipende dall'algoritmo che la deve utilizzare, un algoritmo dipende dalle strutture dati che utilizza; il loro sviluppo deve dunque andare di pari passo.
Progettare strutture dati inadeguate rende la progettazione dell'algoritmo molto più complessa di quanto in realtà potrebbe essere.
Le strutture permettono di combinare una serie di dati eterogenei in un'unità logica. In C si utilizza una sintassi che per prima cosa specifica ciò che la struttura contiene, quindi dichiara una variabile che servirà per riferirsi al nuovo dato definito. Per esempio:
struct {
} un_libro;
Per fare riferimento a un campo particolare della struttura si scrive il nome della struttura seguito da un punto “.” a sua volta seguito dal nome del campo. Riprendendo l'esempio di prima, per riferirci al campo anno della variabile un_libro, si scriverà: un_libro.anno;
La definizione di una struttura è a tutti gli effetti la definizione di un nuovo tipo, a cui si può dare anche un nome. Ad esempio:
struct Libro {
};
permette la dichiarazione di una variabile di questo tipo: Libro la_divina_commedia;
Le strutture dati dinamiche sono utilizzate per rappresentare le informazioni in tutti quei problemi che richiedono il cambiamento della struttura stessa durante l'elaborazione.
Pur avendo costituenti di base statici (quindi dati elementari, vettori o strutture statiche), il modo con cui vengono organizzati e collegati tra loro è ciò che li rende dinamici.
Nell'allocazione dinamica della memoria l'associazione tra specifiche aree di memoria e singole componenti della variabile di una struttura dati avviene solo quando le componenti cominciano ad esistere, cioè durante l'esecuzione del programma.
I linguaggi di alto livello supportano l'utilizzo di strutture dati dinamiche offrendo:
Un pezzo di codice si dice corretto quando fa esattamente quello che volevamo facesse. Un programma corretto è quindi un programma che soddisfa le sue specifiche.
In termini formali, si definisce specifica una quadrupla S = <X, Y, I, U>, dove I(x) è la precondizione che si assume vera per ogni dato di ingresso x ∈ X e U(x, y) è la postcondizione che deve essere vera dopo che il pezzo di codice è stato eseguito e che lega il dato di ingresso x con il risultato y.
Dire che un pezzo di codice che calcola una funzione f è corretto rispetto alla specifica S, vuol dire che: ∀x ∈ X, f (x) ∈ Y ∧ I (x) ⊃ U (x, f (x))
Esistono due modi per dimostrare che f sia corretta:
La verifica ha un valore assoluto di correttezza, mentre la validazione esclusivamente statistico; si può anche dire che la verifica è formale, mentre la validazione è empirica.
Pur essendo la via più sicura e definitiva per dimostrare la correttezza di un codice, è estremamente difficile e oneroso verificare programmi di una certa complessità; in alcuni casi addirittura proibitivo.
Quando si valida un programma lo spirito giusto non è dimostrare che il programma funziona, ma che non funziona. Tutto ciò che può fare la validazione è infatti rilevare la presenza di un errore e non garantirne l'assenza.
L'insieme dei casi di prova dovrebbe seguire i seguenti principi:
Ogni modifica apportata durante la manutenzione del codice richiede nuovi collaudi. Il test di regressione è quel processo che controlla che le modifiche non abbiano introdotto nuovi errori in un codice già validato. È un processo necessario, ma oneroso e molto costoso: è stato calcolato che le attività di manutenzione del software rappresentano i due terzi dell'intero costo di produzione.
L'opzione più semplice e costosa per effettuare il test di regressione è rifare da capo tutte le prove di validazione. Normalmente però si preferisce selezionare un opportuno sottoinsieme dei casi di prova, scegliendo uno tra i seguenti approcci:
Riguardo la verifica della correttezza del codice è opportuno fare una distinzione tra:
Le asserzioni sono costrutti condizionali che controllano una proprietà invariante e, nel caso in cui questa non si sia verificata, producono intenzionalmente un errore di esecuzione che ha l'effetto di abortire l'esecuzione del programma, segnalando così l'anomalia al programmatore, al collaudatore o all'utente.
Le asserzioni costituiscono una pratica comoda ed efficace di scrittura che, se seguita con attenzione, facilita la produzione di codice corretto e di documentazione interna di un programma.
Uno dei principi chiave di una buona organizzazione del codice è che sia modulare, ovvero suddiviso in unità funzionali separate, chiamate moduli, chiaramente individuate e caratterizzate da un livello di complessità gestibile.
Nella programmazione il modulo è un pezzo di programma logicamente autocontenuto, con modalità di interazione con gli altri eventuali pezzi di un sistema software ben definite e limitate. Si può dire che un modulo è un blocco di codice con esattamente un punto di entrata ed un punto di uscita.
La modularità è la proprietà di un sistema costituito da unità dette moduli e progettato con dimensioni standardizzate, in modo da essere flessibile e configurabile nell'utilizzo.
Nella programmazione, modularità significa identificare dei moduli semplici e ben delimitati in cui il programma può essere scomposto, in modo che ogni funzionalità sia confinata in un solo modulo e che le interazioni tra moduli siano il più possibile limitate e governate da convenzioni e regole precise.
Questa proprietà ha innegabili vantaggi: