ESERCIZIO ML 1. - definire due tipi ML Var e Term corrispondenti all'insieme delle variabili ed a quello dei lambda termini M ::= x | M1 M2 | l x.M - si definiscano due funzioni di valutazione CBN, CBV : Env -> Term -> Term corrispondenti alla semantica operazione CBV e CBN si considerino due possibili definizioni del tipo degli ambienti Env Env = Var -> Term e Env = (Var * Term) list ESERCIZIO ML 2. - definire i tipi Tvar e Type corrispondenti all'insieme delle variabili di tipo ed a quello dei tipi semplici T ::= X | T1 -> T2 - si definisca una funzione corrispondente all'algoritmo W W : (Context * Term) -> (TSubst * Type) dove Context = (Var * Type) list e TSubst = (TVar * Type) list ESERCIZIO ML 3. - si definisca una azione relazionale associata al tipo lista Rmap : (X,Y) rel -> (X list,Y list) rel dove type (X,Y) rel = (X*Y) -> bool e' l'insieme delle relazioni, e scriviamo x R y invece di R (x,y) Rmap deve essere tale che [x_{i:m}] (Rmap R) [y_{i:n}] sse m=n e x_i R y_i per ogni i:m ESERCIZIO ML 4. Si consideri i tipi di dato list e btree (alberi binari). - definire la relazione Rtranspose : (X btree list, X list btree) Rel (dove X varia sugli equality types) t.c. [t_{i:m}] Rtranspose t sse gli alberi t_i hanno la stessa struttura dell'albero t e ogni foglia di t, diciamo quella in "posizione" p, e' costituita dalla lista [x_{i:m}] dove x_i e' la foglia in posizione p dell'albero t_i. - definire la funzione parziale transpose : (X btree list) -> X list btree t.c. transpose [t_{i:m}] = t sse t e' l'unico albero di liste per cui vale [t_{i:m}] Rtranspose t (in tutti gli altri casi transpose [t_{i:m}] deve sollevare una eccezione). =============================================================================== ESERCIZIO OO 1. si definisca (in Java o Java-like) un classe astratta collection i cui oggetti rappresentano collezioni di oggetti di una certa classe T. I metodi della classe astratta collection sono: bool empty? (); T get (); insert (T x); Si implementino le seguenti sottoclassi di collection: - queue, con costruttore queue() che crea una coda vuota - union, con costruttore union(collection X,Y) che corrisponde alla unione di X "seguita" da Y - bigcollection, con costruttore bigcollection() che crea una coda vuota, e con il metodo aggiuntivo biginsert(collection X) per inserire in coda gli elementi della collezione X ESERCIZIO OO 2. Si modifichi l'esercizio precedente supponendo che collection sia una interfaccia invece che una classe astratta. Si modifichi l'esercizio precedente supponendo che collection sia una classe astratta che abbia anche un metodo collection clone() che restituisce una copia della collezione. Rivedere l'implementazione dei metodi union e biginsert onde evitare sharing di collezioni mediante l'uso di clone. ESERCIZIO OO 3. Si definisca la classe queue come una sottoclasse di stack usando un linguaggio Java-like. Traccia: class list { public int elem; public list next; } class stack { MODIFIER list top; public stack() - inizializzazione stack public bool empty() - controlla se lo stack e' vuoto public int get() - rimuove l'elemento in testa public put(int x) - aggiunge x in testa } class queue extends stack { MODIFIER list bottom; public queue () - inizializzazione queue public put(int x) - aggiunge x in coda }