Programmazione non strutturata - Home

Lezione 1 - Programmazione non
strutturata
Corso — Programmazione
Programmazione e progettazione — Programmazione
strutturata
Marco Anisetti
e-mail: [email protected]
web: http://homes.di.unimi.it/anisetti/
Riepilogo Modulo 1
• Pre requisiti matematici, elementi di linguaggi formali,
macchine a stati e architettura di riferimento
• Valutazioni su algoritmi semplici e loro rappresentazione
in un linguaggio adatto ad un elaboratore automatico
• Notazione prefissa, infissa e postfissa nelle espressioni
matematiche
• Linguaggio naturale, Flow chart, pseudocodice, linguaggio
di Programmazione
• Grammatica di un linguaggio, BNF, espressioni regolari,
carte sintattiche
• Classificazione dei linguaggi di programmazione in
dipendenza dell'esecutore e di chi scrive il programma
Problema - algoritmo - programma
Algoritmo - Modellazione - Programma
• La modellazione del problema attraverso flow chart è
utilissima, anche per produrre prove di correttezza del
funzionamento, ma deve poi essere tradotto in un
linguaggio comprensibile all'elaboratore
• Abbiamo visto una anticipazione di un programma scritto
per un modello di elaboratore (RAM) con prevalenti finalità
di valutazione della complessità
• Il linguaggio comprensibile per un elaboratore è quello
quanto più possibile vicino alla sua vera logica di
ragionamento
Il programmatore anche se agisce con strumenti ad alto livello deve aver molto ben
presente come funziona la macchina che eseguirà i programmi da esso sviluppati
Codice assembler per Macchina (RAM)
1: Mem[0]:=0
2: read(Mem[1])
3: if Mem[1]≥ 0 then goto 5
4: goto 7
5: Mem[3]:=Mem[0]-Mem[1]
6: if Mem[3]≥ 0 then goto 16
7: write(Mem[1])
8: read(Mem[2])
9: Mem[3]:= Mem[2]-Mem[1]
10: if Mem[3]≥ 0 then goto 12
11: goto 14
12: Mem[3]:=Mem[1]-Mem[2]
13: if Mem[3]≥ 0 then goto 8
14: Mem[1]:=Mem[2] +Mem[0]
15: goto 3
16: halt
Programmazione non strutturata
• Non è semplice capire cosa il codice fa guardandolo
• Vediamo un costrutto condizionale if-then e degli
assegnameni
• Il problema principale è seguire i goto incondizionati
• Non sempre posso avere una documentazione addizionale
• Il programma deve avere una sua leggibilità indipendente
da documentazione aggiuntiva
• Al crescere delle dimensioni di un programma, diventa
sempre più difficile per il programmatore padroneggiarlo
nel suo complesso.
• Il problema dei salti incondizionati e della relativa
programmazione non strutturata è di cruciale importanza
• Un salto condizionato è più facile da comprendere per via
della condizione che lo genera
Il programma precedente prende in ingresso una sequenza di numeri tipo 112223144
e ritorna la sequenza senza doppioni 12314
Programmazione non strutturata
• E' stata per molti anni l'unica possibile
• I salti non condizionati sono stati l'unico modo per avere
un flusso differente dal flusso sequenziale
• Alcuni salti incondizionati mappano strutture iterative
come quelle viste nei primi esempi di flow chart
• Altri però non hanno nessuna corrispondenza diretta con
tali strutture
• Questo genere di salti non condizionati (non in relazione
con cicli) sono quelli più critici da valutare
Flow chart e programmazione non
strutturata
• I flow chart possono essere usati anche a solo scopo di
documentazione di un codice
• Come esercizio si provi a scrivere il flow chart del
programma RAM visto in precedenza
• Evidenziare i goto con delle apposite frecce ed indicare
condizioni e operazioni come visto nello scorso modulo
• Individuate eventuali strutture iterative
Soluzione
Lezione 2 - Programmazione strutturata
Corso — Programmazione
Programmazione e progettazione — Programmazione
strutturata
Marco Anisetti
e-mail: [email protected]
web: http://homes.di.unimi.it/anisetti/
Università degli Studi di Milano — Dipartimento di informatica
Programmazione imperativa
• Programmazione classica in cui si ordina all'esecutore di
compiere delle azioni
• Fino ad ora abbiamo sempre implicitamente parlato di
programmazione imperativa
• Gli elementi caratterizzanti sono:
Il valore delle variabili cambia durante l'esecuzione
(dinamicità)
Il programma non è la stessa cosa della computazione
(staticità)
• Gli elementi più significativi per la programmazione
imperativa sono quindi:
Elementi strutturati
Invarianti
Esempio: rimozione dei doppioni
• Possiamo scrivere lo stesso programma dell'esempio RAM
usando la programmazione imperativa
• In questo caso sfrutto ancora i salti incondizionati
(Fortran)
• E' più leggibile (codificata ad un livello più alto) ma si può
fare di meglio usando degli elementi strutturati
1:
2:
3:
4:
5:
6:
7:
8:
read(x);
if x=0 then goto 8;
writeln(x);
read(next);
if next=x then goto 4;
x:=next;
goto 2;
;
Esempio programmare con goto
• Il goto è ancora presente come costrutto di alcuni
linguaggi ad alto livello
• Proviamo a scrivere il programma che calcola della
divisione tra due numeri controllando che il divisore sia
diverso da zero
1:
2:
3:
4:
5:
6:
7:
leggi il dividendo e il divisore
if il divisore è diverso da zero then goto 5
scrivi `errore: divisione per zero'
goto 7
calcola dividendo/divisore
scrivi il risultato
end
Programmazione strutturata
• E' un paradigma di programmazione emerso fra gli anni
sessanta e gli anni settanta nel contesto della
programmazione procedurale
• Critica della struttura di controllo del salto incondizionato,
che rappresentava, negli anni sessanta, lo strumento
fondamentale per la definizione di algoritmi complessi
• Dijkstra fu tra i primi a evidenziare gli effetti deleteri dei
salti incondizionati sulla leggibilità e modificabilità del
software (spaghetti code)
• In seguito parleremo di programma come di un algoritmo
scritto in un linguaggio specifico
• I passi dell'algoritmo vengono mappati in una o più
istruzioni nel linguaggio
• Il flusso dell'algoritmo in una serie di strutture per il
controllo di flusso del programma
Programmazione strutturata (2)
• Obiettivo: ottenere il più possibile un flusso ordinato di
istruzioni dall'inizio alla fine (abolizione dei salti
incondizionati)
• Idealmente ottenibile considerando una sequenza lineare
di operazioni, senza alternative (ridotta potenza degli
algoritmi)
• Nella realtà avviene attraverso regole che portano ad
effetti equivalenti all'esecuzione sequenziale di operazioni
• Ogni struttura di controllo ha un solo punto di ingresso e
un solo punto d'uscita
• Il flusso di esecuzione è evidente dalla struttura del codice
• Enfasi sulla struttura e sul flusso, è indipendente dalla
efficienza
Programma proprio (1)
• Un programma si definisce proprio se gode delle seguenti
proprietà
Ha un unico ingresso ed un'unica uscita
Ogni elemento appartiene ad un percorso che porta
dall'ingresso all'uscita
• L'ingresso è l'unica via di accesso al programma e l'uscita
è l'unica via di terminazione del programma
• Il programma proprio può essere suddiviso in strutture
proprie detti blocchi che godono delle stesse due proprietà
Programma proprio (2)
Programmi equivalenti
• Due programmi che realizzano lo stesso algoritmo usando
operazioni differenti si dicono equivalenti
• In modo formale due programmi propri P e Q sono
equivalenti se: P(X ) = Y = Q(X )
• Ovvero se applicati agli stessi argomenti X forniscono lo
stesso risultato Y
Strutturazione in moduli
• La definizione di programma proprio e di blocchi
suggerisce una strutturazione modulare dei programmi
• I moduli hanno una strutturazione gerarchica ben definita,
e definiscono funzioni logiche precise (coesione
funzionale)
• I moduli devo avere dimensioni accettabili (dimensione)
• Le strutture di controllo presenti nei moduli devono essere
tenute d'occhio, annidate al max su 3 livelli (profondità)
• Un modulo è una fase concettuale dell'algoritmo (fase
temporale)
• Tutte le attività di un modulo dovrebbero essere eseguite
nelle stesse condizioni (stessa base condizionale)
• Tutte le attività di uno stesso modulo dovrebbero lavorare
sugli stessi dati (condivisione dei dati)
Teorema di Böhm Jacopini
[Teorema di Böhm Jacopini]
Dato un programma proprio P è possibile costruire un
programma strutturato S(P) equivalente a P
• Il teorema permise di dimostrare che la potenza di calcolo
dei programmi strutturati non è inferiore a quella dei
programmi che usano il goto (completezza)
• Il programma strutturato S(P) è costituito da combinazioni
di tre oggetti logici fondamentali: Sequenza, Selezione,
Iterazione
[Completezza]
Tutti i programmi esprimibili tramite istruzioni di salto (goto) o
diagrammi di flusso (flow-chart) possono essere riscritti
utilizzando esclusivamente le tre strutture di controllo
fondamentali (eliminazione dei salti)
Strutture di controllo ed invarianti
• Come abbiamo visto il programma evolve
• Una invariante è una asserzione vera in qualunque
momento della esecuzione del programma
• Una asserzione è una condizione vera o falsa circa lo stato
della computazione (e.g. x > y)
• La maggiore difficoltà nello scrivere codice è che la
correttezza è una proprietà dinamica della computazione e
non statica del codice scritto
• Gli invarianti sono associati ad un punto del programma
ma ci danno delle indicazioni circa le proprietà della sua
computazione
• Nella prossima lezione vedremo nel dettaglio le strutture
di controllo tipiche della programmazione strutturata
Lezione 3 - Costrutti della
programmazione strutturata
Corso — Programmazione
Programmazione e progettazione — Programmazione
strutturata
Marco Anisetti
e-mail: [email protected]
web: http://homes.di.unimi.it/anisetti/
Costrutti fondamentali
[Sequenza]
Le istruzioni vengono eseguite a seconda dell'ordine in cui
sono scritte
[Selezione]
L'esecuzione di un blocco di istruzioni viene scelta tra due
possibili in base al valore di una condizione
[Iterazione]
L'esecuzione di una o più istruzioni viene ripetuta in base al
valore di una condizione
Sequenza
Le istruzioni sono eseguite nello stesso ordine in cui
compaiono nel programma, cioè secondo la sequenza in cui
sono scritte.
[Moltiplicazione tra due numeri]
1: leggi i numeri x e y
2: calcola x ∗ y
Sequenza: esempio
Calcolo dell'età media dei componenti di un nucleo familiare
Selezione (if-then)(1)
[Sintassi]
IF condizione
THEN
blocco 1
ENDIF
blocco 2
[non strutturata]
if condizione
then < goto blocco 1>
< goto blocco 2>
blocco 1
blocco 2
Selezione (if-then)(2)
[Esecuzione]
Valutazione della condizione:
VERA Vengono eseguite le istruzioni del blocco 1
In seguito si esegue blocco 2 essendo la prima
istruzione che segue il costrutto
FALSA l'esecuzione prosegue direttamente dalla prima
istruzione che segue il costrutto ovvero blocco 2
Selezione (if-then-else)(1)
[Sintassi]
IF condizione
THEN
blocco 1
ELSE
blocco 2
ENDIF
blocco 3
[non strutturata]
if condizione
then < goto blocco 1>
blocco 2
< goto blocco 3>
blocco 1
blocco 3
Selezione (if-then-else)(2)
[Esecuzione]
(1) Valutazione della condizione
VERA Vengono eseguite le istruzioni del blocco 1
FALSA Vengono eseguite quelle del blocco 2
(1) L'esecuzione procede con le istruzioni in blocco 3
Selezione (if-then-else)(3)
L'uso dell'else equivale ad un doppio uso dell'if-then:
[Esempio]
IF condizione
THEN
blocco 1
ENDIF
IF not condizione
THEN
blocco 2
ENDIF
blocco 3
Esempio(1)
Rivediamo l'esercizio del calcolo della divisione tra due numeri
controllando che il divisore sia diverso da zero:
leggi il dividendo e il divisore
IF il divisore è diverso da zero
THEN
calcola dividendo/divisore
scrivi il risultato
ELSE
scrivi `errore: divisione per zero'
ENDIF
Esempio: flow chart(1)
Calcolo delle soluzioni reali di ax 2 + bx + c = 0
Prima approssimazione della soluzione, approccio modulare
Esempio: flow chart(2)
Versione completa dettagliano il modulo del calcolo delle radici
Esempio: pseudocodifica
Versione in pseudocodice sviluppando meglio i moduli di
calcolo delle radici
leggi i valori dei parametri a, b, c
calcola il discriminante
IF il discriminante è minore di zero
THEN
scrivi `nessuna soluzione reale'
ELSE
IF il discriminante è uguale a zero
THEN
calcola −b
2a
scrivi le due soluzioni coincidenti
ELSE
√
b2 −4ac
calcola −b−√2a
b2 −4ac
calcola −b+ 2a
scrivi le due soluzioni
ENDIF
ENDIF
Iterazione (post-condizionato)(1)
Chiamato anche ciclo repeat-until
[Sintassi]
DO
blocco 1
WHILE condizione
blocco 2
[Non strutturato]
blocco 1
if condizione
then goto blocco 1
blocco 2
Iterazione (post-condizionato)(2)
[Esecuzione]
(1) Viene eseguito blocco 1
(1) Viene valutata condizione:
VERA Si ritorna al punto (1)
FALSA Si prosegue con la prima istruzione scritta dopo il costrutto
iterativo
• Il blocco 1 è eseguito almeno una volta
• L'iterazione termina quando la condizione diventa falsa
Esempio
Somma dei primi 1000
P numeri interi senza utilizzare la
formula di Gauss ( ni=1 i = n(n+1)
), ma iterativamente
2
inizializza la somma a zero
parti dal numero 1
DO
aggiungi alla somma il numero
passa al numero successivo (incremento)
WHILE il numero non supera 1000
scrivi la somma ottenuta
Iterazione (pre-condizionato)(1)
[Sintassi]
WHILE condizione DO
blocco 1
END WHILE
blocco 2
Iterazione (pre-condizionato)(2)
[Esecuzione]
(1) Viene valutata la condizione:
VERA Viene eseguito blocco 1
quindi si torna al punto (1)
FALSA L'esecuzione riprende dalla prima l'istruzione che segue il
costrutto iterativo
• Il blocco 1 può essere eseguito anche zero volte
• L'iterazione termina quando la condizione diventa falsa
Esempio iterazione
Il comportamento dell'iterazione pre-condizionata può essere
simulato combinando un iteratore post-condizionato e una
selezione:
IF condizione
THEN
DO
blocco 1
WHILE condizione
ENDIF
Lezione 4 - Variabili ed assegnamenti
Corso — Programmazione
Programmazione e progettazione — Programmazione
strutturata
Marco Anisetti
e-mail: [email protected]
web: http://homes.di.unimi.it/anisetti/
Università degli Studi di Milano — Dipartimento di informatica
Variabili
• Le abbiamo introdotte nel precedente modulo come
paragonabili alle incognite matematiche
• Dato che un algoritmo descrive una soluzione per una
classe di problemi abbiamo bisogno di variabili (contenitori
di valori) per esprimere le varie istanze di problemi
• Si definiscono in termini di:
• Nome: identificatore (a cui fare riferimento)
• Tipo: insieme dei possibili valori che possono essere
assunti (char, stringa, intero, reale, booleana)
• Valore: valore attualmente assunto dalla variabile
Identificatore - valore
• Un identificatore è il nome di un oggetto
• L'identificatore corrisponde ad una area di memoria che
contiene il valore dell'oggetto
• Il rapporto tra identificatore e valore è dinamico mentre
quello tra identificatore e l'area di memoria è statico
• L'identificatore o nome di un variabile deve essere
auto-documentante
Variabili e assegnamenti(1)
• Una variabile è un contenitore preposto a contenere dei
valori che possono variare durante il tempo di esecuzione
• E' una locazione di memoria che ha una dimensione
associata e che è riferibile attraverso il suo nome e nella
quale si può scrivere attraverso un assegnamento
• Gli assegnamenti li usiamo da molte lezioni e permettono
di variare il contenuto di una variabile
[Istruzione di assegnamento]
variabile ←espressione (oppure variabile := espressione)
Variabili e assegnamenti(2)
[Semantica assegnamento]
(1) Viene calcolato il valore dell'espressione scritta a destra
del simbolo ←
(1) Il risultato ottenuto è assegnato alla variabile a sinistra
del simbolo ← (nel caso sovrascrivendo l'eventuale valore
precedentemente contenuto)
Molti linguaggi, utilizzano per l'assegnamento il simbolo =, usato comunemente per
indicare l'uguaglianza
Esempio
x←y + z
• Valuta l'espressione y + z, recuperando i valori presenti
nella celle di memoria relative a y e z
• Assegna alla variabile x il risultato di tale somma
(sovrascrivendo il valore)
Tipo
Il tipo di una variabile specifica:
• La classe di valori che questa può assumere
• L'insieme delle operazioni che possono essere effettuate
su di essa.
• Quanto spazio occupa in memoria (il numero contiguo di
celle da occupare)
Ad esempio una variabile x di tipo intero
• Può assumere come valori solo numeri interi
• Su di essa possono essere effettuate soltanto
le operazioni consentite per i numeri interi
• La sua occupazione di memoria è solitamente uguale alla
dimensione dei registri dell'elaboratore (es. 32, 64 bit)
Astrazioni
[Variabile]
• Il concetto di variabile è un'astrazione del concetto di
locazione di memoria
• La variabile è il riferimento mnemonico all'indirizzo della
locazione di memoria
• L'assegnamento di un valore a una variabile è
un'astrazione dell'operazione STORE di un ipotetico
linguaggio macchina
[Tipi]
• Sebbene tutte le variabili siano rappresentate nella
memoria come sequenze di bit, tali sequenze possono
essere interpretate diversamente in base ai tipi
• La tipizzazione delle variabili permette di mantenere il
controllo sulla correttezza dello sviluppo
• La nozione di tipo fornisce un'astrazione rispetto alla
rappresentazione effettiva dei dati
• Il programmatore può utilizzare variabili di tipi differenti,
Dichiarazione delle variabili
• Molti linguaggi richiedono di dichiarare le variabili
utilizzate nel programma indicandone il tipo
• Alcuni linguaggi (ad esempio Pascal) richiedono che le
variabili siano dichiarate tutte all'inizio del programma
• Alcuni linguaggi richiedono che siano dichiarate prima del
loro utilizzo (ad esempio Java)
• Vantaggi nella dichiarazione:
Accresce la leggibilità dei programmi
Diminuisce la possibilità di errori
Facilita la realizzazione di compilatori efficienti
Esempio: rimozione dei doppioni
• Ora possiamo rivedere l'esempio usando la
programmazione strutturata
read(x);
while x 6= 0 do
writeln(x);
repeat
read(next);
until x6=next;
x:=next;
endwhile
Condizioni - tipi - assegnamenti
• Quello che viene valutato in una condizione è simile al
membro destro di un assegnamento
• Esiste genericamente un tipo associato ad una
espressione il quale dipende dai tipi delle variabili o
letterali utilizzati nell'espressione
• L'espressione utilizzabile in una condizione può anche
essere una uguaglianza una disuguaglianza o una
proposizionale logica
• Quando l'espressione è usata in una condizione essa viene
valutata ed il ritorno viene interpretato dall'istruzione
condizionale
• Questo passaggio dipende dal linguaggio
• Il valore di verità è associato ad un tipo particolare detto
booleano
• Tale tipo può prendere valore nell'insieme {vero,falso}
Lezione 5 - Eliminazione dei salti
Corso — Programmazione
Programmazione e progettazione — Programmazione
strutturata
Marco Anisetti
e-mail: [email protected]
web: http://homes.di.unimi.it/anisetti/
Università degli Studi di Milano — Dipartimento di informatica
Eliminazione dei salti
• Quando abbiamo parlato di programmazione strutturata e
non strutturata abbiamo introdotto il teorema di
Böhm Jacopini
• In questa lezione vediamo la dimostrazione e come si può
utilizzare
• Vediamo anche una dimostrazione alternativa al teorema
tramite la trasformazione di Ashcroft e Manna
Dimostrazione Teorema di Böhm Jacopini
• La dimostrazione del teorema porta a del codice
strutturato in maniera da avere un unico ciclo (di tipo
pre-condizionato) e una serie di variabili booleane di
supporto per il mantenimento dell'ordine delle operazioni
• Le variabili booleane sono a guardia di ogni operazione e
permettono di eseguire una istruzione per ogni ciclo
WHILE in maniera simile ad un program counter
WHILE ....
IF ... THEN istruzione 1
ENDIF
.
.
.
IF ... THEN istruzione n
ENDIF
Teorema di Böhm Jacopini: esempio
Teorema di Böhm Jacopini: conclusioni
• E' sempre possibile scrivere un qualsiasi programma
usando solo i costrutti della programmazione strutturata
• Si possono eliminare i salti di un programma non
strutturato ottenendo un programma strutturato a patto di
inserire un certo numero di selezioni aggiuntive
• Il risultato di questa trasformazione è un programma
strutturato ma la tecnica presentata nella dimostrazione
non porta ad un programma meno intircato del
programma non strutturato (programma spaghettiforme)
• Esiste una trasformazione che dimostra il teorema e che
porta a risultati più rilevanti
La trasformazione di Ashcroft e Manna(1)
• Tecnica costruttiva per portare alla dimostrazione del
teorema di Böhm Jacopini sfruttando i concetti di
programma proprio e di scomposizione gerarchica di un
programma in sottoprogrammi propri
• La dimostrazione sfrutta il diagramma di flusso come
rappresentazione non considerando gli stati iniziale e
finale e permette di
preservare la struttura logica del programma
La trasformazione di Ashcroft e Manna(2)
La trasformazione di Ashcroft e Manna(2)
La trasformazione di Ashcroft e Manna(3)
La trasformazione di Ashcroft e Manna(4)
Per trasformare questi blocchi ci son due regole:
1. Il blocco contiene un solo test (lo sappiamo già
trasformare), oppure non contiene cicli, e anche questo
caso è banale
2. Il blocco contiene più di un test e almeno un ciclo.
Si identificano i punti dell'insieme di taglio sulle frecce del
blocco in modo tale che ciascun ciclo contenga almeno uno
di tali punti e che uno di questi punti stia sull'unica freccia
uscente.
Si traduce il blocco in un pezzo di programma con un
WHILE esterno in modo tale che ogni iterazione del ciclo
WHILE segua l'esecuzione del blocco da un punto
dell'insieme di taglio al successivo.
Si introduce un numero i di variabili booleane sufficiente a
distinguere tutti i punti dell'insieme di taglio definiti
i è il più piccolo intero successivo a dlog2 ne dove n è il
numero di punti di taglio.
Trasformazione semplice
Se contiene solo un test si tratta di una trasformazione
semplice
sequenza 1
IF condizione THEN salta fuori
ENDIF
sequenza 2
Salta a sequenza 1
↓
b ← True
WHILE b
sequenza 1
b ← ¬ condizione
IF b THEN sequenza 2
ENDWHILE
La trasformazione di Ashcroft e Manna(5)
La trasformazione di Ashcroft e Manna(6)
• b1 controlla il WHILE, quindi è logicamente collegata al
punto γ
• b2 svolge la funzione di selettore tra i due cicli interni
controllati dai punti α e β
• Dimostrazione è più costruttiva e introduce concetti
interessanti di gerarchia
Costrutti strutturati minimali
• In realtà i 3 costrutti visti possono essere ulteriormente
ridotti ai soli sequenza e iterazione per codificare qualsiasi
algoritmo
• E' possibile rappresentare una selezione come un costrutto
iterativo inserendo una variabile booleana in aggiunta.
IF condizione
THEN
blocco 1
ENDIF
↓
b ← condizione
WHILE b
blocco 1
b ← false
ENDWHILE
Programmazione strutturata ed efficienza
• Il fatto che un programma non strutturato possa essere
riscritto in modo strutturato non implica che le due
versioni del programma abbiano la stessa dimensione o la
stessa efficienza
• Esiste infatti un interessante teorema [*] che afferma che
per ogni intero n, esiste un programma di n istruzioni che
usa i salti, che non puo essere convertito
in un
√
n
programma strutturato di meno di 1. 3 istruzioni, a meno
che tale programma non sia più lento di un fattore 12 log2 n.
[*] Ricard A. DeMillo, Stanley C. Eisenstat, and Richard J. Lipton. Spacetime trade-offs
in structured programming: An improved combinatorial embedding theorem. Journal
of the ACM, 1980.

Download Report