Progetto Parte II
OCAML
Obiettivo
• Interprete del linguaggio didattico (PICO)
in ML
• Riprogettare l’interprete utilizzando le
caratteristiche di OCAML
• In particolare, usare i tipi di dato astratto
• Moduli ed Interfacce
Limiti dell’Interprete
• Funziona…
• Il programma e’ molto a basso livello
• Non e’ organizzato in moduli, ogni parte dipende
dall’implementazione delle altre
• Di conseguenza, risulta difficile capire il codice
• Difficilmente estendibile, modificabile (se per
esempio si dovesse aggiungere istruzioni nel
linguaggio imperativo considerato)
Le strutture run-time
• Le componenti dello stato, env e store sono
realizzate a basso livello
• Sono definite da semplici tipi, insiemi di valori
• Mancano le relative operazioni
• Di conseguenza, non e’ possibile garantire
proprieta’ invarianti delle strutture a tempo di
esecuzione
• Segnalando eventualmente errori
Funzioni di valutazione
semantica
• Per le varie componenti
•
•
•
•
valProg: prog * sigma * mu-> sigma * mu
valCom: com * sigma * mu-> sigma * mu
valDecl: com * sigma * mu-> sigma * mu
valExp: aExp * sigma * mu-> value* sigma * mu
• La loro implementazione dipende dall’implementazione
dell’env (sigma) e dello store (mu)
Frame
Definizione Matematica (astratta): il frame e’ una
funzione
frame: Ide ---> Den
Implementazione:
type fi = Frame of
(string * denotation) list;;
• Definizione molto a basso livello, una lista di
coppie (identificatore, valore)
Svantaggi
• L’implementazione e’ molto distante dalla
definizione astratta
• L’implementazione del Frame (la lista di coppie)
non ha proprieta’ invarianti
• Le funzioni dell’interprete che lavorano sul frame
lavorano direttamente sulla lista di coppie (non
c’e’ astrazione sui dati)
Esempio: proprieta’
• Una lista di coppie (identificatore, valore
denotabile) non necessariamente rappresenta
una funzione
[(x,l1),(y,l2),(x,l3)]
• Qual’e’ il valore della variabile x? Questo non e’
un Frame!
• Bisognerebbe garantire questa proprieta’ per
costruzione
Le Operazioni
• Non e’ possibile dato che le operazioni sono
scollegate dal tipo di dato
• Addirittura alcune operazioni, che si usano nella
definizione astratta della semantica tramite SOS,
non sono neanche direttamente implementate in
modo esplicito
• Per esempio l’operazione di modifica di un
frame….
Modifica di un frame
phi [d/x] (y)= phi (y) se x e’ diverso da y
d se x=y
• La definizione cos`ı data risulta corretta
anche nell’eventualit`a che un legame diverso
da Unbound per x esista gia’
• non e’ molto corretto solo per programmi
sintatticamente corretti
Ambiente: env
• Definizione Astratta: env=Stack(Frames)
Implementazione
type sigma = Stack of
fi list;;
• Definizione molto a basso livello, una lista di frames
• Le funzioni che devono operare sull’env operano
direttamente sulla lista
• Le operazioni di pop(),push(), top() non vengono
fornite
• Anche in questo caso non e’ chiaro quali devono
essere le proprieta’ invarianti della lista di frames
Modifica dell’env
let rec addBind sigma (x,y) =
match sigma with
| Stack [Frame[]] ->
Stack [Frame[(x,y)]]
| Stack ((Frame f)::fs) ->
Stack ((Frame (append f [(x,y)])) ::fs);;
• L’operazione e’ implementata in modo ricorsivo sulla lista
che implementa la pila
• mancano anche alcuni casi come quello della pila vuota, al
solito non e’ garantito dalla definizione della pila che non
possa essere vuota
• L’implementazione dipende dall’implementazione del Frame
(non c’e’ astrazione)
Esempio: valCom
let valCom c (sigma,mu) = match c with
| Block l ->
let (Stack (f::rl),mu1) =
valStmtL l
((match sigma with Stack fl ->
Stack (Frame[]::fl)) ,mu)
in (Stack rl, mu1)
• valuta l nello stato in cui un frame vuoto Frame[]
e’ stato messo al top della pila
• restituisce l’env da cui e’ stato fatto pop (le
variabili del blocco sono locali)
• codice parecchio complicato, lontano dalla
definizione della regola della semantica
Esempio: valExp
• Problemi analoghi anche in altre regole
semantiche, che richiedono operazioni di push e
pop dalla pila, tipo la chiamata di funzione
Stack sl ->
addBind (addBind (Stack
(Frame []::sl)) (f,l)) ("retVal",l1))
Memoria
• Definizione Astratta
mu : Loc ---> Val
IMPLEMENTAZIONE:
type 'a mu = Mem of 'a list ;;
• Definizione molto a basso livello, una lista
polimorfa
• Si usera’ per memorizzare coppie (identificatore,
valore)
Problemi
•
•
•
•
Problemi sono simili a quelli del Frame
Quali sono le proprieta’ di questa lista?
E’ una funzione?
Nel caso della memoria pero’ e’ ancora
piu’ complesso, non solo deve essere una
funzione, ma esiste il problema
dell’allocazione della memoria
Per esempio
• free: Store---> Loc *Store
• restitituisce una nuova locazione libera e
la memoria modificata di conseguenza
(alla nuova locazione viene assegnato il
valore omega)
• Deve esserci una politica per gestire le
locazioni
Come abbiamo visto
• La lista viene usata in questo modo…
[(l0,v1),(l2,v2),(l3,v3)]
• L’operazione di free restituisce l4 e la memoria
[(l0,v1),(l2,v2),(l3,v3),(l4,omega)]
Esiste un uso inteso della lista di coppie che
implementa la memoria, ma non e’ garantito per
costruzione
Progetto
• Usare i tipi di dato astratto di OCAML per
migliorare la struttura del programma
• Parte I: definire moduli che realizzino le
strutture a tempo di esecuzione (lo stato),
frame, memoria, env
• Parte II: riprogrammare le funzioni di
valutazione semantica usando i nuovi tipi di
dato astratti
Moduli ed Interfacce
• per supportare in modo semplice i concetti
di encapsulation e data hiding
• l’interfaccia e’ definita da una module
signature
• l’implementazione (o le) e’ definita da una
module structure
Signature: interfaccia
• dichiara il tipo
• dichiara le operazioni tramite metodi
pubblici, (nome, parametri, tipo)
Structure: implementazione
• implementa il tipo ed i metodi associati
• puo’ contenere definizioni ausiliarie, da
fuori e’ visibile solo quello che e’
specificato nella corrispondente interfaccia
(signature)
• L’implementazione puo’ (deve) garantire
proprieta’ invarianti del tipo di dato
Frame, Memoria, Env
• Per ciascuna componente dare una relativa
interfaccia
• Quali operazioni?
• Operazioni per inizializzare la struttura dati
• Operazioni per modificarla (quelle che
servono…in base all’uso nell’interprete) nello stile
degli esempi che abbiamo visto a lezione
• Non Modificabile (consiglio)
Attenzione
• I tipi di dato astratti hanno delle proprieta’
• Le operazioni le devono garantire
• Come abbiamo visto e’ sempre
consigliabile usare le eccezioni per
trattare i casi non previsti
Frame
• Vogliamo che sia una funzione
• Operazione per creare un frame vuoto
(ovunque indefinto)
• Operazioni per inserire un nuovo legame, per
cercare il valore associato ad un identificatore
(altro?)
• Eccezioni per casi non previsti: per esempio,
inserisco un identificatore che e’ gia’ dichiarato
Memoria
• Vogliamo che sia una funzione, e che le
locazioni siano assegnate in modo incrementale
• Operazione per creare un memoria vuota
(ovunque indefinita)
• Operazioni per inserire un nuovo legame, per
cercare il valore associato ad un locazione, per
modificare il valore memorizzato in una
locazione, per scegliere una nuova locazione
(altro?)
• Eccezioni per casi non previsti: ce ne sono un
tot
Env
•
•
•
•
Vogliamo che sia una Pila di Frames
Operazione per creare una pila vuota
Operazioni di pop, push, top
Eccezioni per casi non previsti: esempio, faccio
pop su una pila che e’ vuota
Implementazione
• Per ciascuna componente dare una implementazione
dell’interfaccia
• Si puo’ anche usare l’implementazione vista nell’interprete
Pico
• Frame puo’ essere realizzato una lista di coppie
(identificatore, valore)
• Env puo’ essere realizzato una lista
• Store puo’ essere realizzato una lista di coppie
(locazione, valore)
• Liste adatte per TDA non modificabili
Parte II: Cosa Cambia?
• L’implementazione dello stato e’ invisibile al codice
dell’interprete
• Alle funzioni di valutazione semantica
•
•
•
•
valProg: prog * sigma * mu-> sigma * mu
valCom: com * sigma * mu-> sigma * mu
valDecl: com * sigma * mu-> sigma * mu
valExp: aExp * sigma * mu-> value*
sigma * mu
Esempio: valCom
let valCom c (sigma,mu) = match c with
| Block l ->
let (Stack (f::rl),mu1) =
valStmtL l
((match sigma with Stack fl ->
Stack (Frame[]::fl)) ,mu) in (Stack rl, mu1)
• La semantica del blocco va modificata, il codice non vede
l’implementazione dell’env e del frame tramite lista tramite lista
• Le strutture dello stato andranno manipolate solo tramite le
operazioni pubbliche fornite dalla relativa interfaccia
Vantaggio
• Non solo l’interprete diventa piu’ astratto, non
dipendente dall’implementazione delle strutture dati
• Il codice delle funzioni di valutazione semantica
risultera’ piu’ semplice, piu’ vicino alla semantica data
in forma SOS
Informazioni Pratiche
• Lo svolgimento dei due progetti puo’
rimpiazzare l’esame scritto
• Il progetto si puo’ fare in gruppi di al
massimo due persone (va consegnato
insieme, indicando i nomi)
• L’esame orale puo’ essere sostenuto
indipendentemente (in date da concordare,
non sono fissate)
Documentazione
• Per facilitare la correzione mandare
insieme ai files con il codice, una breve
relazione
• La relazione dovrebbe spiegare
brevemente le principali scelte adottate
nel programma
Quando vanno consegnati?
• Entro l’inizio delle lezioni del secondo
semestre
• Per qualsiasi informazione, problemi e/o per
fissare un ricevimento a Spezia
[email protected]