ESERCIZI Object Orientation

ESERCIZI OBJECT ORIENTATION e FJ

Esercizio 1(anni 2010/11 e precedenti)

Per Featherweight Java e' definibile la funzione "Join" (vedi [BV]) utilizzabile per fornire una regola di tipaggio per le espressioni condizionali? Giustificare

In caso affermativo, definire formalmente la funzione Join utilizzando assiomi e regole come fatto per le funzioni mtype e mbody.

Esercizio 2

Cosa si intende per "dynamic dispatch" nel contesto dei linguaggi O.O.?

Featherweight Java utilizza il dynamic dispatch? Giustificare.

Esercizio 3(anni 2010/11 e precedenti)
Completare le dimostrazioni in [BV].

Esercizio 4
Fornire gli assiomi e le regole di inferenza che descrivano la nozione di sottotipo cosi' come utilizzata da Java, nel caso che quest'ultimo utilizzasse lo structural subtyping.

Esercizio 5
Nella programmazione O.O. possono esserci casi in cui l'invocazione di un metodo puo' provocare la necessita' di scegliere tra piu' possibili codici da eseguire. Questo puo' avvenire sia in presenza di metodi overloaded che di metodi overridden.
Che differenza c'e' tra metodi overloaded e metodi overridden?
Cosa si intende per "static" e "dynamic" method resolution?
Il seguente e' un esempio del testo contenente un metodo che e' sia overloaded che overridden e dove

SCType <: CType

class C {
     ...
     function equals(other:CType): Boolean is
         { ... }      // equals 1
	}

class SC inherits C modifies equals {
     ...
     function equals(other:CType): Boolean is
         { ... }      // equals 1
     function equals(other:SCType): Boolean is
         { ... }      // equals 2
}

In presenza di static resolution per i metodi overloaded e dynamic per quelli overridden, quale codice viene eseguito nelle seguenti invocazioni di metodo, supponendo che c e c' sono stati dichiarati di tipo C ed sc di tipo SC?
Giustificare le risposte. Risposte senza giustificazione non verranno valutate.

c := new C;
sc := new SC;
c' := new SC;

c  <= equals(c);
c  <= equals(c');
c  <= equals(sc);

c'  <= equals(c);
c'  <= equals(c');
c'  <= equals(sc);

sc  <= equals(c);
sc  <= equals(c');
sc  <= equals(sc);

Soluzione

Esercizio 6
In FJ e' possibile dimostrare il seguente

Theorem [Progress] Suppose e is a well-typed expression.
(1) If e includes new C₀(e₁,..,e_n).f as a subexpression, then fields(C₀)=T₁f₁,..,T_nf_n and f is in {f₁,..,f_n}.
(2) If e includes C₀(e₁,..,e_n).m(d₁,..,d_k) as a subexpression, then mbody(m,C₀)=(x₁,..,x_j, e₀) and k=j.

In sintesi, cosa ci dice questo teorema?

Esercizio 7
Alcuni linguaggi di programmazione O.O. hanno sistemi di tipo che sono invariant.
Cosa significa?
Questi linguaggi hanno problemi con i metodi binari, in particolare quando si definiscono delle sottoclassi.
Supponiamo che quella seguente sia una definizione di classe in uno di tali linguaggi (dove CType e' il tipo degli oggetti della classe C).

class C {
   ...
   function equals(other:CType): Boolean is
   { ... }
   ...
}

Se si definisse ora la seguente sottoclasse

class SC inherits C modifies equals {
   ...
   function equals(other:CType): Boolean is
   { super <== equals(other);
   ... 
   }
   ...
}

a quali problemi si andrebbe incontro?

Esercizio 8
Supponiamo di avere le seguenti definizioni in FJ:

class A extends Object {
A() { super(); }
}

class B extends Object {
B() { super();  }
}

La seguente espressione FJ e' correttamente tipabile?

(A)(Object)new B()

Perche?
Perche' si e' introdotta in FJ la seguente regola di tipo?

Gamma |- e : D    C non sottotipo di D    D non sottotipo di C

		  stupid warning
----------------------------------------------------------------------
		Gamma |- (C)e : C

Esercizio 9
Dire, giustificando la risposta, se l'approccio del sistema di tipi di FJ, e quindi di Java, e' a' la Curry o a' la Church.

Esercizio 10
Descrivere l'algoritmo di type-checking per il lambda calcolo tipato a' la Church utilizzando assiomi e regole di inferenza, nello stile di quanto di fa per FJ.

Esercizio 11
Definire formalmente quello che K.Bruce intende per Invariant Type Systems per linguaggi O.O. Quali i vantaggi di avere type system che sono invariant? Quali gli svantaggi? Fornire qualche esempio esplicativo.

Esercizio 13(anni 2010/11 e precedenti)
Descrivere l'F-bounded polimorphism cosi' come utilizzato in Java. Uso, vantaggi e svantaggi.

Esercizio 14
Cosa si intende per nominal e structural subtyping?
Qual e' l'approccio di Java? e quello di Ocaml?
Quali i vantaggi e svantaggi dei due approcci?

Esercizio 15
(a) Il cast in Java quali problemi crea? Quali garanzie ci forniscono a riguardo i teoremi di FJ i cui enunciati sono stati studiati nel corso?

(b) Il sistema di tipi di Java e' invariante, covariante o controvariante rispetto ai tipi degli argomenti e del risultato dei metodi overridden nelle sottoclassi? Quali problemi comporta tale invarianza/covarianza/controvarianza? Quali vantaggi? Si potrebbe definire il type system di Java diversamente per migliorarlo?

Esercizio 16
In Ocaml la definizione di una classe ha la forma

class name =
    object (self:'self)
    ....
    ....
    end;;

Qual e' il significato di "self" e di "'self"?
Quale vantaggio fornisce l'uso di "'self" relativamente ai metodi binari?

Esercizio 17
Il seguente segmento di codice e' parte di una definizione di classe in Ocaml:

class colorPoint =
    object (self:'self)
      inherit point as super
               :
               :

Descrivere l'uso del costrutto (self:'self) e come si riflette nel tipo delle classi.
Descrivere le problematiche presenti in Java che l'uso di tale costrutto impedisce che siano presenti in Ocaml.

Esercizio 18
Descrivere cosa si intende per subtyping nominale e subtyping strutturale. Descriverne vantaggi e svantaggi. Che specie di subtyping ha Java? e Ocaml? Fornire un esempio per entrambi il linguaggi.

Esercizio 19
Dire se ed eventualmente in quali casi in OCaml una sottoclasse definisce anche un sottotipo.

Esercizio 20
Definire una classe in OCaml i cui oggetti abbiano il tipo seguente
< pippo : int; pluto : int; paperino : int → int → unit; paperina : 'a → bool > as `a

Soluzione

Esercizio 21
Inserire le premesse (dandone giustificazione) della seguente regola (T-invk) utilizzata dal type system di FJ per tipare l'invocazione di metodo.

???
------------------------------------
Γ |- e₀.m(e) ∈ C

In cosa si discosta il type system di FJ rispetto a quello di Java (tenuto conto ovviamente che FJ e' un frammento di Java)?

Esercizio 22
Definire i concetti di covarianza e controvarianza di una relazione rispetto ad un operatore e giustificare informalmente la controvarianza della relazione di sottotipo per il costruttore di tipo Ref. Giustificare quindi perche' non e' possibile modificare il tipo delle instance variables in una sottoclasse.

Esercizio 23
Quello che segue e' uno schema di codice Ocaml-like in cui un metodo m viene "overridden" nella sottoclasse, modificando da S ad S' il tipo del suo argomento.

class aClass2 =
   object 
       ...
   method m(s:S) = ...    
       ...
   end


class aSubclass2 =
   object 
   inherits aClass2 as super 
   ...
   method m(s:S.) = ...    
   ...
   end

Aggiungere del codice allo schema, una volta per mostrare che S' deve necessariamente essere un sottotipo di S; ed una seconda volta per mostrare che S deve essere un sottotipo di S'. A quale conseguenza portano i due esempi?

Esercizio 24
Quale problema viene introdotto in Java dall'uso del downcast? Perche' allora viene utilizzato?
Perche' il type system di Java per FJ viene esteso con la regola (T-SCast) (stupid cast)?

Esercizio 25
Cosa si intende per Subtyping Polymorphism?
Le due seguenti funzioni OCaml hanno lo stesso body, ma comportamenti differenti. Perche?

let bumpd1 (p:< get_x : int; get_y : int; setcoord : int -> int -> unit >)     
             = p#setcoord (p#get_x +1) (p#get_y +1);;

let bumpd2 p = p#setcoord (p#get_x +1) (p#get_y +1);;

Definire un elemento myPoint tale che bump2 myPoint risulti un'applicazione corretta, mentre bump1 myPoint no.
C'e' un modo per poter applicare correttamente la funzione bump1 all'argomento myPoint? Giustificare.

Esercizio 26
Perche' il downcast in Java e' pericoloso? E perche', nonostante cio', e' stato inserito nel linguaggio?

Esercizio 27
Perche' non e' possibile avere overridden methods con un numero differente di argomenti anche ammettendo la possibilita' di modificare il tipo degli input types e dei return types?

Soluzione