Dispense Tetty - Capitolo 3

Torna alla pagina di Programmazione degli Elaboratori

---

:: Capitolo 3: Programmazione strutturata ::

Indice

1 Principi della programmazione strutturata
2 I linguaggi di alto livello

3 Elementi di sintassi C/Java

4 Costrutti di controllo

5 Eliminazione dei salti

6 Strutture dati

7 Correttezza dei programmi

8 Modularità

---

1. Principi della programmazione strutturata

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:

• esecuzione seriale, cioè esecuzione di un'attività dopo l'altra;
• iterazione, cioè ripetizione di un'attività;
• selezione, cioè esecuzione di due o più attività a seconda di una condizione.

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:

• dimensione: ogni modulo dovrebbe starci tutto in una schermata;
• profondità: un modulo non dovrebbe contenere più di tre livelli di strutture di controllo nidificate, meglio ancora se meno;
• fase temporale: tutte le attività integrate in un modulo dovrebbero riguardare la stessa fase concettuale dell'algoritmo che viene realizzato;
• stessa base condizionale: tutte le attività integrate nello stesso modulo dovrebbero essere eseguite nelle stesse condizioni;
• condivisione dei dati: tutte le attività integrate nello stesso modulo dovrebbero lavorare sugli stessi dati;
• coesione funzionale: ciascun modulo dovrebbe essere volto ad ottenere un solo scopo specifico o a realizzare una precisa funzionalità.

Torna su

2. I linguaggi di alto livello

2.1 Caratteristiche dei linguaggi di alto livello

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:

• portabilità. Dato che un linguaggio di alto livello nasconde al programmatore i dettagli della macchina su cui girerà, ne consegue che tali linguaggi siano (quasi) indipendenti dalla macchina stessa;
• facilità di scrittura, lettura e manutenzione. Grazie alla maggiore intuitività espressiva del linguaggio vi è una minore esposizione agli errori ed una maggiore velocità nella scrittura del codice;
• meno dettagli da gestire. Un linguaggio di alto livello solleva il programmatore da una serie di incombenze complesse ma necessarie, che rischiano di far perdere di vista il compito principale. Ne è un esempio la gestione della memoria.

Un linguaggio di programmazione di alto livello strutturato è caratterizzato da:

• dichiarazione di tipi;
• disponibilità di costrutti di sequenza, selezione ed iterazione;
• dichiarazione di variabili e sottoprogrammi;
• presenza di regole di visibilità (scoping) che specificano in quali parti del programma ha significato un particolare identificatore.

2.2 Cenni su altri paradigmi di programmazione

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:

• imperativo, quello classico e più diffuso, basato su una serie di comandi;
• funzionale, le cui espressioni utilizzano le funzioni per combinare i valori di partenza. È unicamente costituito da definizioni di funzioni, e il programma stesso assume la forma di funzione;
• logico, che richiede al programmatore di descrivere la struttura logica del problema piuttosto che il modo di risolverlo. Unica preoccupazione sarà quindi rappresentare adeguatamente il problema, lasciando all'interprete il compito di utilizzare le informazioni fornite e risolverlo.

2.3 Il concetto di tipo di dato

È 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.

2.4 Gestione della memoria

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.

Torna su

3. Elementi di sintassi C/Java

In questo capitolo verranno fornite alcune conoscenze di base per C, C++ e Java.

3.1 Commenti

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: //.

3.2 Dichiarazione di variabili

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.

3.3 Espressioni e assegnamenti

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.

3.4 Vettori (array)

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];

3.5 Funzioni

Tutti i linguaggi di alto livello permettono la gestione dei sottoprogrammi, distinguendoli in:

• procedure, ovvero sottoprogrammi che prendono in ingresso zero o più argomenti (o parametri), svolgono una particolare elaborazione in base ad essi e non restituiscono (almeno esplicitamente) alcun risultato al programma chiamante;
• funzioni, ovvero sottoprogrammi che prendono in ingresso zero o più argomenti (o parametri), svolgono una particolare elaborazione in base ad essi e restituiscono un valore al programma chiamante per mezzo dell'istruzione “return  espressione ”.

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.

Torna su

4. Costrutti di controllo

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.

4.1 Esecuzione in sequenza

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: { } .

4.2 Costrutti iterativi

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:

• break, che interrompe l'esecuzione del ciclo e passa all'istruzione successiva;
• continue, che non esce dal ciclo ma passa all'iterazione successiva.

4.3 Costrutti di selezione

I costrutti di selezione possono essere di due tipi fondamentali:

• gli if , che permettono una selezione tra due alternative in base ad una

condizione binaria;

• gli switch , che permettono una selezione tra molte alternative in base al valore

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>) {

}

Torna su

5. Eliminazione dei salti

5.1 Il Teorema di Böhm-Jacopini

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.

5.2 La trasformazione di Ashcroft e Manna

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.

5.3 Costrutti minimali

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.

Torna su

6. Strutture dati

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.

6.1 Strutture dati statiche

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;

6.2 Strutture dati dinamiche e puntatori

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:

• tipi di dato in grado di fornire gli indirizzi delle locazioni di memoria, ovvero i puntatori. Si dichiarano con un asterisco * dopo l'identificatore del tipo;
• opportune convenzioni sintattiche per definire e utilizzare i puntatori;
• una gestione automatica dell'allocazione dinamica di memoria.

Torna su

7. Correttezza dei programmi

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))

7.1 Verifica e validazione

Esistono due modi per dimostrare che f sia corretta:

• la verifica, che consiste nel considerare la formula precedente e dimostrare che f restituisce il risultato corretto per ogni possibile ingresso;
• la validazione, che consiste nell'eseguire una serie di prove e verificare che f restituisce il risultato desiderato in ciascuna delle prove effettuate, in modo che sia ragionevole aspettarsi che f restituirà il risultato desiderato anche in quei casi non ancora provati.

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.

7.2 Validazione del codice

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:

• esercitare tutto il codice, poiché l'errore potrebbe annidarsi nel ramo di codice meno usato e più remoto;
• provare alcuni casi tipici, per trovare eventuali errori macroscopici dovuti a distrazione;
• provare alcuni casi atipici, ovvero quei casi più insidiosi perché non tenuti in considerazione dal programmatore durante la realizzazione del programma. Sono quelli su cui bisognerebbe concentrarsi maggiormente;
• provare tutti i casi limite (stress testing), che mettono alla prova la robustezza del codice e che possono evidenziare alcune falle dovute a mancati controlli o errori di distrazione.

7.3 Test di regressione

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:

• approcci di minimizzazione, che assicurano un minimo di copertura strutturale, ad esempio selezionando una sola prova per ciascun blocco di codice modificato;
• approcci di copertura, anch'essi basati su approcci di copertura, ma che selezionano tutte le prove che esercitano il codice modificato;
• approcci sicuri, che selezionano ogni prova che potrebbe far sì che il programma modificato produca un risultato diverso dall'originale.

7.4 Verifica del codice

Riguardo la verifica della correttezza del codice è opportuno fare una distinzione tra:

• correttezza totale, che corrisponde alla garanzia del soddisfacimento delle specifiche per qualsiasi ingresso in un numero finito di passi. Per dimostrare la correttezza totale bisogna dimostrare che il programma termina per ogni ingresso x ∈ X che soddisfa I(x), e dimostrare inoltre la correttezza parziale del programma;
• correttezza parziale, che corrisponde alla semplice garanzia che per ogni ingresso x ∈ X che soddisfa I(x), il programma, se termina, produce un risultato y ∈ Y che soddisfa la specifica.

7.5 Asserzioni

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.

Torna su

8. Modularità

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.

8.1 Definizione di modulo

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.

8.2 Definizione di modularità

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:

• la possibilità di modificare il codice di un modulo senza dover di conseguenza riscrivere anche il resto del programma;
• la possibilità di estrarre un modulo da un programma per riutilizzarlo in un altro.

Torna su

---

Torna alla pagina di Programmazione degli Elaboratori