Linguaggi di Programmazione II (programmazione funzionale)
4 Marzo 2004

Niente appunti o calcolatrici. Massima SINTETICITA' nelle risposte.
Esercizio 1
(a) Considerate i due seguenti termini: \nfx.f(nf(fx)) e \nfx.f(nf(fx))
Se applicati a numerali di Church calcolano la stessa funzione sui naturali?
  • Se si, quale? Dimostrarlo formalmente. Sono termini beta-convertibili? Perche', intuitivamente, pur calcolando la stessa funzione non e' da ritenersi "sconveniente" che non siano beta-convertibili?
  • Se no, quali funzioni distinte calcolano? Dimostrarlo formalmente. Sono termini beta-convertibili? Perche', intuitivamente, pur calcolando funzioni distinte non e' da ritenersi "sconveniente" che siano beta-convertibili?


    (b) Sia => la relazione di beta-riduzione parallela e I il lambda termine \x.x
    Quali delle seguenti relazioni sono vere? Perche'? (b) Sia N un \-termine che non contiene x. Allora vale sempre 
    	(\x.Mx)N = (Mx)[N/x]  =  MN
    Leggendo il primo e l' ultimo membro dell' uguaglianza otteniamo
    (\x.Mx)N=MN ovvero \x.Mx=M
    E' uno schema di ragionamento corretto? Se si, dettagliarlo e completarlo. Se no, perche'?
    Esercizio 2
    (a) Definire una funzione che prenda in input una lista ls di numeri e tre numeri n1, n2 e n3 tali che n1 < n2 < n3.
    La funzione dovra' restituire una lista di due liste tali che gli elementi della prima sono tutti gli elementi di ls strettamente minori di n1 e gli elementi della seconda sono tutti gli elementi di ls compresi tra n2 e n3.
    Possibilmente definire la funzione non utilizzando funzioni ausiliarie.
    (b) Si consideri la seguente funzione Scheme che prende come input coppie di numeri naturali. 
    	(define (Matrix n m)
	     (cond ((= m 0) m)
	           ((= n 0) n) 
		   (else (+ 1 (Matrix (- n 1) (Matrix n (- m 1)))))))
    Dimostrare formalmente che la funzione Matrix e' totale.
    Facoltativo: cosa calcola Matrix?.
    Esercizio 3
    (a) Mostrare l'ambiente al termine della valutazione della espressione Scheme 
    		 ( ((lambda (x) x) +) (pippo y) (let ((y y)) 3) )
    supponendo di valutarla nel seguente ambiente avendo p1 come puntatore di frame corrente. Dire anche qual e' il valore restituito dall'interprete. 
                       ^
                   | pTop
          -----------------------------------------
          |  y --> 5                              | 
	  | pippo --> < (lambda (x) (+ y x)), p1> |
          -----------------------------------------
                 ^
                 | p2
                 |
           --------------
           |  y --> 64  | <---- p1
           |  z --> 3   |
           --------------


    (b) La sonda Spirit ha trovato che su Marte esistono i Loffioni.
    Un Loffione puo' essere un Gangarone oppure un Sarrapone, oppure una sequenza finita di Purpuroni. Un Purpurone e' formato da un Gangarone e un Sarrapone. In natura il numero di gangaroni e' infinito, invece esistono solo due Gangaroni, il GangaroneA e il GangaroneB.
    Definire in Haskell il tipo di dato astratto Loffione che possa permettere di scrivere programmi Haskell che simulino esperimenti virtuali sui Loffioni.