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
espressione let o
let
let-binding
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
nomi per valori definiti dall’utente
val <nome> = <espressione>
dichiarazione di
valore
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
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
4
c
*
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:
infissa:
postfissa:
-*bb**4ac
b*b-4*a*c
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
postfissa
7*7–4*2*3=
77*42*3*–=
49 – 4 * 2 * 3 =
49 4 2 * 3 * – =
49 – 8 * 3 =
49 8 3 * – =
49 – 24 =
49 24 – =
25
25
_
_
*
*
49
7
7
*
3
*
3
*
4
2
4
_
2
_
49
*
8
49
3
24
25
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
77*42*3*–
77*42*3*–
77*42*3*–
77*42*3*–
77*42*3*–
77*42*3*–
77*42*3*–
77*42*3*–
77*42*3*–
7
77
49
49 4
49 4 2
49 8
49 8 3
49 24
25
push 7
push 7
mult
push 4
push 2
mult
push 3
mult
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+1
fun successore(n)= n+1
successore(5) è sempre 6
cosa succede se la dichiarazione di funzione fa
riferimento a nomi non locali??
fun sommay= x+y
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
tutte le occorrenze di x in questa
espressione sono nello scope
(ambito) del binding (legame)
binding di x
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
let val x=3 in let val y=4 in x*x+y*y end end
l’ambito del binding di x include le
due occorrenze di x in x*x+y*y
l’ambito del binding di y include le
due occorrenze di y in x*x+y*y
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
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:
AB = {(a,b) | aA, b B}
primo(a,b) secondo(a,b)
funzione:
f:AB
es: intintint (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 aritmetici
a ogni operatore op è associata una regola che specifica
il tipo di un’espressione E op F, partendo dai tipi di E ed F
overloading
simboli di operatori comuni (come + o *) sono
sovraccarichi, cioè hanno significati diversi a seconda del
contesto in cui sono usati.
+: intintint
oppure
*: intintint
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 ST è
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
valori associati al tipo direzione
fun sensoorario(x)=
if x=nord then est
else if x=est then sud
else if x=sud then ovest
else nord;
datatype binalbero=
foglia | nonfoglia of binalbero * binalbero
definizione ricorsiva
foglia
nonfoglia(foglia, foglia)
nonfoglia(foglia, nonfoglia(foglia, foglia))
fun
contafoglie(foglia)= 1 |
contafoglie(nonfoglia(s,t))= contafoglie(s)+contafoglie(t)
funzione ricorsiva che conta le
foglie dell’albero
– scrivere la funzione che dice se un albero è una foglia
– scrivere la funzione che estrae il sottoalbero destro e sinistro di
un albero
datatype intalbero=
vuoto | nodo of int * intalbero * intalbero
albero binario di ricerca
15
15
15
2
16
15
16
10
15
2
2
16
0
10
2
16
9
16
10
15
9
15
2
0
16
10
9
19
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;
Scarica

Document