Linguaggi II (Programmazione Funzionale), 4 Marzo 2004
RECUPERO ESONERO I

Non e' ammesso l'uso di alcun testo, appunti o calcolatrici. Le risposte ai quesiti vanno scritte nel foglio di bella copia.
Si raccomanda SINTETICITA' negli esercizi che richiedano una spiegazione.
N.B.:
  • Il tempo a disposizione per svolgere il recupero di un esonero e' 40 min.
  • Se si intende svolgere un esonero gia' sostenuto con successo la cosa va comunicata al docente in aula entro 10 min. dall'inizio, questo comportera' l'annullamento automatico del voto gia' preso per l'esonero in questione.

    (a) Ridenominare il minor numero possibile di variabili legate nel seguente termine, in modo che non ci siano due lambda che leghino variabili con lo stesso nome.

    (\xxx.(z\z.x))(x\y.(y(\y.z)yy))


    (b) Enunciare il teorema di Church-Rosser.
    Cos'e' la proprieta' del diamante per una relazione?
    Di quale relazione viene utilizzata la proprieta' del diamante nel teorema di Confluenza?
    Fornire un esempio che mostri che per la relazione di beta-riduzione ad un passo non vale la proprieta' del diamante.


    (c) Sia S in insieme finito di numeri naturali. Consideriamo ora i seguenti insiemi di lambda-termini:
    { M | esiste n in S tale che M = cn}
    { M | esiste n in S tale che M - >> cn}
    { M | esiste n in S tale che M = cn e M e' in forma normale}
    { M | esiste n in S tale che M << - cn}
    dove cn e' il numerale di Church per il numero n e "=" indica la beta convertibilita'.
    Per ognuno di questi insiemi dire se e' ricorsivo o meno, motivando formalmente la risposta.


    Linguaggi II (Programmazione Funzionale), 4 Marzo 2004
    RECUPERO ESONERO II

    Non e' ammesso l'uso di alcun testo, appunti o calcolatrici. Le risposte ai quesiti vanno scritte nel foglio di bella copia.
    Si raccomanda SINTETICITA' negli esercizi che richiedano una spiegazione.
    N.B.:
  • Il tempo a disposizione per svolgere il recupero di un esonero e' 40 min.
  • Se si intende svolgere un esonero gia' sostenuto con successo la cosa va comunicata al docente in aula entro 10 min. dall'inizio, questo comportera' l'annullamento automatico del voto gia' preso per l'esonero in questione.
    (a)
    Definire in Scheme i tipi di dato
  • Albero Ternario con Etichette Funzionali (le etichette ai nodi di un albero di questo tipo sono funzioni da interi a interi)
  • Albero Ternario con Etichette Numeriche.
    NB:E' sufficiente semplicemente indicare i costruttori, i selettori e i predicati del tipo di dato. Non e' necessario implementarli.

    Definire poi in SCHEME una funzione "revFtree" che prenda in input un albero del primo tipo sopra definito ed un intero e restituisca in output un albero del secondo tipo. L'albero in output avra' come struttura quella dell'albero in input "ribaltato" (ruotato di 180 gradi sul suo asse centrale) e come etichette l'applicazione delle etichette al numero dato in input .
    Esempio: 
           f                               f(n) 
     / |                               |   \
   f'  g           n     ---->        g(n)  f'(n) 
  / \  | \                          /  |    /   \ 
 g  h'  h  f                     f(n) h(n) h'(n) g(n)
    Dare uno schema di dimostrazione formale che la funzione Scheme definita si comporta come specificato.


    (b) Si definisca in SCHEME una funzione both che, preso un predicato unario P, restituisca un predicato binario che e' vero se e solo se su entrambi i suoi argomenti vale P.
  • Definire in SCHEME la funzione compose che, prese due funzioni ne restituisce la loro composizione.
  • Definire in SCHEME la funzione neither che, preso un predicato unario P, restituisca un predicato binario che e' vero se e solo se su entrambi i suoi argomenti P non vale. Tale funzione deve essere definita utilizzando both e compose.


    (c) Definire in Haskell i tipi di dato descritti all'inizio dell'esercizio (a).


    Linguaggi II (Programmazione Funzionale), 4 Marzo 2004
    RECUPERO ESONERO III

    Non e' ammesso l'uso di alcun testo, appunti o calcolatrici. Le risposte ai quesiti vanno scritte nel foglio di bella copia.
    Si raccomanda SINTETICITA' negli esercizi che richiedano una spiegazione.
    N.B.:
  • Il tempo a disposizione per svolgere il recupero di un esonero e' 40 min.
  • Se si intende svolgere un esonero gia' sostenuto con successo la cosa va comunicata al docente in aula entro 10 min. dall'inizio, questo comportera' l'annullamento automatico del voto gia' preso per l'esonero in questione.
    (a)
    Dire qual e' il valore di (f 1) nella seguente sessione scheme e giustificarlo mostrando l'evoluzione dei frame durante la valutazione di (f 1). 
    (define a 3)
(define (f y)
     (let ( (a (+ a 1) )
            (b (+ a 1) ) )
       (+ y (+ a b))))
(f 1)

    (b) Scrivere una regola per la Semantica Operazionale Strutturata dello SCHEME per la valutazione di un nuovo tipo di espressione 
    (cacettu e1 e2)
    la cui semantica informale e' la seguente: si valuta e1 poi, di seguito, e2. Il valore di una cacettu-espressione e' sempre il valore dell'espressione e1. Le eventuali modifiche all'ambiente causate dalla valutazione di e1 ed e2 vanno pero' tenute in considerazione.

    (c) Fornire una o piu' espressioni define e un'espressione exp tale che valgano entrambe le seguenti condizioni:
  • il valore di exp e' 1 se valutiamo exp con un normale interprete di Scheme.
  • il valore di exp sarebbe 6 se lo Scheme avesse scoping dinamico.