Linguaggi di Programmazione (13 Dicembre 2014)

Esercizio 1 Supponiamo di voler estendere il lambda-calcolo tipato a' la Curry LC⁺ anche con termini che rappresentino liste (in modo esplicito, non tramite una codifica).
Fornire i tipi, gli assiomi e le regole di inferenza da aggiungere al type system.

Esercizio 2 La sonda Spirit ha trovato che su Marte esistono i Loffioni.
Un Loffione puo' essere generato da un Gangarone oppure da un Sarrapone, oppure da una sequenza finita di Purpuroni. Un Purpurone viene generato dall'incontro di un Gangarone e un Sarrapone. Su Marte ci sono infiniti sarraponi, ma solo due Gangaroni, il GangaroneA e il GangaroneB.
Definire in Haskell il tipo di dato astratto Loffione che possa permettere di scrivere programmi Haskell che simulino esperimenti virtuali sui Loffioni.
Scrivere il programma Haskell che, preso un Loffione, restituisca quante volte il GangaroneA e' intervenuto nella generazione del Loffione dato.

Esercizio 3 Definire la grammatica dei processi del pi-calcolo e dare formalmente la definizione di insieme dei nomi legati di un processo, bn(P), e dei nomi liberi, fn(P).

Esercizio 4 Supponiamo di avere un sistema composto da un processo server e due processi client. Il processo server riceve in continuazione dei numeri che i vari client inviano, li incrementa di uno e rispedisce indietro il risultato. Il primo client invia il numero 3, mentre il secondo invia 5. Entrambi i client, una volta ricevuto il numero incrementato, lo stampano. Ovviamente il sistema rispetta il vincolo che ogni client deve riceve indietro l'incremento del numero che lui aveva inviato, non del numero inviato dall'altro client.
Implementare in Pict due versioni differenti del sistema, una in cui il rispetto del vincolo avviene attraverso l'uso di canali privati, l'altra in cui la ricezione del risultato avviene attraverso un canale comune ai client ed in cui il rispetto del vincolo avviene attraverso l'implementazione di una mutua esclusione tra i client rispetto all'invio del numero e ricezione del risultato.

Esercizio 5 Si consideri il seguente programma Prolog per calcolare l'altezza di un albero binario etichettato con etichette che sono atomi:

max(N1,N2,N1):- N1>N2.
max(_,N2,N2).


altezza(X,1):- atom(X).

altezza(node(_,Subtree1,Subtree2),N):- altezza(Subtree1,N1),
                                       altezza(Subtree2,N2),
                                       max(N1,N2,M),
                                       N is M+1.

Se ora calcoliamo l'altezza dell'albero node(a,node(a,a,a),node(a,node(a,a,a),a)) attraverso la query

?- altezza(node(a,node(a,a,a),node(a,node(a,a,a),a)),X).

otteniamo non uno, ma ben due valori per l'altezza:

X = 4 ;
X = 3.

Perche'? Modificare il programma in modo che il calcolo dell'altezza restituisca l'unico valore corretto. Se possibile, fornire due differenti possibilita' di modifica.

Esercizio 6
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?