Programmazione II - Lezione 11groups.di.unipi.it/~daniele/teaching/pr2-10/pr2-11.pdf ·...

Programmazione IILezione 11

Daniele Sgandurra

[email protected]

23/11/2010

1/30 Programmazione II Lezione 11 23/11/2010

Sommario

1 Strutturare il ControlloEspressioniComandiControllo di Sequenza


Strutturare il Controllo

Parte I

Strutturare il Controllo


Strutturare il ControlloEspressioniComandiControllo di Sequenza

Obiettivi

Capire come si realizzano le sequenze di controllo nei linguaggi di altolivello.

Espressioni:

sintassi: notazioni;semantica: valutazione.

Comandi:

assegnamenti.

Controllo sequenza:

espliciti, condizionali, iterativi;programmazione strutturata.

Ricorsione:

ricorsione in coda.



Espressioni

Espressione

Entita sintattica la cui valutazione produce un valore oppure non termina, nelqual caso l’espressione e indefinita.

Presenti in tutti i linguaggi, anche quelli dichiarativi.

Non sono necessariamente numeriche:

booleane, alfanumeriche (su stringhe), etc.

Esempio: 4 + 3 ∗ 2:

risulta ovvio che la valutazione produca il valore 10;assunzione implicita: precedenza di ∗ su +, altrimenti il risultatosarebbe stato diverso (14).



Sintassi delle Espressioni

Espressione, composta da:

una singola entita: costante, variabile:

es.: true, 27.34, altezza, contoCorrente.

operatore applicato ad una espressione:

es.: !(flag), -saldoConto.

operatore applicato a due (o piu) espressioni:

es: b+1/2, ((i>0) and !(found)).



Notazione Infissa

Notazione piu comune (dalla Matematica).

Il simbolo dell’operatore e posto fra le espressioni che rappresentano i suoi

operandi:

es.: moltiplicazione per z della somma di x e y : (x + y) ∗ z .

Per evitare ambiguita:

parentesi;regole di precedenza.

Per alcuni linguaggi, la notazione infissa e solo un’abbreviazione per la

notazione prefissa:

in C++: a + b e abbreviazione di a.operator+(b);in Ada: a + b abbreviazione per +(a,b).



Notazione Prefissa

Notazione polacca prefissa (W. Lukasiewicz):

il simbolo dell’operatore precede le espressioni che rappresentano isuoi operandi:

es.: somma: +(x y) oppure semplicemente + x y;es.: applicazione funzioni f(x y) oppure f x y.

Non servono parentesi ne regole di precedenza purche sia nota l’arieta di

ogni funzione/operatore:

si applica sempre l’operatore che precede immediatamente glioperandi:

es.: * + a b + c d significa, in notazione infissa:(a+b)*(c+d)

Notazione polacca di Cambridge: anche gli operatori tra parentesi:

(* (+ a b) (+ c d))



Notazione Postfissa

Notazione polacca inversa: il simbolo dell’operatore segue le espressioni

che rappresentano i suoi operandi:

es: a b + c d + *

Vantaggi delle notazioni polacche:

si possono usare per rappresentare facilmente operatori diqualunque arieta (al contrario della notazione infissa);si possono evitare le parentesi:

utili solo per motivi di leggibilita, non per l’ordine divalutazione.

valutazione piu semplice.



Semantica delle Espressioni

La modalita di valutazione (quindi, la semantica) varia a seconda dellanotazione scelta per la sintassi.

Rappresentazione interna delle espressioni: albero.

Notazione infissa: evitare l’ambiguita:

definendo la precedenza;definendo associativita;usando parentesi.



Notazione Infissa: Precedenza e Associativita

Naturalezza della scrittura / maggiore difficolta di valutazione.

Chiarire la precedenza tra tutti gli operatori:

es.: 4+3*5 deve dare 19 e non 35.

Usare parentesi per imporre la precedenza:

esempio precedente: 4+(3*5) e non (4+3)*5.

Operatori diversi:

es.: x=4 and y=5 senza parentesi porta a un errore di tipo in Pascalperche interpretato come x=(4 and y)=5.

Associativita:

come intendere l’espressione 15-5-3?

(15-5)-3 o 15-(5-3).

la maggior parte degli operatori associa a sinistra a destra:

eccezione: potenza ** associativa da destra verso sinistra:

5**3**2 significa 5(32) e non (53)2.



Notazione Prefissa: Valutazione Espressioni

Scansione da sinistra a destra e uso di una pila. Algoritmo:

1 Leggi il prossimo simbolo e mettilo sulla pila.

2 Se il simbolo e un operatore, inizializza il contatore C alla sua arieta etorna al passo 1.

3 Se il simbolo e un operando decrementa C .

4 Se C 6= 0 torna al passo 1.

5 Se C = 0:

applica l’ultimo operatore inserito sulla pila agli operandisuccessivamente inseriti, memorizzando il risultato in R, rimuovidalla pila operandi e operatore, inserisci R sulla pila;se i simboli sulla pila sono terminati allora salta al passo 6;inzializza C a n −m, con n arieta dell’operatore in cima e mnumero di operandi presenti sopra l’operatore;torna al passo 4.

6 Se la sequenza di termini da leggere non e vuota torna a 1.



Notazione Postfissa: Valutazione Espressioni

Scansione da sinistra a destra e uso di una pila.

Piu semplice: non serve controllare la presenza degli operandi perl’operatore inserito dato che vengono letti prima.

Algoritmo:

1 Leggi il prossimo termine e mettilo sulla pila.2 Se il simbolo e un operatore applicalo agli operandi immediatamente

precedenti sulla pila, memorizza il risultato in R, elimina operandi eoperatore dalla pila, memorizza il valore di R sulla pila.

3 Se la sequenza ancora da leggere non e vuota torna a 1.4 Se il simbolo letto e un operando torna a 1.

In entrambi i casi (notazione prefissa e postfissa), bisogna conoscerepreventivamente l’arieta di ogni operatore.



Valutazione delle Espressioni

Espressioni rappresentate da alberi sintattici:

nodi interni: operatori;nodi foglia: operandi semplici;sotto-alberi radicati in un nodo N: operandi per espressioni di livelloinferiore.

Notazioni lineari precedenti: corrispondono a visite diverse:

simmetrica;anticipata;differita.

Risultato dell’analisi sintattica nei linguaggi compilati.

In altri linguaggi si trasforma in notazione polacca prima della valutazione.



Ordine di Valutazione delle Sotto-Espressioni (1)

Trascurabile in Matematica, importante in Informatica.

Effetti collaterali: azione che influenza i risultati parziali o finali.

L’ordine di valutazione degli operandi e rilevante ai fini del risultato:

es.: (a+f(b)) * (c+f(b)) .assenti nei linguaggi dichiarativi;se presentei, si specifica l’ordine: es., Java impone la valutazione dasinistra a destra.

Aritmetica finita: riordinando i termini delle espressioni si possono

causare:

errori di overflow;errori dovuti alla precisione.




Valutazione degli operandi:

valutazione eager: prima valutare gli operandi poi applicare l’operatore ai

valori ottenuti:

alcune operazioni possono essere definite anche se alcuni suoioperandi non lo sono (ad es., i condizionali): a == 0 ? b : b/a.

valutazione lazy: non valutare gli operandi prima dell’operatore; al

momento della sua valutazione si decidera quali devono essere valutati e

quali no:

piu costosa da implementare.

valutazione corto-circuitata:

es. a == 0 || b/a > 2;valutazione lazy: si calcola il valore finale senza valutare tutti glioperandi;adottata in Java, C, Ada ma non in Pascal.




Ottimizzazione:

l’ordine influenza l’efficienza dell’esecuzione del codice; es:

a = vettore [ i ] ;b = a∗a+c∗d ;

nella seconda assegnazione meglio valutare prima c*d perche ilvalore per a potrebbe essere ancora non disponibile (piu accessi inmemoria);messa in atto dai compilatori purche la semantica sia preservata.

Pragmatica: particolari sulla semantica del linguaggio sono spesso:

nascosti,poco chiari,dipendenti dall’implementazione (compilatore),

per cui, meglio usare tutti i mezzi per eliminare le fonti di ambiguita.



Comandi

Comando

Entita sintattica la cui valutazione non necessariamente restituisce un valore,ma puo aver un effetto collaterale.

Caratteristica dei linguaggi imperativi.

Fissato uno stato di partenza σ:

la valutazione di un comando puo cambiare σ come effettocollaterale;la valutazione di un’espressione produce un valore (e possibili effetticollaterali).

Scopo di un comando: modifica dello stato.

Comando di assegnamento: unita elementare nel meccanismo dicomputazione.



Variabile

In Matematica: la variabile e una incognita (valore sconosciuto).

In Informatica, dipende dal paradigma:

paradigma imperativo:

variabile modificabile: contenitore (locazione) dotato di nomee che puo contenere valori solitamente di tipo omogeneo;modifiche di valore tramite comandi di assegnamento (inMatematica il valore di un’incognita non e modificabile).

paradigma ad oggetti:

variabile riferimento (reference o object model): meccanismodi accesso ad un valore memorizzato altrove (heap)simile al concetto di puntatore, ma questo non deve esseremanipolabile.

paradigma funzionale:

variabile: identificatore che denota un valore.

paradigma logico:

idem: una volta creato un legato tra il nome della variabile eun valore questo non e piu modificabile.



Assegnamento (1)

Comando che permette di modificare il valore di una variabilemodificabile (e quindi lo stato).

Tipico dei linguaggi imperativi. Esempio (Pascal):

X := 2

Dopo l’esecuzione la locazione associata al nome X conterra il valore 2che sovrascrive il precedente.

La modifica dello stato e un effetto collaterale.

La valutazione di per se non restituisce, di norma, alcun valore.



Assegnamento (2)

Esempio (Pascal):

X := X + 1

Dopo l’esecuzione la locazione associata al nome X conterra il precedentevalore aumentato di 1.

Possibile perche le due occorrenze di X hanno un significato diverso:

occorrenze a destra indicano dei valori;occorrenze a sinistra indicano i contenitori (le locazioni).

A destra dell’assegnamento ci sono r-valori (r sta per right):

contenuti nelle locazioni.

A sinistra dell’assegnamento ci sono l-valori (l sta per left):

(indirizzi di) locazioni (contenitori di valori);dipende dal linguaggio di programmazione quali espressioni possonodeterminare un l-valore.



Assegnamento (3)

Semantica: <assegnamento> ::= <exp1> OpAss <exp2>:calcola l’l-valore di <exp1> determinando quindi la locazione loc;calcola l’r-valore, valutando l’espressione <exp2>;modifica il valore contenuto in loc con quello calcolato al passoprecedente.

In alcuni linguaggi (es., C), l’assegnamento e anche un operatore la cuivalutazione restituisce l’r-valore; es.:

x = 2 ;

oltre ad assegnare a x il valore di 2, restituisce il valore 2.In linguaggi con modello a riferimento:

x = e ;

abbiamo che x e un riferimento per l’oggetto ottenuto dalla valutazione di e;diverso dal copiare il valore di e nella locazione associata a x. Es.:

x = y ;

in questo caso, abbiamo che x e y sono due riferimenti per lo stesso oggetto.



Controllo di Sequenza

Comandi espliciti:

composizione (blocco);salto.

Comandi condizionali (o di selezione):

permettono di specificare alternative con cui continuare lacomputazione in dipendenza da condizioni.

Comandi iterativi:

ripetizione di un comando un numero di volte predefinito odipendente dal verificarsi di una condizione.



Controllo esplicito (1)

Comando sequenziale (quasi sempre indicato con “;”):

specifica la sequenza tra due comandi piu semplici: C1; C2:

l’esecuzione di C2 comincia dopo la terminazione di C1.

operatore associativo a sinistra.

Comando composto:

raggruppamento di una sequenza usando delimitatori(begin...end, {...}) usabile al posto di un comando semplice.




Comando di salto (goto):

deriva dal salto incondizionato dell’Assembly:

es.: goto A: l’esecuzione del salto trasferisce il controllo alpunto etichettato da A (es., anche essere un numero di riga).

Dijkstra: “Go to statement considered harmful”.Non essenziale, grazie al teorema di Bohm e Jacopini.I salti a grandi distanze diminuiscono la leggibilita e quindi il riuso ela manutenibilita.Si accorda male con gli altri costrutti.




Salti controllati a distanze brevi presenti in molti linguaggi:

return: ritorno da un sottoprogramma, funzione, metodo;break: uscita da un ciclo o selezione multipla;continue: terminare l’iterazione corrente riprendendo dallaprossima;eccezioni: salto ad un flusso di controllo parallelo.



Comandi Condizionali (if)

Comandi che esprimono alternative nella computazione.

Comando if (introdotto da ALGOL 60):

i f Bexp then C1 e l s e C2

dove Bexp e un’espressione booleana, mentre C1 e C2 sono comandi.

La presenza di if annidati porta ad ambiguita:

i f Bexp1 i f Bexp2 then C1 e l s e C2

Generalmente l’else appartiene all’if piu interno (oppure si usa unterminatore, ad esempio endif).

Alcuni linguaggi utilizzano esplicitamente l’annidamento con la parolachiave elseif.

Comando implementato attraverso i salti condizionati dell’Assembly.



Comandi Condizionali (case)

Comando case (selezione multipla):

c a s e Exp o flabel1 : C1 ;label2 : C2 ;. . .labeln : Cn ;

e l s e Cn+1

dove Bexp e un’espressione di tipo compatibile con quello delle etichette(label1, ...), mentre C1 ... Cn+1 sono comandi.

Tipi ammessi dipendono dai linguaggi e sono in genere scalari.

Piu leggibile degli if annidati.

Realizzato in Assembly attraverso una jump table.

Vantaggio: piu efficiente dell’implementazione degli if annidati.

Svantaggio: la jump table puo consumare spazio se i valori sono distanti.

Differenti implementazioni:

case (Pascal) e switch (C e derivati).



Controllo di Sequenza

Continua...



Riferimenti

[1] Linguaggi di programmazione: principi e paradigmi (Cap. 6).

Maurizio Gabbrielli, Simone Martini.


Programmazione II - Lezione 11groups.di.unipi.it/~daniele/teaching/pr2-10/pr2-11.pdf ·...

Documents

Transcript of Programmazione II - Lezione 11groups.di.unipi.it/~daniele/teaching/pr2-10/pr2-11.pdf ·...