mosaic

manipola oggetti primitivi (ruota e unisci)

regole:

1. un mosaico è uno dei pezzi primitivi

2. si ottiene ruotano di 90° in senso orario un mosaico

3. si ottiene unendo un mosaico a destra di un mosaico della stessa altezza

4. niente altro è un mosaico

sintassi di espressioni che denotano mosaici

E è una espressione se

E è a

E è b

E è ruota(E1) e E1 è un’espressione

E è unisci(E1,E2), e E1 e E2 sono espressioni

niente altro è espressione

<espressione>::= a | b

| ruota(<espressione>)

| unisci(<espressione>,<espressione>)

semantica delle espressioni

specifica il mosaico denotato da un’espressione

unisci(ruota(ruota(b)),a) che mosaico definisce?

funzioni definite dall’utente

fun controruota(x) = ruota(ruota(ruota(x)))

fun impila(x,y) = controruota(unisci(ruota(y),ruota(x)))

dichiarazioni locali

let <dichiarazione> in <espressione> end

let

fun controruota(x) = ruota(ruota(ruota(x)))

fun impila(x,y) = controruota(unisci(ruota(y),ruota(x)))

in

impila(controruota(b),ruota(b))

denota il mosaico precedente

espressione let olet-binding

nomi per valori definiti dall’utente

val <nome> = <espressione>

let val x = E1 in E2 end

dice che l’occorrenza del nome x nell’espressione E2 rappresenta il valore di E1

let val no = controruota(b)

val se = ruota(b)

in

impila(no,se)

end

dichiarazione di valore

espressione precedente con nomi più significativi

discussione: abbiamo lasciato in sospeso molti punti

– notazione: nell’espressione unisci(a,b) la funzione unisci è scritta prima dei suoi argomenti; esistono altre notazioni?

– valutazione: nel valutare l’espressione E1 e E2 si valuta prima E1 e poi E2 ? e se la prima espressione influenza la seconda?

– funzioni: cosa succede se una funzione è definita in termini di se stessa?

– ambito dei nomi: cambiare i nomi può cambiare il significato di una espressione?

– checking: cosa succede se una funzione riceve meno argomenti di quelli previsti, o argomenti di tipo diverso?

Notazioni per le espressioni

-infissa (a+b)

-prefissa (+ab)

costante o variabile

op applicato a a e b si scrive op a b

- postfissa (ab+)

associatività e precedenza

come si valuta a + b * c ??

- parentesi- precedenza fra operatori- raggruppati da sinistra verso destra

operatori associativi a sinistra (es. sottrazione)

operatori associativi a destra (es. potenza)

rappresentazione ad albero di un’espressione

radice -> operatore

per ogni operando

figlio della radice -> sottoalbero per l’operando

b*b-4*a*c

_

*

b b

*

c

4

*

a

alberi astratti:

denotano la struttura dell’espressione senza tener conto della notazione

l’albero dell’esempio precedente è lo stesso per le tre notazioni

prefissa: -*bb**4ac

infissa: b*b-4*a*c

postfissa: bb*4a*c*-

Valutazione di espressioni

in generale, per valutare (E op F)

si valutano E ed F in qualche ordine e

si applica ai valori risultanti l’operatore op

- valutazione come riscrittura di alberi

- valutazione tramite stack

valutazione come riscrittura di alberi

infissa

7 * 7 – 4 * 2 * 3 =

49 – 4 * 2 * 3 =

49 – 8 * 3 =

49 – 24 =

25

postfissa

7 7 * 4 2 * 3 * – =

49 4 2 * 3 * – =

49 8 3 * – =

49 24 – =

25

_

*

7 7

*

3

4

*

2

_

49 *

3*

4

_

49 *

38

2

_

49 2425

valutazione tramite stack

espressione in notaz. postfissa

leggere da sinistra a destra

se c’è una costante c, push(c)

se c’è un operatore binario op, push(pop op pop)

risultato = top

valutazione tramite stack

espressione stack azione

7 7 * 4 2 * 3 * – 7 push 7

7 7 * 4 2 * 3 * – 7 7 push 7

7 7 * 4 2 * 3 * – 49 mult

7 7 * 4 2 * 3 * – 49 4 push 4

7 7 * 4 2 * 3 * – 49 4 2 push 2

7 7 * 4 2 * 3 * – 49 8 mult

7 7 * 4 2 * 3 * – 49 8 3 push 3

7 7 * 4 2 * 3 * – 49 24 mult

7 7 * 4 2 * 3 * – 25 subtr

Dichiarazioni e applicazioni di funzione

funzioni come corrispondenze

f : A -> B

mappa gli elementi del dominio in quelli del codominio

f è totale se associa ad ogni elemento di A uno di B

f è parziale se è indefinita per qualche elemento di A

funzioni come algoritmi

una dichiarazione di funzione è formata da- nome- parametri- regola per calcolare il risultato partendo dai parametri

dichiarazione:

fun <nome> (<parametri formali>) = <corpo>

applicazione:

<nome>(<parametri attuali>)

es. fun successore (n) = n+1; successore(2+3)

valutazione (attivazione) innermost

<nome>(<parametri attuali>) è calcolata:

- valuta le espressioni in <parametri attuali>

- sostituisci i risultati ai parametri formali nel corpo della funzione-valuta il corpo- restituisci il valore come risposta

la tecnica è detta anche chiamata per valore

valutazione selettiva

if <condizione> then <espr1> else <espr2>

fun abs(n)= if n >= 0 then n else 0-n

fun or(n)= if x = true then true

else if y = true then true

else false

funzioni ricorsive

una funzione f è ricorsiva se il suo corpo contiene un’applicazione di f (o se può attivare se stessa, anche indirettamente); ad esempio

fun fib(n)=if (n=0 or n=1) then 1 else fib(n-1)+fib(n-2)

la funzione è valutata come sempre: i parametri attuali sono calcolati e sostituiti nel corpo della funzione

esempio: fib(4).

ricorsione lineare

una funzione f è ricorsiva lineare se una attivazione di f(a) può attivare al più una singola attivazione di f; ad esempio

fun fattoriale(n)=if n=0 then 1 else n*fattoriale(n-1)

la funzione è valutata in due fasi:– winding, in cui sono iniziate nuove attivazioni– unwinding, in cui le attivazioni rilasciano il controllo (LIFO)

ricorsione tail

una funzione f è tail ricorsiva se restituisce un valore (senza richiedere risorsione) oppure il risultato di una attivazione ricorsiva; ad esempio

fun g(n,a)=if n=0 then a else g(n-1, n*a)

in questo caso tutto il lavoro è fatto nella fase di winding

ambito lessicale: significato dei nomi in un programma

rinominare in modo consistente le variabili non cambia il valore di un’espressione; per rinominare occorre esprimere il concetto di variabile locale (bound)

fun successore(x)= x+1fun successore(n)= n+1

cosa succede se la dichiarazione di funzione fa riferimento a nomi non locali??

fun sommay= x+y

successore(5) è sempre 6

y non è locale; dipende dal contesto.

regole di ambito lessicale (lexical scope rules):

usano il testo del programma in cui si trova una dichiarazione di funzione per determinare il contesto di valutazione dei nomi non locali

let val x=2 in x+x end

il valore di una espressione non cambia se sostituiamo tutte le occorrenze di una variabile nell’ambito di un binding di x con una nuova variabile

binding di x

tutte le occorrenze di x in questa espressione sono nello scope (ambito) del binding (legame)

let val x=3 in let val y=4 in x*x+y*y end end

let val x=2 in let val x=x+1 in x*x end end

se rimpiazzo x con y nel binding più interno ottengo

let val x=2 in let val y=x+1 in y*y end end

l’ambito del binding di y include le due occorrenze di y in x*x+y*y

l’ambito del binding di x include le due occorrenze di x in x*x+y*y

tipo di un’espressione:

indica i valori che essa può rappresentare e le operazioni che possono essere applicate

una espressione (un oggetto) può avere più di un tipo??

– livello macchina: i valori supportati direttamente dall’architettura sono i tipi elementari (con operazioni diverse)– livello del linguaggio: tipi strutturati o aggregati (con costruttori di tipo)– livello utente: raggruppamenti di dati e funzioni con nomi (classi)

costruttori di insiemi (ognuno con la sua sintassi, gli elementi dell’insieme costruito, le operazioni ammesse):

prodotto: AB = {(a,b) | aA, b B}

primo(a,b) secondo(a,b)

funzione: f:AB

es: intintint (insieme di tutte le funzioni

che associano un intero a una coppia di interi)

sequenza: dato l’insieme A, la chiusura di Kleene (A*) sono tutte le ennuple formate a partire da A

sistemi di tipi

un insieme di regole per associare un tipo alle espressioni di un linguaggio; il sistema rigetta un’espressione se non può associare un tipo

esempio

espressione = variabile, costante, E+F, E-F, E*F, E/F

regole di tipo =– i nomi di variabili che cominciano con una lettera fra I e N sono di tipo int– tutti gli altri nomi sono di tipo real– un numero è real se contiene il punto decimale; tutti gli altri sono int–se E ed F sono dello stesso tipo, allora E+F, E-F, E*F, E/Fsono espressioni dello stesso tipo

di che tipo è I+J ?? di che tipo è X+Y ??di che tipo è X+J ??

operatori aritmeticia ogni operatore op è associata una regola che specifica il tipo di un’espressione E op F, partendo dai tipi di E ed F

overloadingsimboli di operatori comuni (come + o *) sono sovraccarichi, cioè hanno significati diversi a seconda del contesto in cui sono usati.

+: intintint oppure *: intintint

coercion (conversione forzata)

cosa succede se sommo un int e un real??

tipi e controllo degli errori (type checking)

garantisce che le operazioni in un programma siano applicate in modo proprio

si verifica un errore di tipo se una funzione di tipo ST è applicata a un elemento a che non è di tipo S

un programma eseguito (o compilato) senza errori di tipo si dice type safe rispetto ai tipi

– controllo statico (sistema forte)– controllo dinamico (sistema debole)

introduzione a ML

le espressioni, le funzioni e i let binding usati finora sono quelli di ML

datatype direzione= nord | sud | est | ovest

fun sensoorario(x)=

if x=nord then est

else if x=est then sud

else if x=sud then ovest

else nord;

valori associati al tipo direzione

datatype binalbero=

foglia | nonfoglia of binalbero * binalbero

foglia

nonfoglia(foglia, foglia)

nonfoglia(foglia, nonfoglia(foglia, foglia))

definizione ricorsiva

fun

contafoglie(foglia)= 1 |

contafoglie(nonfoglia(s,t))= contafoglie(s)+contafoglie(t)

– scrivere la funzione che dice se un albero è una foglia– scrivere la funzione che estrae il sottoalbero destro e sinistro di un albero

funzione ricorsiva che conta le foglie dell’albero

datatype intalbero=

vuoto | nodo of int * intalbero * intalbero

albero binario di ricerca

10

162

15

0 19

9

10

162

15

16

15

15

162

15

10

162

15

9

10

162

15

0

9

fun inserisci(k, vuoto) = nodo(k, vuoto, vuoto) |inserisci(k, nodo(n, s, t)) =

if (k<n) then nodo(n, inserisci(k, s), t)else if (k>n) then nodo(n, s, inserisci(k, t))else nodo(n, s, t);

fun appartiene(k, vuoto) = false |appartiene(k, nodo(n, s, t)) =

if (k<n) then appartiene(k, s)else if (k>n) then appartiene(k, t)else true;