Semantica Operazionale di un
frammento di Java: intro
estensione (con piccole varianti) di quella di FP
|
1
Semantica operazionale
 modello di esecuzione
– importanti soprattutto le strutture che
compongono lo stato
 simile alle strutture a run-time della JVM,
che esegue il byte-code prodotto dal
compilatore
2
Semantica operazionale
 piu’ orientata all’implementazione
– Per esempio le strutture dati che si usano per
descrivere lo stato e le transizioni
3
Cosa aggiungiamo
 le gerarchie di classi
– trattiamo ereditarietà ed overriding
 l’attributo “static” per variabili e metodi
– esistono variabili e metodi propri della classe,
oltre a quelli propri degli oggetti
 i costruttori
– metodi che vengono invocati al momento della
creazione di una istanza di classe
4
In particolare
 Espressioni per accedere ai nomi del tipo
Path.I
variabile
Path.I(ListP) chiamata di metodo
• Path generico (puo’ riferirsi ad un oggetto, una
classe, puo’ essere vuoto)
• Dobbiamo formalizzare delle regole di accesso e
ricerca dei nomi abbastanza complicate
5
Regole di Visibilita’ dei Nomi
 Sono quelle verificate staticamente dal
compilatore (si chiamano anche regole di
scoping)
 Verifica che ogni accesso ad un nome (di
variabile o metodo) sia legale, ovvero il
legame tra le dichiarazioni e l’uso dei nomi
 Sono utilizzate a tempo di esecuzione per
cercare le associazioni giuste per i nomi
6
Regole di Visibilita’ dei Nomi
 E’ necessario richiamare le regole di base (le
vedremo per bene nella semantica di MP)
 Sono un po’ piu’ complicate di quelle che avete
visto fino ad ora (erano semplificate a scopo
didattico)
 Complicate dalla coesistenza di nomi statici e
d’istanza
 Tralasciamo i vincoli imposti dagli specificatori di
accesso (public, private)
7
A cosa servono?
 Stiamo scrivendo un metodo
 Come facciamo a capire se un accesso del seguente tipo e’
legale?
Path.I
variabile
Path.I(ListP) chiamata di metodo
 A quale identificatore I mi riferisco?
 Dove vado a cercare l’associazione giusta?
8
Nota
 E’ complicato perche’ I potrebbe essere
statico o d’istanza o potrebbe essere una
variabile locale del metodo
 Dipende dal Path e dal tipo di metodo (statico
o d’istanza) in esecuzione
9
Cosa puo’ indicare un path?
 Accesso diretto (path vuoto) I
•Riferimento ad un oggetto
this.I
p1.I
•Riferimento ad una classe
BankAccount.I
10
Per semplicare
 Vediamo le regole per le variabili
 Per i metodi e’ analogo
 Non trattiamo per ora ereditarieta’
11
Path Vuoto
 I potrebbe essere
 una variabile locale o un parametro del
metodo in esecuzione
 una variabile che si vede dalla classe c
(se il metodo e’ statico di c)
 una variabile che si vede dall’oggetto l su
cui il metodo e’ eseguito (se il metodo e’
d’istanza o e’ un costruttore)
12
Cosa e’ visibile da un oggetto?
 I suoi nomi d’istanza
 I nomi statici dichiarati nella classe a cui
appartiene (perche’ sono condivise tra
tutti gli oggetti)
13
Esempio
public class BankAccount{
private double balance;
private int miocodice;
private static int codice;
}
•Quali variabili sono direttamente visibili dai metodi
d’istanza o dai costruttori della classe?
14
Costruttore
public BankAccount(double initial){
balance=initial;
miocodice=codice;
codice++;
}
• Riferimento diretto alla variabile d’istanza miocodice
(this non e’ necessario) si riferisce implicitamente a quella dell’oggetto
creato
•Riferimento diretto alla variabile statica codice che e’ condivisa e
visibile tra tutti gli oggetti della classe (Bankaccount non e’ necessario)
•Riferimento diretto al parametro
15
Cosa e’ visibile da una classe?
 I suoi nomi statici
 Non sono visibili nomi d’istanza (sono
relativi agli oggetti)
16
Esempio
public class BankAccount{
private double balance;
private int miocodice;
private static int codice;
}
•Quali variabili sono direttamente visibili dai metodi
statici della classe?
•Solo la variabili statica codice che appartiene alla classe
17
Metodo statico di BankAccount
public static void incr(int x){
codice=x;
}
•Accesso diretto alla variabile statica codice
che appartiene alla classe del metodo
• Non potremo accedere direttamente alla variabile d’istanza
miocodice (non ci sono oggetti di riferimento)
18
Path Classe
 Vediamo quello che si vede dalla classe
 Per esempio dal main:
BankAccount.codice=1; (accesso legale)
BankAccount.balance=1; (accesso illegale)
19
Path Oggetto
 Vediamo quello che si vede dall’oggetto
 Per esempio dal main:
BankAccount p1=new Bankaccount(1000);
p1.codice=1; (accesso legale)
p1.balance=1; (accesso legale)
20
Conclusione
 La coesistenza di nomi statici e d’istanza
complica il linguaggio
 Cosa succede con l’ereditarieta’?
21
Semantica informale
Se c1 è una sottoclasse di (estende) c2
• le variabili e metodi statici di c2 (e delle sue
superclassi) sono visibili direttamente da c1
•variabili e metodi di istanza di c2 (e delle sue
superclassi) diventano anche variabili e metodi di
istanza di c1 (a meno di overriding)
22
Cosa cambia?
 Da una classe sono direttamente visibili nell’ordine
i propri nomi statici e quelli delle superclassi
 Di conseguenza: dagli oggetti di una classe sono
direttamente visibili nell’ordine
i propri nomi statici e quelli delle superclassi
23
Semantica statica
 nella formalizzazione trascuriamo tutti gli
aspetti legati alla semantica statica
– in particolare, quelli che darebbero origine a
messaggi di errore durante la compilazione
– tipi, visibilità dei nomi, vincoli sull’overriding
 semantica semplificata solo per programmi
che supererebbero con successo l’analisi
statica
24
Nota
 La semantica non e’ completa
 Tratteremo solo le regole che differiscono
da quelle gia’ viste (blocchi, if, while…)
 Inoltre non consideriamo specificatori di
accesso (supponiamo che sia tutto public)
25
Lo stato
 pila di attivazioni s
– per la valutazione dei metodi
– pila dei record di attivazione dei metodi
 heap z
– contiene gli oggetti (istanze di classi)
 ambiente delle classi r
– contiene le classi dichiarate prima dell’inizio
dell’esecuzione
26
Ambiente delle classi r
 Cosa deve associare ad ogni classe?
 le informazioni per accedere alla superclasse (per
implementare le regole di visibilita’ dei nomi)
 le variabili ed metodi statici (condivise da tutti gli
oggetti della classe)
 le informazioni per creare oggetti istanze della
classe (quali variabili e metodi d’istanza)
27
Ambiente delle classi r
 r è una funzione da identificatori di classe a
descrizioni di classe
– r : Cenv
– Cenv = Id -> Cdescr
 cos’è una descrizione di classe?
 vediamo prima la sintassi (semplificata) che
usiamo per le dichiarazioni di classe
28
Sintassi
Class_decl := class Id extends Id {
Static_var_decl_list
Static_meth_decl_list
Inst_var_decl_list
Inst_meth_decl_list
Costruttore
}
•La sintassi del costruttore (sequenza di assegnamenti),
non nome non parametri
• Inoltre assumiamo che ogni classe sia definita come
29
sottoclasse di qualcosa (per default Object)
Descrizione di classe
E’ una quintupla:
Cdescr = Id * Frame * Menv * Frame * Menv
superclasse
variabili istanza
variabili statiche
metodi istanza
metodi statici
30
Osservazione
 Il frame delle variabili statiche e l’ambiente dei
metodi statici appartengono alla classe (per
esempio il frame contiene il valore effettivo delle
variabili etc..)
 variabili e metodi statici sono condivisi tra tutti gli
oggetti istanza della classe
31
Osservazione
 Il frame delle variabili d’istanza e l’ambiente dei
metodi d’istanza stanno nella classe solo come
“informazione” (non contengono valori, ma
verranno utilizzati per creare gli oggetti)
 variabili e metodi d’istanza sono propri degli
oggetti istanza della classe, vanno mantenuti nella
descrizione degli oggetti (come vedremo nello
heap)
32
 è una funzione j che mantiene associazioni fra
– identificatori (di variabili)
– valori
• interi, booleani
• locazioni (puntatori ad oggetti)
 è una tabella modificabile (il valore associato ad
un
identificatore puo’ cambiare)
33
Operazioni su frame
 newframe() crea un frame vuoto
 l’operazione bind(j, i, v) estende j inserendo l’associazione tra i e v
 l’operazione update(j, i, v) modifica in j l’associazione per i (che
deve esistere)
 l’operazione copy(j) costruisce una copia di j
 l’operazione defined(j, i) dice se j contiene un’associazione per i
 per ottenere il valore di una variabile, si applica il frame all’Id, j(i)
34
Ambiente di metodi m
 m è una funzione da identificatori di metodo a
descrizioni di metodo
– m : Menv
– Menv = Id -> Mdescr
 cos’è una descrizione di metodo?
35
Descrizione di metodo
 deve contenere le informazioni per eseguirlo
– lista dei parametri formali
– corpo
– una informazione per implementare le regole di
visibilita’ dei nomi, ovvero per sapere dove andare a
cercare gli identificatori
36
In particolare
 manteniamo un puntatore
– alla classe (se metodo statico)
– all’oggetto a cui appartiene (se metodo d’istanza)
 Tramite il puntatore potremmo
differenziare le
regole di ricerca dei nomi nei due casi
37
Dichiarazione di metodo: sintassi
Method_decl := Id (Idlist) Blocco
– ignoriamo i tipi
Mdescr = Idlist * Blocco * ( Loc | Id )
parametri formali
corpo del metodo
nome di classe
puntatore a oggetto
38
Operazioni sugli ambienti di metodi
e di class
 cemptyenv() costruisce un ambiente di classi “vuoto”
 cbind((r:Cenv), (i:Id), (c:Cdescr)) estende r associando ad





i il valore c
cdefined(r, i) dice se r è definita per i
memptyenv() costruisce un ambiente di metodi “vuoto”
mbind((m:Menv), (i:Id), (m:Mdescr)) estende m associando
ad i il valore m
mdefined(m, i) dice se m è definita per i
instantiate((m:Menv), (l: Loc)) crea un nuovo ambiente m1
diverso da m perché tutte le descrizioni di metodi
39
contengono l’oggetto l
La heap z
 z è una funzione da locazioni a descrizioni di
istanza (oggetto)
– z : Heap
– Heap = Loc -> Odescr
 cos’è una descrizione di oggetto?
40
Descrizione di oggetto
 deve contenere
 puntatore alla classe di appartenenza
 valore delle variabili d’istanza proprie dell’oggetto
 le informazioni per eseguire metodi d’istanza e
costruttori(le loro descrizioni)
41
Descrizione di oggetti
 z è una funzione da locazioni a descrizioni di
istanza (oggetto)
Odescr = Id * Frame * Menv
classe
variabili di istanza
metodi di istanza
42
Osservazione
I metodi d’istanza nel modello visto in precedenza
 erano mantenuti in modo comune a tutti gli oggetti (nella descrizione
della classe)
 erano invocati tramite il puntatore che lega l’oggetto alla classe
•

La modifica semplifica il problema della ricerca dei nomi dovuto alla
coesistenza di variabili e metodi statici e d’istanza
 I metodi d’istanza stanno gia’ nell’oggetto e possono essere trattati in
modo uniforme alle variabili d’istanza
 Il puntatore alla classe servira’ invece per accedere alle variabili ed ai
metodi statici
43
Operazioni sulla heap
 newheap() genera una heap vuota
 newloc(z) genera una nuova locazione in z
 hbind((z:Heap), (l:Loc), (o:Odescr)) estende
z associando ad l il valore o
44
La pila di attivazioni s
 s è una pila di records di attivazione di metodi
 Last In First Out (LIFO)
 Ogni record di attivazione descrive uno dei metodi
annidati che sono in esecuzione
 Quello al top e’ l’unico attivo
 Gli altri sono sospesi
45
Attivazione/disattivazione
 Invocazione di metodo: viene messo al top della
pila un corrispondente record di attivazione
 Terminazione di metodo: viene tolto dal top della
pila il corrispondente record di attivazione
 in modo che il record di attivazione del metodo
chiamante (metodo che e’ stato sospeso) torni al
top della pila, ovvero possa riprendere
l’esecuzione
46
Record di attivazione
 il record di attivazione descrive il metodo in esecuzione
– oggetto o classe a cui il metodo appartiene
– pila di frames (blocchi annidati) che descrivono sia le variabili
locali che le associazioni tra parametri formali ed attuali
Record = ( Id | Loc ) * Stack(Frame)
classe
oggetto
variabili locali
47
Osservazione
 il puntatore all’oggetto o alla classe indicano se il
metodo e’ d’istanza o statico rispettivamente
– e’ utilizzato per andare a cercare i nomi in base alle
regole di visibilita’
48
La pila di attivazioni s
 s è una pila di records di attivazione di metodi
– s : Astack
– Astack = Stack (Record)
 il record di attivazione
Record = ( Id | Loc ) * Stack(Frame)
classe
oggetto
variabili locali
49
Operazioni sulle pile ( di record o
frame)
 emptystack() genera una pila vuota
 top((p:Stack(x)) restituisce l’elemento di tipo x in
testa a p
 pop((p:Stack(x)) modifica p eliminando
l’elemento in testa
 push((p:Stack(x),(e:x)) modifica p inserendo
l’elemento e in testa
 empty((p:Stack(x)) verifica se p è vuota
50
Uno stato (1)
puntatore ad oggetto
codice blocco f1
codice blocco f2
codice blocco f3
C
A
a 23
f1 (y,z)
C
b
c 5
f2 (w)
C
d ?
e ?
f3 ()
f4 (x)
?
?
C ()
?
codice blocco f4
codice blocco C
B
A
Object
 Ambiente delle classi
51
Osservazioni
 la classe C e’ sottoclasse di A
 Il frame delle variabili statiche contiene i valori
attuali delle variabili
 L’ambiente dei metodi statici contiene le
descrizioni dei metodi (puntano a C)
 La parte che descrive variabili e metodi d’istanza
(incluso il costruttore) e’ un prototipo (valori ?),
servono per creare gli oggetti
52
Uno stato (2)
x
d 3
e
C
f3 ()
f4 (x)
C ()
stack
heap
puntatori al codice dei metodi
 Pila e heap (è in esecuzione il metodo d’istanza f4
di una istanza di C)
53
Osservazioni
 I valori delle variabili d’istanza dell’oggetto
stanno nello heap
 La descrizione dei metodi d’istanza sta
nello heap (puntano all’oggetto stesso,
quando verranno chiamati manterranno il
puntatore)
 Il costruttore e’ trattato come un metodo
d’istanza
54
Cosa si “vede” in questo stato
x
d 3
e
C
f3 ()
f4 (x)
C ()
stack
heap
puntatori al codice dei metodi
 tutti i nomi delle classi
– attraverso queste, le variabili ed i metodi statici
55
Ricordiamo (visibilita’ dei nomi)
• Da un oggetto sono direttamente visibili solo i propri
nomi d’istanza (inclusi quelli ereditati) e la classe; tramite
questa le variabili statiche sue e delle superclassi
•I metodi d’istanza hanno la visibilita’ dell’oggetto su cui
sono eseguiti (vedi f4)
56
nomi di variabili (nell’ordine)
–stack locale (per esempio x)
–frame dell’oggetto a cui appartiene il metodo (per esempio la
sua varibile d’istanza d)
–frames (statici) della classe C e delle superclassi
(per esempio la varibile statica a della classe C)
come vi accediamo?
–Direttamente dal record di attivazione
–Tramite il puntatore dal record all’oggetto nello heap
–Tramite il puntatore dall’oggetto alla sua classe e poi la catena di
puntatori tra classi
57
Cosa si “vede” in questo stato
x
d 3
e
C
f3 ()
f4 (x)
C ()
stack
heap
 nomi di metodi (nell’ordine)
puntatori al codice dei metodi
– ambiente di metodi dell’oggetto a cui appartiene il metodo
• lui incluso (ricorsione)
– ambienti di metodi (statici) lungo la catena di sottoclassi
58
Metodi statici
•Se fosse in esecuzione un metodo statico (per esempio
f1della classe C) il suo record di attivazione al top dello
stack punterebbe alla classe C
•In questo caso potremmo vedere
 stack locale
frames (statici) della classe C e delle superclassi
come vi accediamo?
–Direttamente dal record di attivazione
–Tramite il puntatore dal record alla sua classe ed
la catena di puntatori alle superclassi
59