Programmazione Funzionale
5 Luglio 2006


Esercizio 1
(a)
  • Fornire un lambda termine che sia normalizzabile, ma non fortemente normalizzabile.
  • Fornire dei lambda termini M1 e M2 tali che M1 si puo' ridurre in piu' passi a M2, ma non si puo' ridurre ad M2 con un passo di beta riduzione parellela (=>).

    (b) Supponendo di avere gia' definito nel lambda calcolo le funzioni succ (successore) e mult (moltiplicazione), definire la funzione sqr (quadrato).
    Supponendo poi di avere anche definito la funzione cons, il numerale di Church zero e l'operatore di punto fisso Y, definire i lambda-termini corrispondenti
  • alla lista infinita formata da tutte x,
  • alla lista infinita formata dai quadrati di tutti i naturali.
    possibile aiutino: definire, tramite Y, la funzione che, preso un naturale n restituisca la lista infinita dei quadrati dei naturali da n in poi.
    Mostrare qualche passo di riduzione dei termini cosi' definiti.
    Esercizio 2
    Si supponga di avere il tipo di dato astratto albero binario etichettato, in cui le etichette siano funzioni da naturali a naturali.
    (a) Definire una funzione SCHEME "parapaponzi" che prenda in input due alberi binari e restituisca l'albero binario la cui struttura sia l'intersezione delle due strutture, e in cui le etichette dei nodi siano la composizione delle etichette dei nodi corrispondenti negli alberi in input.
    Esempio: 
            f                 w                         j
      /   \             /   \                     /   \ 
     h     g           z     r       ----->      l     u 
      \   / \         /     /                         /
      s  t   v       i     k                         q
    dove j e' la composizione delle funzione f e w, l e' la composizione delle funzioni h e z, u quella delle funzioni g ed r, q la composizione di t e k.

    (b) Definire una funzione SCHEME "ponzipo" che prenda in input una funzione f da naturali in naturali e restituisca un albero binario completo (con funzioni da naturali a naturali come etichette) tale che l'etichetta della radice sia f, le etichette dei nodi a profondita' 1 siano funzioni uguali ad f tranne che su n valgono f(n)-1, quelle al secondo livello, lo stesso, solo che su n valgono f(n)-2 e cosi' via.
    Ovviamente se f(n)=0 allora ponzipo restituisce un albero formato da un solo nodo, con etichetta f.
    Esempio: 
                                                     succ
                                               /      \
      (ponzipo succ 1)    ---->            succ'       succ'
                                          /  \         / \
                                       succ" succ" succ" succ"
    dove succ e' la funzione successore, succ' e' la funzione uguale a succ tranne che succ'(1)=1, mentre succ" e' come succ tranne che succ"(1)=0.

    Dimostrare che ponzipo e' totale.
    Esercizio 3
    (a) Considerare il costrutto double-let con la seguente sintassi 
    (double-let (  ((var1 exp1)
                    :
                (varn expn))   )

               ((var'1 exp'1) 
                    :
                (var'm exp'm)) ) )
       expa; expb)
    Il valore di un'espressione double-let valutata in un frame rho, si ottiene nel seguente modo: si estende rho con un frame rho' contenente le associazioni vari -> vi (i=1,..,n), dove vi e' il valore di expi valutato in rho. Poi si estende sempre rho con un frame rho" contenente le associazioni var'j -> v'j (j=1,..,m), dove v'j e' il valore di exp'j valutato in rho'. Quindi si valuta expa in rho' e expb in rho". Il valore finale dell'intera espressione double-let e' il valore di expb.
    Fornire la semantica dell'espressione double-let con una o piu' regole della semantica operazionale strutturata.

    (b) Fare una bella domanda intelligente la cui risposta sia "chiusure".