Laurea Specialistica: Programmazione Funzionale
e
Vecchio Ordinamento: Linguaggi di Programmazione II
(modulo progr. funzionale)
26 Dicembre 2005
Niente appunti o calcolatrici.
Massima SINTETICITA' nelle risposte.
Esercizio 1
(a)
Spiegare perche' talvolta, prima di eseguire una beta-riduzione,
occorra rinominare le variabili legate (della lambda astrazione).
In tali casi, si riuscirebbero ad evitare problemi se si operasse invece
sulle variabili dell'argomento della beta riduzione? Motivare.
(b)
Fornire la coppia principale (Principal Pair) nel sistema di tipi a' la Curry
per il lambda termine y(\x.x) . Motivare la risposta.
(c)
Nel lambda-calcolo tipato a' la Church ogni termine e' fortemente normalizzabile.
Come e' possibile allora in PCF definire funzioni ricorsive che non terminano?
Esercizio 2
(a)
Definire una funzione Scheme numEmpties che prenda in input una lista (che puo' contenere elementi di qualsiasi genere, anche altre liste a qualsiasi livello di annidamento) e che restituisca il numero di liste vuote in essa presenti (a qualsiasi livello di annidamento).
Esempio:
(define test (list (list 2 3 (list '() 3 (list 2 3)) '() ) '() (list 2 3 (list '()))))
(numEmpties test) ----> 4 .
Ricordate che esiste una funzione primitiva list? che restituisce #t sse l'argomento della funzione e' una lista.
Dimostrare formalmente che la funzione definita soddisfa la sua specifica.
(b)
Supponiamo di aver definito il tipo di dato astratto Insieme che ha i
seguenti
Costruttori:
emptyset l'insieme vuoto;
(add-elem element set) restituisce l'insieme set a cui e' stato aggiunto element
Selettori:
(pick set) restituisce un elemento a caso di set;
(residue element set) restituisce set ia cui e' stato tolto element
Predicati:
(emptyset? set) vero se set e' l'insieme vuoto.
Definire una funzione SCHEME Intersection che presi in input due insiemi restituisca
l'insieme intersezione.
Esercizio 3
(a)
Gli Yunz sono esseri magici che nella contea di Hargaar vengono usati dagli studenti per passare
gli esami.
Uno Yunz puo' venire generato dicendo due numeri qualsiasi mentre si effettua l'incantesimo del mago Frunz su due Yunz. Il nanetto Yor e' uno Yunz.
Definire il tipo di dato Yunz in Haskell.
(b)
Considerare la seguente sessione SCHEME:
(define (f y) (+ y 1))
(f ??)
Dire cosa si puo' inserire al posto di "??" affinche' alla fine della valutazione di (f ??) (e prima che i frame non piu' utili vengano eventualmente eliminati) la situazione dei frame sia la seguente ed il valore di (f ??) risulti 4:
| f --> <..., ........> |
---------------------------------------
^ ^ ^ ^
n1 | | | |___________
------------------------------- | | |
| g --> < n1, (lambda (x)...)>| | ----------- |
------------------------------- | | y --> 2 | |
----------- ----------- |
| x --> 3 | -----------
----------- | y --> 3 |
-----------
Ridisegnare anche la figura sopra riempiendo i puntini.