Linguaggi di Programmazione II (programmazione funzionale)
13 Maggio 2005

Niente appunti o calcolatrici. Massima SINTETICITA' nelle risposte.
Esercizio 1
(a) Fornire un lambda termine che sia normalizzabile, ma a partire dal quale esista anche una sequenza infinita di beta-riduzioni.
(b) Scrivere esplicitamente il lambda-termine che rappresenta la funzione prodotto quando questa e' definita ricorsivamente a partire dalla funzione somma : 
	0*y = 0
	x*y = (y + (x-1)*y)     se x diverso da 0
Si supponga di avere gia' i lambda-termini if, add, iszero, pre e Y.
(c) Discutere brevemente del sistema di assegnamento di tipi alla Curry (type assignment 'a la Curry) studiato durante il corso.
Esercizio 2
(a) Definire in SCHEME il tipo di dato astratto Stack (nella sua versione puramente funzionale).
Definire una funzione SCHEME "perepe" che, preso in input uno Stack restituisce in output lo Stack invertito.
Esempio informale: 
          | 1 |             | 3 |
          | 7 |             | 7 |
(perepe   | 3 | )   --->    | 1 |
          -----             -----
(b) Si consideri la seguente funzione Scheme che prende come input due numeri naturali. 
	(define (Matrix n m)
	     (cond ((= m 0) m)
	           ((= n 0) n) 
		   (else (+ 1 (Matrix (- n 1) (Matrix n (- m 1)))))))
Dimostrare formalmente che la funzione Matrix restituisce il minimo tra i due numeri naturali in input.
Esercizio 3
(a) Definire in Haskell il tipo di dato Stack. Discutere brevemente la soluzione proposta.

(b) Mostrare come evolve l'ambiente (si supponga di partire con l'ambiente che contiene solo il frame a top level vuoto) durante la valutazione della seguente espressione Scheme 
(let ((g (lambda (z) (+ z 1))))
   ((lambda (x) x) (g 2)))