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'?
-
(II)(III) => II
-
I(II) => I
-
IIII => III
-
IIII => I
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 restituisce il minimo tra i due numeri naturali in input.
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.