Laurea Specialistica: Programmazione Funzionale
e
Vecchio Ordinamento: Linguaggi di Programmazione II (modulo progr. funzionale)
2 Marzo 2005

Niente appunti o calcolatrici. Massima SINTETICITA' nelle risposte.
Esercizio 1
(a) Eseguire le seguenti sostituzioni: (b) Discutere della nozione di Punto Fisso e del suo uso nel Lambda-calcolo.
Esercizio 2
(a) 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 un predicato SCHEME ForAll che, presi in input un insieme I ed un predicato P?, verifichi se il predicato P? e' soddisfatto per tutti gli elementi di I.

(b) Si consideri l'insieme (N->N)xNxN, dove N e' l'insieme dei naturali e N->N quello delle funzioni totali da N in N. Su tale insieme si consideri la seguente relazione:
(g,n,m) << (g',n',m') sse (n = n' e g(n) < g(n')) oppure (n = n', g=g' e m < m')
Si dimostri che ((N->N)xN,<<) e' un insieme ben-fondato. Si fornisca una qualsiasi funzione SCHEME la cui totalita' sia dimostrabile utilizzando l'induzione ben-fondata su ((N->N)xNxN,<<).
Esercizio 3
(a) Mostrare l'ambiente al termine della valutazione della espressione Scheme 













( (lambda (y) (+ y 3)) (+ x y) )
supponendo di valutarla nel seguente ambiente avendo p1 come puntatore di frame corrente. 
             ^ pTop
             | 
    ------------------
    |  y --> 5       | 
    | pippo --> true |
    ------------------
         ^
         | p2
    --------------
    |  x --> 64  | <---- p1
    |  y --> 3   |
    --------------

(b) Dire brevemente cosa fa' l'interprete HASKELL quando scriviamo qualcosa del genere: 
	funct :: [Int] -> Bool
	
	funct ls = BODY