Programmazione Funzionale, 2 Ottobre 2008

  • Niente appunti o calcolatrici. Massima SINTETICITA' nelle risposte.
  • Per quelli della specialistica: i voti (quelli positivi) verranno registrati non appena corretto il compito. Chi non intendesse accettare un voto ritenuto basso o desiderasse fare l'orale (opzione possibile solo se il voto fosse maggiore di 24), deve comunicarlo per tempo al docente, indicandolo anche sull'elaborato.

    • Esercizio 1
    (a) Enunciare i teoremi di Confluenza e di Church-Rosser. Dimostrare che sono equivalenti. Discutere del loro significato per la programmazione funzionale.
    (b) Definire la nozione di strategia di riduzione. Il termine H = \g.((\f.ff) (\f.(g\x.ffx))) e' un punto fisso? Perche'? Perche' conviene utilizzarlo per definire punti fissi nel lambda-calcolo con strategie tipo quella di Scheme?
    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) 
    (define (YY? x y)
  (cond ((= x y) #t)
        ((< x y) #f)
        ((> x y) (YY? (- x y) y))))
    Dimostrare che il predicato YY? definito sopra e' totale. Dire per quali valori vale YY?
    Riscrivere YY? utilizzando solo operatori booleani (senza utilizzare cond quindi).
    Esercizio 3
    (a) Descrivere brevemente il sistema di tipi di Haskell.
    (b) Supponiate che venga aggiunta allo Scheme la parola chiave "Boink" e che la nostra S.O.S. per lo Scheme contenga la seguente regola di inferenza:
                             Z,n |-- e1 --> <(lambda (x) e), n'>,Z'   
       Z'[Next(Z'),(n,0[pippo,<(lambda (x) e), n>])],  Next(Z')|-- e2 --> v,Z"
    -----------------------------------------------------------------------------------------------------------
                                  Z,n |-- (Boink e1 e2) --> v, Z"
    Descrivere a parole cosa fa l'interprete per valutare una Boink-espressione
    Descrivere lo stato dei frame alla fine dalla valutazione della seguente sessione Scheme e dire qual e' il valore restituito. 
    	(define x 34)
	(Boink ( (lambda (x) x) (lambda (y) y))  (pippo x) )