Strutturare il controllo

Controllo del flusso

Espressioni:

• notazioni
• valutazione
• problemi

Comandi

• assegnamento
• sequenziale
• condizionale

Comandi iterativi Ricorsione

Espressioni

Un’espressione un’entità sintattica la cui valutazione produce un valore oppure non termina, nel qual caso l’espressione è indefinita. – infissa a + b – prefissa (polacca) + a b – postfissa (polacca inversa) a b +

Semantica delle espressioni: notazione infissa

Precedenza fra gli operatori:

a + b * c ** d ** e / f ?? if A < B and C < D then ?? (in Pascal Errore se A,B,C,D non sono tutti booleani)

Di solito operatori aritmetici precedenza su quelli di confronto che hanno precedenza su quelli logici (nono pascal) APL, Smalltalk: tutti gli op hanno eguale precedenza (si devono usare le parentesi)

Associativita'

15 - 4 - 3 ?? (15 -4) -3 5 ** 2 ** 3 ?? 5 ** (2 ** 3)

Non sempre ovvio (apl: 15-4-3 diventa 15-(4-3))

Semantica delle espressioni: notazione postfissa

Molto piu semplice della infissa

• non servono le regole di precedenza
• non servono regole di associativita'
• non servono parentesi
• valutazione semplice usando una pila

Valutazione usando una pila

1. Leggi il prossimo simbolo dell’exp. e mettilo sulla pila
2. Se il simbolo letto è un operatore: – applica a operandi immediatamente precedenti sulla pila, – memorizza il risultato in R, – elimina operatore ed operandi dalla pila – memorizza il valore di R sulla pila.
3. Se la sequenza da leggere non è vuota torna a (1).
4. Se il simbolo letto un operando torna a (1).

Semantica delle espressioni: notazione prefissa

Molto piu semplice della infissa:

• no regole di precedenza
• no regole di associativita
• no parentesi
• valutazione smplce usando una pila (piu complicata di quella postfissa, dobbiamo contare gli operandi che vengono letti)

Valutazione delle espressioni

• Le espressioni internamente sono rappresentate da alberi • Visite diverse dell’albero producono le varie notazione lineari: – Simmetrica -> infissa – Anticipata -> prefissa – Differita -> postfissa

A partire dall'albero il compilatore prodice il codice oggetto oppure l'interprete valuta l'espressione In entrambi i casi l'ordine di valutazione delle sottoespressioni e' importante per vari motivi: – Effetti collaterali (modifiche di var che non sono ) – Aritmetica finita (overflow) – Operandi non definiti () – Ottimizzazione

Es: a+f(b)) * (c+f(b))

se f(n) = {x++ return x} chiamate diverse della stessa funzione possono provocare una modifica di valori e channo effetti diversi. Altro es: a+f(b)) * (c+f(b)) Se f modifica b il risultato da sinistra a destra e diverso di quello da destra a sinistra • In alcuni linguaggi non sono ammesso funzioni con effetti laterali nelle espressioni • In Java è specificato chiaramente l’ordine (da sinistra a destra)

Operandi non definiti

in C:

a == 0 ? b : b/a

presuppone una valutazione lazy: si valutano solo gli op strettamente necessari. E'importante sapere se il ling adotta una valutazione lazy oppure eager (tutti gli operandi sono comunque valutati)

Valutazione corto-circutio

Nel caso delle espressioni booleane spesso la vlutazione lazy è detta corto-circuito:

a == 0 || b/a > 2

– Con valutazione lazy (corto circuito, come in C) => VERO – Con valutazione eager => possibile errore

Visto che eager controlla tutti i parametri puo stare facendo una divisione con zero se a=0

p := lista;
while (p <> nil ) and (pˆ.valore <> 3) do
p := pˆ.prossimo;

(in pascal da errore)

Comandi

Un comando e'un entita' la cui valutazione non necessariamente restituisce un valore, ma puo avere un affetto collaterale

• effetto collaterale: modifica stato della computazione senza restituire un valore

I comandi:

• sono tipici del paradigma imperativo
• non sono presenti nei paradigmi funzionali e logici
• in alcuni casi restituiscono un valore

Variabili

Nei ling imperativi (pascal, c, Ada…) la variabile e' modificabile (contenitore di val, normalmente di un certo tipo ed ha un nome)

Il val nel contenitore puo essre modificato mediante il comando di assegnamento

Assegnamento

x:=2 X = X +1 si noti il diverso ruolo delle X

• la X di sinistra e'un l-value, ossia un valore che denota una locazione (e puo comparire a sinistra di un assegnamento)
• la X di destra e'un r-value ossia un valore puo'essere contenuto in una locazione (e puo comparire a destra di un assegnamento)

In generale exp1 Opass exp2

Normalmente la valutazione di un assegnamento non restituisce un valore ma produce un ``side effect’’ (effetto collaterale) – In alcuni linguaggi l’assegnamento resituisce anche un valore. In C: x= 2 restituisce 2 quindi possiamo scrivere Y = X = 2

Modelli di variabile diversi

Linguaggi funzionali (Lisp, ML, Haskell, Smalltalk): modello analogo a quella della matematica. Una variabile denota un valore e non è modificabile • Linguaggi logici: modello analogo a quello dei funzionali, ma con la possibilità di modificare (entro certi limiti) il valore associato alla variabile • Clu: modello a oggetti, chiamato anche modello a riferimento • Java: – variabile modificabile per i tipi primitivi (interi, booleani ecc.) – modello a riferimento per i tipi classe

Modello a riferimento

na variabile è un riferimento ad un valore, che ha un nome X —-> 2 Analogo alla nozione di puntatore, ma senza le possibilità di manipolazione delle locazioni dei puntatori: le locazioni qui possono essere manipolate solo implicitamente

A destra, se gli oggetti riferiti da X e Y sono modificabili (es.oggetti Java) modifiche fatte attraverso la X si riflettono sull’oggetto riferito da Y

Operatori di assegnamento

X := X+1

• doppio accesso alla locazione di a (a meno di ottimizzazione del compilatore)
• poco chiaro; in alcuni casi puo’ causare errori

Espressioni e comandi (l. imperativi)

lgol 68: expression oriented – non c’e’ nozione separata di comando – ogni procedura restituise un valore

Pascal: comandi separati da espressioni – un comando non puo’ comparire dove e’ richiesta un’espressione – e viceversa

C: comandi separati da espressioni – espressioni possono comparire dove ci si aspetta un comando – assegnamento (=) permesso nelle espressioni

Ambiente e memoria

Due variabili diverse possono denotare lo stesso oggetto (aliasing) – come si rappresenta questa situazione in termini di stato ? – la semplice funzione Stato: Nomi —> Valori non basta

La semantica dei linguaggi imperativi usa: – Ambiente: Nomi —-> Valori Denotabili – Memoria: Locazioni —> Valori Memorizzabili

Nei linguaggi imperativi sono presenti tre importanti domini semantici: – Valori Denotabili (quelli a cui si può dare un nome) – Valori Memorizzabili (si possono memorizzare) – Valori Esprimibili (risultato della valutazione di una exp.)

Nota: I linguaggi funzionali usano sono l’ambiente

Comandi per il controllo sequenza

Comandi per il controllo sequenza esplicito – ; – blocchi – goto Comandi condizionali – if – case Comandi iterativi – iterazione determinata (for) – iterazione indeterminata (while)

Comando sequenziale e blocchi

C1 ; C2 (significa che viene prima eseguito c1 e poi c2) – E’ il costrutto di base dei linguaggi imperativi – Ha senso solo se ci sono side-effects – in alcuni linguaggi il ``;’’ più che un comando sequenziale è un terminatore

Algol 68, C: Il valore di un comando composto e’ quello dell’ultimo comando.

Comando composto – può essere usato al posto di un comando semplice – Algol 68, C (no distinzione espressione-comando): il valore di un comando composto e’ quello dell’ultimo comando

… …
} end```
````

### GOTO

Acceso dibattito negli anni 60 sull'utilita del goto
Alla fine considerato dannoso

## Programmazione strutturata

- GOTO sconfitto perche'considerato contrario alla programmazione strutturata
- Nata negli anni 70 antesignana della programmazione OOP

Caratteristiche:

- design top down
- codice modulare
- nomi identificatori significativi
- uso esteso commenti
- tipi di dato strutturato
- comandi per il controllo strutturato
- ...

### Comandi di controllo strutturati

Un solo punto di ingressoe un solo punto d'uscita

- la scansione lineare del testo corrisponde al flusso di esecuzione
- fondamentale per la comprensione del codice

Comandi strutturati

- for if while case
- non e'il caso del goto

Permette codice strutturato e non spaghetti code

### Comando condizionale

`if B then C_1 esle C_2`

Introdotto con algol 60
Varie regole per evitare ambiguita' in presenza di if annidati (es. `if B then C1 else C2 endif`)

Case:
Discendente del goto di fortran e del switch di algol 60

- Molte versioni nei vari linguaggi

Il case, in confronto all'if-then-else e' piu leggibile e piu efficiente se compilato bene

## Iterazione

iterazione e ricorsione sono due meccanismi fondamentali che permettono di ottenere formalismi di calcolo Turing completi. Senza di essi avremmo automi a stati finiti.

Iterazione:

- indeterminata: cicli controllati logicamente (while, repeat)
- determinata: cicli controllati numericamente (for, do) con numero di ripetizioni del ciclo determinate all'inizio di esso

### Iterazione indeterminata

while condizione do comando

Introdotto in Algol-W rimasto in pascal e moli altri linguaggi

In pascal esiste anche la versione post-test:

repeat comando until codizione

Equivalente a `while not condizione do comando`

L'iterazione e'indeterminata perche'il numero di iterazioni non e' noto a priori.
L'iterazione indeterminata permette il potere espressivo di una MdT

### Iterazione determinata

for indice := inizio TO fine BY passo DO … END ```

Non si possono modificare: indice, inizio, fine, passo all'interno del loop e'determinato (al momento dell'exec del ciclo) il numero di ripetizioni del ciclo Il potere espressivo e'minore rispetto all'iterazione indeterminata: non si possono esprimere computazioni che non terminano In molti ling (es il C) il for non e'un costrutto di iterazione determinata (in C il for e' un while mascherato)

Semantica del for

Supponendo passo positivo:

1. valuta le espressioni inizio e fine e ``congela’’ i valori ottenuti
2. inizializza I con il valore di inizio;
3. se I > fine termina l’esecuzione del for altrimenti
   • si esegue corpo e si incrementa I del valore di passo;
   • si torna a (3).

In alcuni lig se il passo e'negativo si usa una sistassi diversa: downto (Pascal), reverse (ada) Per non fare istruzioni diverse, si puo usare un IC: IC = (fine - inizio + passo) / passo

Cicli controllati numericamente

I vari lig differiscono nei seguenti aspetti:

1. possibilita' di modificare gli indici
2. Numero di iterazioni (dove avviene il controllo indice<fine)
3. incremento negativo
4. valore di indice al termine del ciclo
5. possibilita di salto dall'esterno all'interno

(il do in fortran permette quasi tutto, con conseguenti problemi di leggibilita')

Se in un ling c'e' solo il for allora esso non e'turing completo (manca la possibilita' di fare loop infiniti) Se considerassimo solo le exec finite e' possibile usare solo il for? NO -> funz di hackerman