I linguaggi di programmazione - MathUniPDaceccato/Intro_1213/Lezione4... · 2012-10-12 · di alto...
Transcript of I linguaggi di programmazione - MathUniPDaceccato/Intro_1213/Lezione4... · 2012-10-12 · di alto...
11
I linguaggi di programmazioneI linguaggi di programmazione
22
Lessico, sintassi e semanticaLessico, sintassi e semantica
• Lessico:Lessico: l’insieme di regole formali per la scrittura di parole in un linguaggio
• Sintassi:Sintassi: l’insieme di regole formali per la scrittura di frasi in un linguaggio, che stabiliscono cioè la grammatica del linguaggio stesso
• Semantica:Semantica: l’insieme dei significati da attribuire alle frasi (sintatticamente corrette) costruite nel linguaggio
• Nota:Nota: una frase può essere sintatticamente corretta e tuttavia non avere significato!“Sento il micino che cinguetta e annaffio nel giardino le mie mimose blu…”
33
Esempio: la sintassi di un numero naturaleEsempio: la sintassi di un numero naturale
Diagramma sintatticoDiagramma sintattico
<cifra-non-nulla> := 1|2|3|4|5|6|7|8|9
<cifra> := 0 | <cifra-non-nulla>
<naturale> := 0 | <cifra-non-nulla>{<cifra>}
44
I linguaggi di programmazione:I linguaggi di programmazione:Cenni storici Cenni storici −− 1 1
• Benché siano macchine in grado di compiere operazioni complesse, i calcolatori devono essere “guidati” per mezzo di istruzioni appartenenti ad un linguaggio specifico e limitato, a loro comprensibile
• Un linguaggio di programmazione è costituito, come ogni altro tipo di linguaggio, da un alfabetoalfabeto, con cui viene costruito un insieme di parole chiaveparole chiave (il vocabolario) e da un insieme di regole sintatticheregole sintattiche per l’uso corretto delle parole del linguaggio
• A livello hardware, i calcolatori riconoscono solo comandi semplici, del tipo copia un numerocopia un numero, addiziona addiziona due numeridue numeri, confronta due numericonfronta due numeri
55
I linguaggi di programmazione:I linguaggi di programmazione:Cenni storici Cenni storici −− 2 2
• I primi linguaggi di programmazione coincidevano con l’insieme delle istruzioni eseguibili dall’hardware
• Le istruzioni hardware sono codificate in codice binario: ogni informazione è rappresentata, all’interno della macchina, come una sequenza di bit Enorme sforzo programmativo richiesto per codificare Enorme sforzo programmativo richiesto per codificare
algoritmi semplicialgoritmi semplici• I comandi realizzati in hardware definiscono il set di set di
istruzioni macchinaistruzioni macchina e i programmi che li utilizzano direttamente sono i programmi in linguaggio macchinalinguaggio macchina
66
I linguaggi di programmazione:I linguaggi di programmazione:Cenni storici Cenni storici −− 3 3
• In linguaggio macchina… …ogni “operazione” richiede l’attivazione di numerose
istruzioni base …qualunque entità, istruzioni, variabili, dati, è
rappresentata da numeri binari: i programmi sono difficili da scrivere, leggere e manutenere
• Il linguaggio macchina riflette l’organizzazione della macchina più che la natura del problema da risolvere
• Dalla nascita dei primi calcolatori, si è cercato di Dalla nascita dei primi calcolatori, si è cercato di diminuire lo sforzo ed aumentare la produttività diminuire lo sforzo ed aumentare la produttività dell’utente, anche a costo di caricare la macchina di dell’utente, anche a costo di caricare la macchina di maggiori compitimaggiori compiti
77
I linguaggi di programmazione:I linguaggi di programmazione:Cenni storici Cenni storici −− 4 4
• La prima evoluzione dei linguaggi di programmazione ha portato ad una codifica di tipo simbolico, anziché binaria, dei programmi
• Tali versioni simboliche dei linguaggi hardware sono note come linguaggi assemblatorilinguaggi assemblatori, dal termine usato per indicare i programmi traduttori che, ricevendo come dato la versione simbolica di un programma, producono come risultato la corrispondente forma binaria direttamente eseguibile dalla macchina
• Per la prima volta, con la nascita degli assembler, fu applicato il principio che è meglio risparmiare il tempo dell’uomo anche a costo di sprecare tempo−macchina (una parte del tempo è dedicata alla traduzione di programmi, non alla loro esecuzione)
88
I linguaggi di programmazione:I linguaggi di programmazione:Cenni storici Cenni storici −− 5 5
• Negli anni ‘50, tutti i programmi erano scritti in linguaggio macchina o in assemblyassembly
• In assembly… …le istruzioni corrispondono univocamente alle istruzioni
macchina, ma vengono espresse tramite nomi simbolici (parole chiave) piuttosto che mediante codici numerici
…il riferimento alle variabili viene effettuato per mezzo di nomi piuttosto che con indirizzi di memoria
• I programmi scritti in assembly necessitano di un apposito programma assemblatoreassemblatore per tradurre le istruzioni tipiche del linguaggio in istruzioni macchina
99
I linguaggi di programmazione:I linguaggi di programmazione:Cenni storici Cenni storici −− 6 6
• Il passo successivo nell’evoluzione dei linguaggi di programmazione tese a rendere la codifica degli algoritmi il più possibile “vicina” al problema da risolvere, anziché all’architettura della macchina destinata all’esecuzione del programma
I primi due linguaggi di alto livellolinguaggi di alto livello, FORTRANFORTRAN e COBOLCOBOL, hanno costrutti fortemente ispirati alla notazione usata, negli anni ‘50, per l’elaborazione numerica e gestionale
1010
I linguaggi di programmazione:I linguaggi di programmazione:Cenni storici Cenni storici −− 6 6
• Il passo successivo nell’evoluzione dei linguaggi di programmazione tese a rendere la codifica degli algoritmi il più possibile “vicina” al problema da risolvere, anziché all’architettura della macchina destinata all’esecuzione del programma
I primi due linguaggi di alto livellolinguaggi di alto livello, FORTRANFORTRAN e COBOLCOBOL, hanno costrutti fortemente ispirati alla notazione usata, negli anni ‘50, per l’elaborazione numerica e gestionale
Formula Translation (o Translator), cioè traduzione/traduttore di formule (matematiche) in algoritmi computazionali
COmmon Business-Oriented Language, ossia, letteralmente, "linguaggio comune orientato alle applicazioni commerciali"
1111
I linguaggi di programmazione:I linguaggi di programmazione:Cenni storici Cenni storici −− 7 7
• Negli anni ‘70: Si diffondono i linguaggi strutturati, quali il SIMULA 67SIMULA 67,
capostipite dei linguaggi Object−Oriented, l’ALGOL 68ALGOL 68, ma soprattutto il PASCALPASCAL, primo esempio di prodotto di origine accademica che abbia conosciuto vasto successo ed applicazione nel mondo dell’industria
In modo simile, il CC, concepito come un assembler strutturato per trasportare facilmente UNIXUNIX, ha finito per diventare il linguaggio più affermato nella programmazione di sistema
1212
I linguaggi di programmazione:I linguaggi di programmazione:Cenni storici Cenni storici −− 8 8
• Nel periodo a cavallo tra gli anni ‘70 ed ‘80:
Si moltiplicano i nuovi linguaggi tesi a rendere più gradevole ed efficiente la programmazione tradizionale e si ha l’affermarsi definitivo dei linguaggi object−oriented (CC++++, Visual BASICVisual BASIC, JavaJava)
1313
I linguaggi di programmazione:I linguaggi di programmazione:Cenni storici Cenni storici −− 9 9
• Python è un potente linguaggio di programmazione (paragonabile al C++ e Java) orientato agli oggetti e pseudocompilato.
• Nacque verso la fine degli anni 80 nell'istituto di matematica e informatica (CWI) di Amsterdam e fu il frutto del lavoro di alcuni ricercatori tra cui spicca particolarmente Guido van RossumGuido van Rossum (creatore, ideatore del linguaggio e capo del team), ispirandosi al "Monty Python's Flying Circus" (una serie televisiva del periodo) Guido decise di dare un tocco di misteriosità al linguaggio e infatti lo chiamò Python (in italiano Pitone).
1414
I linguaggi di programmazione:I linguaggi di programmazione:Cenni storici Cenni storici −− 9 9
• Python è free
• Python è portabile
• Python è veloce
• Python gestisce la memoria automaticamente
• Python ha una sintassi chiara
• Python è ricco di librerie
• La NASA usa python per implementare i sistemi di controllo delle proprie missioni
1515
Da basso verso alto livelloDa basso verso alto livello
• In informatica si parla di programmazione di basso programmazione di basso livellolivello quando si utilizza un linguaggio molto vicino alla macchina
• Si parla invece di programmazione di alto livelloprogrammazione di alto livello quando si utilizzano linguaggi più sofisticati ed astratti, slegati dal funzionamento fisico della macchina
• Si viene così a creare una gerarchia di linguaggi, dai meno evoluti (il linguaggio macchina o l’assembler) ai più evoluti (PascalPascal, Perl,Perl, JavaJava, PythonPython, etc.)
1616
Linguaggi di programmazioneLinguaggi di programmazionedi alto livello di alto livello −− 1 1
• Consentono al programmatore di trattare oggetti complessi senza doversi preoccupare dei dettagli della particolare macchina sulla quale il programma viene eseguito
• Richiedono un compilatorecompilatore o un interpreteinterprete che sia in grado di tradurre le istruzioni del linguaggio di alto livello in istruzioni macchina di basso livello, eseguibili dal calcolatore
• Un compilatore è un programma traduttore complesso, infatti… …mentre esiste una corrispondenza biunivoca fra istruzioni in
assembler ed istruzioni macchina …ogni singola istruzione di un linguaggio di alto livello
corrisponde a molte istruzioni in linguaggio macchina: quanto più il linguaggio si discosta dal linguaggio macchina, tanto più il lavoro di traduzione del compilatore è difficile
1717
Linguaggi di programmazioneLinguaggi di programmazionedi alto livello di alto livello −− 2 2
• I linguaggi che non dipendono dall’architettura della macchina offrono due vantaggi fondamentali: i programmatori non devono cimentarsi con i dettagli
architetturali di ogni calcolatore i programmi risultano più semplici da leggere e da
modificare
portabilitàportabilità, leggibilitàleggibilità, manutenibilitàmanutenibilità
1818
Linguaggi di programmazioneLinguaggi di programmazionedi alto livello di alto livello −− 3 3
• Eventuale svantaggio dell’uso dei linguaggi di alto livello è la riduzione di efficienza
È possibile utilizzare successioni di istruzioni macchina diverse per scrivere programmi funzionalmente equivalenti: il programmatore ha un controllo limitato sulle modalità con cui il compilatore traduce il codice
Tuttavia… i compilatori attuali ricorrono a trucchi di cui molti programmatori ignorano l’esistenza
• La ragione fondamentale per decretare la superiorità dei La ragione fondamentale per decretare la superiorità dei linguaggi di alto livello consiste nel fatto che la maggior linguaggi di alto livello consiste nel fatto che la maggior parte dei costi di produzione del software è localizzata nella parte dei costi di produzione del software è localizzata nella fase di manutenzione, per la quale leggibilità e portabilità fase di manutenzione, per la quale leggibilità e portabilità sono crucialisono cruciali
1919
Linguaggi di programmazioneLinguaggi di programmazionedi alto livello di alto livello −− 4 4
• Sulla base dell’ambito in cui si colloca il problema da risolvere, è opportuno adottare un linguaggio piuttosto che un altro:
Calcolo scientifico: Calcolo scientifico: Fortran, pythonpython
Intelligenza artificiale:Intelligenza artificiale: Prolog, Lisp, pythonpython
Applicazioni gestionali: Applicazioni gestionali: Cobol, SQL, pythonpython
2020
I programmi traduttori I programmi traduttori −− 1 1
• Affinché un programma scritto in un qualsiasi linguaggio di programmazione sia comprensibile (e quindi eseguibile) da parte di un calcolatore, occorre tradurlo dal linguaggio originario al linguaggio della macchina
• Ogni traduttore è in grado di comprendere e tradurre un solo linguaggio
• Il traduttore converte il testo di un programma scritto in un particolare linguaggio di programmazione (sorgentesorgente) nella corrispondente rappresentazione in linguaggio macchina (eseguibileeseguibile)
2121
I programmi traduttori I programmi traduttori −− 2 2
• Compilatore:Compilatore: opera la traduzione di un programma sorgente (scritto in linguaggio di alto livello) in un programma direttamente eseguibile dal calcolatore PRIMA si traduce tutto il programmaPRIMA si traduce tutto il programma POI si esegue la versione tradottaPOI si esegue la versione tradotta
• Interprete:Interprete: traduce ed esegue il programma sorgente, istruzione per istruzione Traduzione ed esecuzione sono intercalateTraduzione ed esecuzione sono intercalate
2222
I programmi traduttori I programmi traduttori −− 3 3
2323
Il compilatore Il compilatore
• Eseguire un programma scritto in un linguaggio compilatoEseguire un programma scritto in un linguaggio compilato
Il programma P scritto in linguaggio L viene dato in ingresso a un programma PComp
PComp è il programma compilatore del linguaggio L (ad esempio il programma compilatore del CC)
L’esecuzione da parte di un calcolatore di PComp su P (dove P è il dato di ingresso) produce Pexe FASE di FASE di COMPILAZIONECOMPILAZIONE (compile timecompile time)
L’esecuzione da parte di un calcolatore di Pexe su particolari dati in input produce i relativi risultati FASE FASE di ESECUZIONEdi ESECUZIONE (run timerun time)
LINGUAGGIO MACCHINA e LINGUAGGIO MACCHINA e ASSEMBLERASSEMBLER
Una CPU “MINIMA” Il linguaggio macchina di “MINIMA” Il linguaggio Assembler per “MINIMA”
Istruzioni di una CPU minimaIstruzioni di una CPU minima
• Insieme minimale di istruzioni• Ogni istruzione memorizzata in una
parola di memoria
BUS
Dati
Programma in
linguaggio macchina
RAM
PCIR
CI
CPU R0
.......
ALU
ALU riconosce la prossima istruzione e chiama il CI corrispondente
R1
R7
RC
3 tipi di istruzioni macchina:
1) di trasferimento tra RAM e registri di calcolo della CPU
2) aritmetiche: somma,differenza, moltiplicazione, e divisione
3) di controllo (confronto, salto e stop)
Attenzione:
• Le istruzioni vengono eseguite una di seguito all'altra nell'ordine in cui esse sono memorizzate nella RAM
• Il terzo gruppo di istruzioni (confronto e salto) permette di modificare questo ordine.
Istruzioni di trasferimento: registri ⇔ RAM
01234543ALU
R0
R1
R2
LOAD
STORE
PC
IR LOAD
15
STORE151617
1717
16
LOAD
43
STORE
17
STOP
Formato:in binario!codice-op n. registro indirizzo parola RAM
8 bit 4 bit 20 bit
1 parola LOAD 00000000STORE 00000001
Codici:
00000000 0000 0000000000000000001000000001 0010 00000000000000000101Esempio:
ARITMETICHEeseguono somma, differenza, moltiplicazione e divisione usando i registri come operandi
INTADD 00000010 FLOATADD 00000011INTSUB 00000100 FLOATSUB 00000101INTMULT 00000110 FLOATMULT 00000111INTDIV 00001000 FLOATDIV 00001001
Ri
RjCI
FORMATO:
codice-op reg 1 reg 2
8 bit 4 bit 4 bit inutilizzati
1 parola
00000010 0011 0001 xxxxxxxxxxxxxxxx00000011 0011 0001 xxxxxxxxxxxxxxxxEsempio:
Confronto paragona il contenuto di 2 registri Ri ed Rj e:•se Ri < Rj mette -1 nel registro RC•se Ri = Rj mette 0 in RC•se Ri > Rj mette 1 in RC
Ri
RjCCf
RC
INTCOMPARE 00100000FLOATCOMPARE 00100001Codici:
FORMATO
codice-op reg 1 reg 2
8 bit 4 bit 4 bit inutilizzati
1 parola
00100000 0010 0101 xxxxxxxxxxxxxxxx00100001 0010 0101 xxxxxxxxxxxxxxxxEsempio:
Saltoistruzioni che permettono di saltare ad un’altra istruzione del programma a seconda del contenuto di RC (cioè a seconda del risultato di un confronto)BRLT 01000001 BRNE 01000100BRLE 01000010 BRGE 01000110BREQ 01000011 BRGT 01000101 BRANCH 10000000
Anche salto incondizionato!
FORMATO
codice-op indirizzo RAM
8 bits inutilizzati 20 bit
1 parola
01000001 xxxx 0000000000000000100110000000 xxxx 00000000000000001010Esempio:
• BRLT J: se RC=-1 pone P=J altrimenti incrementa P di 1
• BRLE J:se RC<1 pone P=J altrimenti incrementa P di 1
• BREQ J:se RC=0 pone P=J altrimenti incrementa P di 1
• BRGT J:se RC=1 pone P=J altrimenti incrementa P di 1
• BRGE J:se RC>-1 pone P=J altrimenti incrementa P di 1
STOP
termina il programma
STOP 10000001Codice:
FORMATO
codice-op
8 bits inutilizzati
1 parola
10000001 xxxxxxxxxxxxxxxxxxxxxxxxEsempio:
esempioscriviamo un programma in linguaggio macchina che:
• trasferisce il contenuto delle 2 parole della RAM di indirizzi 64 e 68 nei registri R0 ed R1
• somma i contenuti dei registri R0 ed R1
• trasferisce il risultato nella parola della RAM all’indirizzo 60
388
5660646872
Copia 68 in R1Somma R0 e R1Copia 64 in R0
102010241028103210361040
Copia R0 in 60
RAM
..0100110..01000
111000 111100
10000001000100 1001000
000000000001..0100010000001000000001....000000000000..010000
11111111001000000000010000000100100000010001000000110010000010000
000000010000..001111
RAM
byteparola
byte
Problemi del linguaggio macchina:
• i programmi in binario sono difficili da scrivere, capire e modificare.
• il programmatore deve occuparsi di gestire la RAM (visto che I loro indirizzi devono far parte del programma) : difficile ed inefficiente.
primo passo → Assembler
Caratteristiche dell’Assembler• codici mnemonici per le operazioni
• nomi mnemonici (identificatori) al posto degli indirizzi RAM dei dati
• nomi mnemonici (etichette) al posto degli indirizzi RAM delle istruzioni (usati nei salti)
• avanzate: tipi dei dati INT e FLOAT (normalmente non presenti)
codice-op mnemonici:• trasferimento: LOAD (RAM → CPU) e STORE (CPU → RAM)• aritmetiche: INTADD,INTSUB,INTMULT,INTDIV,FLOATADD,FLOATSUB,FLOATMULT,FLOATDIV• test: INTCOMPARE,FLOATCOMPARE • salto: BREQ,BRGT,BRLT,BRGE,BRLE, BRANCH • terminazione: STOP
stesso esempio del linguaggio macchina
Z : INT ; X : INT 38;Y : INT 8 ;LOAD R0 X;LOAD R1 Y;INTADD R0 R1;STORE R0 Z;
dichiarazioni degli identificatori dei dati
istruzioni assemblerRiga vuota
• Il programma scritto in assembler rispecchia molto da vicino il programma scritto in linguaggio macchina
• Inoltre è facile riconoscere la sua struttura e rappresentarla con un diagramma di flusso
• ATTENZIONE: il programma assembler non può essere eseguito direttamente dall'hardware di un computer!!!!!!
esempiocarica due valori dalla RAM, li somma e mette il risultato al posto del maggiore dei 2 numeri sommati (nel caso siano uguali, non importa in quale dei due si mette la somma)
X: INT 38;Y: INT 8; LOAD R0 X; LOAD R1 Y; LOAD R2 X; INTADD R2 R1; INTCOMPARE R0 R1; BRGE maggiore; STORE R2 Y; STOP;maggiore: STORE R2 X; STOP;
flowchart
INTADD R2 R1;
STORE R2 X; STORE R2 Y;
SI NO
test
R0 ≥ R1?
LOAD R0 X;LOAD R1 Y;LOAD R2 X;
STOP
esempioCaricato in memoria un valore reale x ne calcola il valore assoluto e lo stampa.
ZeroF: 0
X: ?
Absx: ?
R0: ?
R1: ?
?RC:
RAM
CPU
ZeroF : FLOAT 0;X: FLOAT -234.43;AbsX: FLOAT; LOAD R0 ZeroF; LOAD R1 X; FLOATCOMPARE R1 R0; BRGE maggiore; FLOATSUB R0 R1; STORE R0 AbsX; BRANCH fine;maggiore: STORE R1 AbsX;fine: STOP;
-234.43
0
-234.43
-1
234.43
234.43
flowchart
FLOATSUB R0 R1;STORE R0 AbsX;
STOP;
SINO R1 ≥ R0?
STORE R1 AbsX;maggiore:
LOAD R0 ZeroF;LOAD R1 X;
FLOATSUB R0 R1;STORE R0 AbsX;
SINO R1 ≥ R0?
STORE R1 AbsX;
condizione o test
Esempio potenza
Leggere un reale x ed un intero positivo n e calcolare la potenza xn
Cicli e complessità
X: FLOAT 3;N: INT 4;Ris: FLOAT ;Uno : INT 1;Unofl: FLOAT 1.0;LOAD R0 Uno; INTSUB R0 R0;LOAD R1 Uno;LOAD R2 X;LOAD R3 N;LOAD R4 Unofl;
X: 3,0N: 4
Ris: ?
R0: 0R1: 1
?RC:
Uno: 1Unofl: 1,0
R2: 3,0R3: 4R4: 1,0
Ciclo: INTCOMPARE R3 R0; BREQ Esci; FLOATMULT R4 R2; INTSUB R3 R1; BRANCH Ciclo;Esci: STORE R4 Ris; STOP;
Durante il ciclo: R4 = XN-R3
Alla fine del ciclo: R3=0 ed R4 = XN
X: 3,0N: 4
Ris: ?
R0: 0R1: 1
?RC:
Uno: 1Unofl: 1,0
R2: 3,0R3: 4R4: 1,0
1
3,03
1
9,02
1
27,01
1
81,00
0
81,0
All’inizio del ciclo: R4 = XN-R3
FLOATMULT R4 R2;INTSUB R3 R1;
NO
flowchart
SIR3 = R0?
INTSUB R0 R0;
STORE R4 Ris;STOP
Ciclo:
Esci:
LOAD R0 Uno;LOAD R1 Uno;LOAD R2 X;LOAD R3 N;
LOAD R4 Unofl;
Nel programma precedente, per calcolare xn, il ciclo viene ripetuto n volte.
Il numero di operazioni eseguite, e quindi il tempo calcolo richiesto, aumenterà proporzionalmente con l’aumentare di n.
Diciamo che il programma ha complessità tempo O(n).
Vediamo un altro modo per calcolare xn.
Useremo un metodo più veloce che usa la rappresentazione binaria bk-1bk-2 …b1b0 di N per scomporre la potenza come segue
00
11
22
11
00
11
22
11
2222
22...22
... bbbb
bbbbN
XXXXXX
kk
kk
kk
kk
⋅⋅⋅⋅==
−−
−−
−−
−− ++++
dove
==
=1 se0 se1
22
i
ib
bXb
X i
ii
Per calcolare: 1...
00
11
22
11 2222 ⋅⋅⋅⋅⋅=
−−
−− bbbbN XXXXX
kk
kk
R2R2R2 221
⋅==← XX
R2R2R2 422
⋅==← XX
R2R2R2 823
⋅==← XX
=⋅==← 1 seR2R4
0 seR4R40
0200
bbX b
XXX ==← 120
R20.1R4 ←
=⋅==⋅← 1 seR2R4
0 seR4R41
122 00
11
bbXX bb
=⋅==⋅⋅← 1 seR2R4
0 seR4R42
2222 00
11
22
bbXXX bbb
• Il registro R3 ha inizialmente il valore N• Ad ogni esecuzione viene diviso per 2 (per
assumere alla fine il valore 0 che fa uscire dal ciclo)
• Ad ogni iterazione viene calcolato in R5 il resto della divisione per 2 di R3 (il bit b
i)
• Il registro R4 viene moltiplicato per R2 solo se R5 è diverso da zero
X: FLOAT 3;N: INT 5;Ris: FLOAT ;Due : INT 2;Unofl: FLOAT 1.0;App: INT;LOAD R0 Due; INTSUB R0 R0;LOAD R1 Due;LOAD R2 X;LOAD R3 N;LOAD R4 Unofl; LOAD R5 Due;
X: ?N: ?
Ris: ?
R0: ?R1: ?
?RC:
Due: 2Unofl: 1,0
R2: ?R3: ?R4: ?R5: ?
3,05
202
3,05
1,02
Ciclo:INTCOMPARE R3 R0; BREQ Esci; INTSUB R5 R5; INTADD R5 R3; MOD R5 R1; INTCOMPARE R5 R0; BREQ Pari; FLOATMULT R4 R2;Pari: FLOATMULT R2 R2; INTDIV R3 R1; BRANCH Ciclo;
X: 3,0N: 5
Ris: ?
R0: 0R1: 2
?RC:
Due: 2Unofl: 1,0
R2: 3,0R3: 5R4: 1,0R5: 20
1
51
1
3,0
9,02
1
020
0
81,01
1
011
1
243,0
6561,00
0
Ciclo:INTCOMPARE R3 R0; BREQ Esci; INTSUB R5 R5; INTADD R5 R3; MOD R5 R1; INTCOMPARE R5 R0; BREQ Pari; FLOATMULT R4 R2;Pari: FLOATMULT R2 R2; INTDIV R3 R1; BRANCH Ciclo;
X: 3,0N: 5
Ris: ?
R0: 0R1: 2
?RC:
Due: 2Unofl: 1,0
R2: 3,0R3: 5R4: 1,0R5: 20
1
51
1
3,0
9,02
1
020
0
81,01
1
011
1
243,0
6561,00
0
STORE R3 APP;LOAD R6 APP;INTDIV R6 R1;INTMULT R6 R1;INTSUB R5 R6;
Esci: STORE R4 Ris; STOP;
X: 3,0N: 5
Ris: ?
R0: 0R1: 2
0RC:
Due: 2Unofl: 1,0
R2: 6561,0R3: 0R4: 243,0R5: 1
243,0
INTSUB R5 R5;INTADD R5 R3;MOD R5 R1;
NO
flowchart
SIR3 = R0?
INTSUB R0 R0;
STORE R4 Ris;STOP;
R5 = R0? SINO
FLOATMULT R4 R2;
FLOATMULT R2 R2;DIV R3 R1;
Quante volte viene ripetuto il ciclo?
LOAD R0 Due;LOAD R1 Due;LOAD R2 X;LOAD R3 N;
LOAD R4 Unofl;LOAD R5 Due;
All’inizio R3 = n (intero), ad ogni iterazione R3 è diviso per 2 e ci si ferma quando R3 = 0, ossia quando il un numero di iterazioni k eseguite è tale che 2k ≤ n ma 2k+1 > n.
Quindi il ciclo viene ripetuto k ≤ log2 n volte.
Il tempo calcolo richiesto aumenterà proporzionalmente a log2 n.
Diciamo che il programma ha complessità tempo O(log2 n).
NumIstr(n)
log2 n
n
n2
n3
2n
10n
Come aumenta il tempo al variare di n. (Processore a 1 Mips (milioni di istruzioni al secondo).)
Tabelle complessità
n=10
3 µs
10 µs
100 µs
1 ms
1 ms
17 min
n=100
6 µs
100 µs
10 ms
1 s
>1016 anni>1092 anni
n=1000
9 µs
1 ms
1 s
17 m
n=106
18 µs
1 s
278 ore
>3·107 anni
n=109
27 µs
17 m
>3·104 anni
Complessità
• Problemi INTRATTABILI: problemi computazionali la cui complessità è espressa da una funzione esponenziale o più che esponenziale
La CPU non “capisce” l’assembler !!
il programma assembler deve essere tradotto in un programma macchina
macchina hardware
assemblatore
programma assembler
interprete
Programma assembler P Dati D
Gli stessi risultati che si otterrebbero eseguendo il programma P con i dati D
Siccome la CPU “MINIMA” è una CPU virtuale noi usiamo un interprete per eseguire i programmi assembler.
Esistono quindi programmi che hanno programmi come dati.
OSSERVAZIONE
Ha senso quindi cercare un programma Test che sia in grado di leggere un qualsiasi programma P e i relativi dati D e dire se, eseguendo il programma P con i dati D, esso termina oppure entra in un ciclo infinito e quindi non termina.
READ INP P
READ INP D
P(D) termina?
WRITE OUT “SI” WRITE OUT “NO”
Test
Il programma Coppia legge un programma P e stampa due copie dello stesso programma P.
Componendolo con un interprete Iterpr otteniamo il programma Riflex che con input un programma P lo esegue con dati il programma stesso P.
READ INP P
WRITE OUT PCoppia
WRITE OUT P
RiflexCoppia
Interpr
P
P P
P
P P
P(P)
Usando il programma ipotetico Test ed il programma Riflex costruiamo un programma Assurdo nel modo seguente.
READ INP P
WRITE OUT RiflexPrefixWRITE OUT P
Assurdo
Prefix
TestREAD INP RISP
RISP?Invert Si
No
Invert
P
Riflex P
P
Riflex P
Si o No
Si o No
Quindi il programma Assurdo, con input un qualsiasi programma P, si comporta nel modo seguente:
Se P con input P non termina allora Assurdo con input P termina.
Se P con input P termina allora Assurdo con input P non termina.
Se Assurdo con input Assurdo non termina allora Assurdo con input Assurdo termina.
Se Assurdo con input Assurdo termina allora Assurdo con input Assurdo non termina.
COMPUTABILITA'
• Problemi computazionali INSOLUBILI: problemi per i quali non esiste alcun programma che li risolva
7878
L’arte della programmazione L’arte della programmazione −− 1 1
AnalisiAnalisi
ProgrammazioneProgrammazione
• La soluzione di un problema tramite un programma è un procedimento che non si esaurisce nello scrivere codice in un dato linguaggio di programmazione, ma comprende una fase di progetto, che precede, e di verifica, che segue, la scrittura del codice Definizione del problema Algoritmo per la soluzione del problema
Codifica Debugging Validazione Documentazione Manutenzione
7979
L’arte della programmazione L’arte della programmazione −− 2 2
• Definizione del problemaDefinizione del problema Definizione degli ingressi e delle uscite
quali variabiliquale dominio per ogni variabile
Risoluzione delle ambiguità Scomposizione in (sotto−)problemi più semplici
• Definizione dell’algoritmoDefinizione dell’algoritmo Soluzione in pseudocodice Soluzione mediante diagramma a blocchi strutturato
8080
L’arte della programmazione L’arte della programmazione −− 3 3
• CodificaCodifica Traduzione dell’algoritmo in istruzioni del linguaggio di
programmazione
• DebuggingDebugging, correzione degli errori sintattici e semantici Errori sintattici
Espressioni non valide o non ben formate nel linguaggio di programmazione
Errori semanticiComportamento non aderente alle aspettative/alla intenzionalità del programmatore
8181
L’arte della programmazione L’arte della programmazione −− 4 4
• ValidazioneValidazione Test su tutte le condizioni operative del programma Test su input estremi (es., vettori di dimensione 0 o 1,
variabili nulle)
• DocumentazioneDocumentazione Inserimento di commenti esplicativi nelle varie parti del
programma per facilitarne la comprensione (dopo molto tempo dalla stesura o per terze persone)
• ManutenzioneManutenzione Modifica del programma per soddisfare al cambiamento
delle specifiche con cui deve operare
8282
I commenti I commenti −− 1 1
• Perché commentare e documentare i programmi?
I programmi vengono utilizzati più volte nel corso di tempi lunghi (mesi, anni) per…
…fare cambiamenti (aggiunta di caratteristiche)
…risolvere errori
Commentare il programma serve a rendere chiaro ed evidente lo scopo delle diverse parti del codice
8383
I commenti I commenti −− 2 2
• Inoltre:
Si devono evitare commenti inutili
Si deve evitare di inserirne “troppo pochi”
• Un buon metodo per verificare il livello di documentazione è quello di leggere solo i commenti (e non il codice) ed ottenere una chiara idea su “cosa fa un programma e come lo fa”