Programmazione Funzionale 7 Dicembre 2006

Esercizio 1

Fornire la definizione informale della funzione (-)^* da lambda-termini a lambda-termini.
Descrivere in quale punto si utilizza nella dimostrazione del Teorema di Confluenza per il lambda-calcolo.
Qual e' la formal normale del seguente termine? ((\w.(xw))(\y.(yx)))[\x.(w(xy))/x]
Fornire un lambda-termine normalizzabile il cui insieme di variabili libere sia {x, y}, e tale che l'insieme delle variabili libere della sua forma normale sia {x, y, z}

Esercizio 2
Definire in SCHEME il tipo di dato astratto Stack (nella sua versione puramente funzionale).
Definire le seguenti funzioni SCHEME che utilizzano tale tipo di dato:

"perepe", che prenda in input una funzione ed uno Stack e che restituisca uno Stack simile a quello in input, ma in cui a tutti gli elementi e' stata applicata la funzione.
Esempio informale:

                               | 1 |             | 3 |
                               | 7 |             | 9 |
(perepe  (lambda (x) (+ 2 x))  | 3 | )   --->    | 5 |
                               -----             -----

"piripi", che prenda in input uno Stack e restituisca la funzione che prende in input un numero naturale n e restituisce l'elemento contenuto a profondita' n nello Stack a partire dalla cima, o il valore 9 nel caso lo stack sia vuoto o abbia meno di n+1 elementi.

Esercizio 3

Fornire una espressione SCHEME alla fine della valutazione della quale l'ambiente sia il seguente:

       ------------------------------------          ------------
       |                                  |    n1    |          |     n2
       | f --> <(lambda (x) (+ 1 y)), n2> | <------- | y --> 1  | <------ 
       |                                  |          |          | 
       ------------------------------------          -------------

Supponiamo di aggiungere allo SCHEME un nuovo tipo di espressione :
```
          (ifeq  exp0 exp1 exp2 exp3)
```
Il cui valore deve venir valutato dall'interprete nel modo seguente: si valuta l'espressione exp0, poi l'espressione exp1. Se i valori di exp0 ed exp1 coincidono, allora il valore dell'intera espressione e' il valore di exp2, altrimenti quello di exp 3.
Fornire una o piu' regole nello stile della Semantica Operazionale Strutturata che descrivano formalmente il modo in cui l'interprete valuta un'espressione ifeq.