Programmazione Funzionale, 6 Febbraio 2006

  • Niente appunti o calcolatrici. Massima SINTETICITA' nelle risposte.
  • Per quelli della specialistica: dopo una settimana dalla pubblicazione dei risultati, i voti (quelli positivi) verranno registrati. Chi non intende accettare il voto o desidera fare l'orale (se il voto e' maggiore di 24), deve comunicarlo per tempo al docente.

    • Esercizio 1
    (a) 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) Eseguire il "principal typing algorithm" sul termine \fx.fx
    Qual'e' invece il tipo principale dell'operatore di punto fisso \f.((\x.f(xx))(\x.f(xx))) ?
    (c) 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).

    Esercizio 2
    (a) Cosa calcola la seguente funzione SCHEME? Giustificare. 
    	(define (X? y?)
	  (lambda (x)
	      (or (null? x)
                  (and (list? x)
                       (y? (car x))
                       ((X? y?) (cdr x))))))

    (b) Definire il tipo di dato astratto "Albero binario con etichette numeriche solo sulle foglie".
    Definire la funzione SCHEME che, preso un albero del tipo descritto restituisca la lista delle etichette delle sue foglie.
    Esercizio 3
    (a) Mostrare graficamente come evolve l'abiente se facciamo valutare all'interprete SCHEME l'espressione
    ( (lambda (x) (x x)) (lambda (x) (x x)) )

    (b) Vogliamo introdurre nello SCHEME un nuovo tipo di espressioni: 
     (paperinika  e1 e2 e3)
    La semantica informale di una paperinika-espressione e' la seguente: Viene valutata l'espressione e1 e poi l'espressione e2. Se i loro valori sono numerici e il valore di e1 e' minore di quello di e2 allora il valore di tutta l'espressione e' il valore di e2. Altrimenti il valore dell'espressione e' il valore di e3.
    Scrivere una o piu' regola nello stile della Semantica Operazionale Strutturata che descrivano formalmente la semantica di una paperinika-espressione.