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”