Semantica Operazionale di un
frammento di Java: lo stato
estensione (con piccole varianti) di quella in
Barbuti, Mancarella, Turini,
Elementi di Semantica Operazionale,
appunti di Fondamenti di Programmazione
1
Cosa aggiungiamo
 le gerarchie di classi
– ereditarietà ed overriding
 l’attributo “static” per variabili e metodi
– esistono variabili e metodi propri della classe
 i costruttori
– metodi che vengono invocati al momento della
creazione di una istanza di classe
2
Semantica statica
 Trascuriamo tutti gli aspetti legati alla semantica
statica
 Proprietà statiche importanti verranno descritte in
modo informale
 Semantica (semplificata) solo per programmi che
supererebbero con successo l’analisi statica
3
Lo stato
r
s
z
 ambiente delle classi r
– contiene le classi dichiarate prima dell’inizio
dell’esecuzione
 pila di attivazioni s
– per la valutazione dei metodi
– simile alla pila dei record di attivazione nei linguaggi
tradizionali
 heap z
– contiene gli oggetti (istanze di classi)
4
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?
Id
Cdesr
…
…
 vediamo prima la sintassi (semplificata) che usiamo per le
dichiarazioni di classe
5
Dichiarazione di classe: sintassi
Class_decl := class Id extends Id {
Static_var_decl_list
Static_meth_decl_list
Inst_var_decl_list
Inst_meth_decl_list
Costruttore
}
Cdescr = Id * Frame * Menv * Frame * Menv
superclasse
variabili istanza
variabili statiche
metodi statici
Id
metodi istanza
+ costruttore
Frame Menv Frame Menv
6
Il frame j
 è una tabella (estendibile e mutabile) che mantiene
associazioni fra
– identificatori (di variabili)
– valori
• interi, booleani
• locazioni (puntatori ad oggetti)






Id
valori
…
…
newframe()-bind(j, i, v)-- estende j inserendo l’associazione tra i e v
update(j, i, v)-- modifica in j l’associazione per i (che deve esistere)
copy(j)-- costruisce una copia di j
defined(j, i)-- true se j contiene un’associazione per i
j(i)-- applicazione:valore di i in j
7
Ambiente di metodi m
 m è una funzione da identificatori di metodo a descrizioni
di metodo
– m : Menv
– Menv = Id -> Mdescr
Id
Mdescr
…
 cos’è una descrizione di metodo?
 vediamo prima la sintassi (semplificata) che usiamo per le
dichiarazioni di metodo
8
Dichiarazione di metodo: sintassi
Method_decl := Id (Idlist) Blocco
– ignoriamo i tipi
– quando il metodo verrà invocato, dovrà sapere la classe
o l’oggetto a cui appartiene
Mdescr = Idlist * Blocco * ( Loc | Id )
parametri formali
corpo del metodo
puntatore a oggetto
Idlist
nome di classe
body
Loc/Id
9
Operazioni sugli ambienti (metodi e
class) r, m
 cemptyenv() / memptyenv() un ambiente “vuoto”
 cbind(r:Cenv, i:Id, c:Cdescr)/
mbind(m:Menv,i:Id,m:Mdescr) estende r/m con i e c/m
 cdefined(r, i)/mdefined(m, i) true se r/m è definita su i
 instantiate(m:Menv,l:Loc) crea un nuovo ambiente m1
diverso da m perché le descrizioni di tutti i metodi hanno l
come componente loc
 applicazione: r(i)/m(i)
10
La memoria heap z
 z è una funzione da locazioni a descrizioni di
istanza (oggetto)
– z : Heap
– Heap = Loc -> Odescr
Loc
Id
Frame
Menv
 cos’è una descrizione di oggetto?
Odescr = Id * Frame * Menv
classe
variabili di istanza
metodi di istanza
11
Operazioni sulla heap
 newheap()
 newloc(z)-- genera una nuova locazione in z
 hbind(z:Heap,l:Loc,o:Odescr)-- estende z con l e o
 un oggetto viene creato con l’espressione new Id
– genera il valore o:Odescr a partire dalla classe Id
– l = newloc(z)
– hbind(z:Heap,l:Loc,o:Odescr)
– restituisce l
12
La pila di attivazioni s
 s è una pila di records di attivazione di metodi
– s : Astack
– Astack = Stack (Record)
Id
Stack(Frame)
 il record di attivazione
– oggetto o classe a cui il metodo appartiene
– pila di frames (blocchi annidati)
Record = ( Id | Loc ) * Stack(Frame)
classe
oggetto
Attuali + Variabili
locali
13
Operazioni sulle pile (record, frame)
 emptystack()
 top(p:Stack(x))-- restituisce l’elemento in testa a p
 pop(p:Stack(x))-- rimuove l’elemento in testa
 push(p:Stack(x),e:x)-- inserisce e in testa
 empty((p:Stack(x))-- verifica se p è vuota
14
Le strutture dello stato (riepilogo 1)
 Ambiente delle classi
Cenv = Id -> Cdescr
Cdescr = Id * Frame * Menv * Frame* Menv
– cemptyenv()
– cbind((r:Cenv), (i:Id), (c:Cdescr))
– cdefined((r:Cenv),(i:Id))
 Heap
Heap = Loc -> Odescr
Odescr = Id * Frame * Menv
– newheap()
– newloc ((z:Heap))
– hbind((z:Heap), (l:Loc), (o:Odescr))
15
Le strutture dello stato (riepilogo 2)
 Pila delle attivazioni
Astack = Stack (Record)
Record = ( Id | Loc ) * Stack(Frame)
– operazioni delle pile
16
Le strutture (ausiliarie) dello stato
(riepilogo 3)
 Ambiente dei metodi
Menv = Id -> Mdescr
Mdescr = Idlist * Blocco * ( Loc | Id )
– memptyenv()
– mbind((m:Menv), (i:Id), (m:Mdescr))
– mdefined ((m:Menv), (i:Id))
– instantiate((m:Menv), (l: Loc))
 Frames
Frame = Id -> Val
Val = (Bool | Int | Loc)
– newframe()
– copy((j:Frame))
– bind((j:Frame) , (i:Id), (v:Val))
– update((j:Frame) , (i:Id), (v:Val))
– defined((j:Frame), (i:Id))
17
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
 parte statica (classi)
18
Uno stato (2)
x
d 3
e
C
f3 ()
f4 (x)
C ()
stack
heap
puntatori al codice dei metodi
 parte dinamica (pila e heap)
– è in esecuzione il metodo f4 di una istanza di C
19
Cosa si “vede” in questo stato
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
 tutti i nomi delle classi
– attraverso queste, le variabili ed i metodi statici
20
Cosa si “vede” in questo stato
x
d 3
e
C
f3 ()
f4 (x)
C ()
stack
heap
 nomi di variabili (nell’ordine)
puntatori al codice dei metodi
– stack locale
– frame dell’oggetto a cui appartiene il metodo
– frames (statici) lungo la catena di sottoclassi
21
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
22