Linguaggi di Programmazione (16 Settembre 2010)
Esercizio 1
(a)
Definire il lambda-calcolo tipato a' la Church e l'algoritmo di
Type Checking.
(b)
Definire in Haskell il tipo di dato Lambda-Termine
e realizzare le funzioni fv e bv che calcolano gli insiemi
delle variabili, rispettivamente, libere e legate di un termine.
Per realizzare fv e bv si utilizzi il dato
data Set a = Set [a]
e si supponga di avere a disposizione gli operatori insiemistici "union" e "minus".
Esercizio 2
(a)
In FJ e' possibile dimostrare il seguente
Theorem [Progress]
Suppose e is a well-typed expression.
(1) If e includes new C0(e1,..,en).f as a subexpression, then fields(C0)=T1f1,..,Tnfn and f is in {f1,..,fn}.
(2) If e includes C0(e1,..,en).m(d1,..,dk) as a subexpression, then mbody(m,C0)=(x1,..,xj, e0) and k=j.
In sintesi, cosa ci dice questo teorema?
(b)
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 e <== equals(other);
...
}
...
}
A quali problemi si andrebbe incontro?
Esercizio 3 Vedi retro.
Esercizio 3
(a)
Esiste un grado di parentela tra due persone se queste
sono discendenti di una stessa persona.
Il grado di parentela di due persone e' la somma delle distanze
(nell'albero genealogico)
tra le due persone e la prima di cui sono entrambe discendenti.
Scrivere un programma Prolog che calcoli, se esiste, il grado di parentela
di due persone (supponendo di avere una base di dati di fatti del tipo
"parent(tizio,caio)." che indicano che tizio e' figlio di caio).
(b)
Cosa si intende per Linguaggi di programmazione con "named state"
e con "unnamed state"?
Possono esserci linguaggi concorrenti in entrambe categorie?