Programmazione Funzionale
  3 Marzo 2006

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 (supponendo di avere gia' i lambda-termini if, add, iszero,pre e Y) : 
0*y = 0
x*y = (y + (x-1)*y)     se x diverso da 0
(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 termina su ogni coppia di naturali.
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)))