Programmazione Funzionale
18 Giugno 2007


Esercizio 1
(a) Qual e' il risultato delle seguenti sostituzioni? Quali sono gli insiemi delle variabili legate e libere dei termini ottenuti? L'insieme delle variabili libere e quello delle legate di un termine sono invarianti per alfa-conversione?

(b) Dare la definizione di funzione lambda-definibile.
Scrivere esplicitamente il lambda-termine che rappresenta la funzione massimo tra due numeri naturali. Si supponga di avere gia' i lambda-termini if, add, iszero, succ, pre e, crepi l'avarizia, Y.
(aiuto: si consideri una versione ricorsiva della funzione massimo).

(c) Sia (-)* la funzione utilizzata nella dimostrazione della proprieta' del diamante della beta-riduzione parallela in 0 o piu' passi (=>).
Si consideri l'insieme { M | (M)* non contiene beta-redessi}.
Tale insieme e' ricorsivo? Perche'?
Esercizio 2
(a) Fornire una funzione SCHEME "zumpappa'" che prende in input un albero binario T, un predicato P1, un predicato P2 ed un numero n. L'albero binario T e' etichettato con etichette che sono funzioni unarie da naturali a naturali. Il predicato P1 e' un predicato su funzioni unarie da naturali a naturali, mentre il predicato P2 e' un predicato su naturali.
La funzione "zumpappa'" restituisce un albero simile a T, ma in cui se una funzione g soddisfa il predicato P1 questa viene sostituita con una funzione che si comporta come g, tranne che per i valori per in cui e' soddisfatto P2, nel qual caso il valore e' n.
Dimostrare che "zumpappa'" e' totale.
(b) E' possibile scrivere un'espressione SCHEME che rappresenti una lista infinita di elementi? Se si, dire brevemente come si puo' fare e se poi e' possibile utilizzare tale espressione per fare delle computazioni.
Se no, dire perche' e cosa andrebbe cambiato dello SCHEME perche' la cosa diventi possibile e se il cambiamento proposto permetterebbe di utilizzare un'espressione del genere per fare delle computazioni.
Esercizio 3
(a)
Considerare la seguente sessione SCHEME: 
(define f 
  (lambda (y) 
            ((lambda (x) x) (g 1))))

(define g ????)

(f 4)
Dire cosa si puo' inserire al posto di "????" affiche' alla fine della valutazione di (f 4) (e prima che i frame non piu' utili vengano eventualmente eliminati) la situazione dei frame sia la seguente: 
   | f --> <.., ....>    |
   | g --> ......        |
   -----------------------
    ^         ^
 n3 |         | n1
 ------       |
|x-->1|   -----------    n2   --------------------
 -----   | y --> 4   | <-----| x --> < n4, ...>  |  
   ^      -----------         --------------------
   | n4
Ridisegnare anche la figura sopra riempiendo i puntini.

(b) Considerare il seguente costrutto lett con la seguente sintassi 
(lett ((b1 var1 exp1 exp'1)
      ..................
       (bn varn expn exp'n))
    exp)
Il valore di un'espressione lett e' il valore di exp valutata nell'ambiente in cui viene valutata l'espressione lett esteso con un frame con le associazioni vari --> vi. Il valore vi e' calcolato valutando l'espressione booleana bi nell'ambiente in cui viene valutata l'espressione lett. Se il valore di bi e' falso si valuta (sempre nell'ambiente di lett) l'espressione expi, altrimenti exp'i.
Fornire la semantica dell'espressione lett o direttamente con delle regole della semantica operazionale strutturata oppure indirettamente in termini di altri costrutti SCHEME (let escluso).