Programmazione Funzionale, 16 Settembre 2008

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)) ?