Linguaggi di Programmazione II (programmazione funzionale)
30 Settembre 2004

Niente appunti o calcolatrici. Massima SINTETICITA' nelle risposte.
Esercizio 1
(a) Fornire la definizione di alfa-conversione. Qual e' il motivo per introdurre tale nozione nel lambda-calcolo?

(b) Qual e' la forma normale del seguente termine?
((\w.(xw))(\y.(yx)))[\x.(w(xy))/x]
Qual e' l'insieme delle sue variabili libere? e quale quello delle sue variabili legate?

(c) Fornire una derivazione nel sistema di tipi a' la Curry per il termine
\b.((\y.c)(bc))
Esercizio 2
(a) Si consideri la funzione
f (0,m) = m
f (n,m) = n * f (n-1,m+1)
Dimostrare per induzione ben fondata che f (n,m) = (n+m) * n!

(b) Si supponga di aver definito in Scheme i costruttori, predicati e selettori per il tipo di dato Albero Binario etichettato con predicati su numeri: Emptytree, MKtree, Emptytree?, LabelRoot, Rightchild, Leftchild.
Definire una funzione Scheme patapunfete che preso un albero di questo tipo, un numero n ed un valore booleano b, restituisca una lista che contenga tutti i predicati presenti nell'albero tali che il loro valore su n sia b.
Esercizio 3
(a) Presa la seguente definizione di tipo in HASKELL 
	data Pirimpo = Pompero Int | Zumpo Pirimpo [Int]
scrivere delle definizioni Scheme che permettano di utilizzare (per qual che e' possibile in Scheme) il tipo di dato Pirimpo.

(b) Considerare la seguente sessione SCHEME: 
(define f 
    (lambda (g) 
        ( (g (lambda (x) x) ) (+ 1 1))))

(define g 1)

(f (lambda (x) x))
Mostrare la situazione dei frame alla fine della valutazione di (f (lambda (x) x)) e prima che i frame non piu' necessari vengano eventualmente eliminati.
Qual e' il valore di (f (lambda (x) x)) ?