Niente appunti o calcolatrici. Massima SINTETICITA' nelle risposte.

Esercizio 1
(a) Si consideri il seguente lambda termine:
\g .\y.cons y (g y)
Esiste un punto fisso di tale termine? Perche? Qual e'? Cosa rappresenta? Si puo' utilizzare per fare computazioni?

(b) Fornire un controesempio che mostri che la strategia leftmost-outermost non e' in genere ottimale (non permette cio' di raggiungere la forma normale, se esiste, con il minimo numero di passi)

(c) Trovare tre termini M,P e Q, tali che M contenga x e y tra le sue variabili libere e tali che M[P/x,Q/y] sia diverso da (M[P/x])[Q/y]

Esercizio 2
(a) Definire una funzione Scheme  (un predicato, per essere piu' precisi) "alternevenodd?" su liste di numeri naturali, che restituisca vero se e solo se ogni numero pari della lista di input (tranne eventualmente l'ultimo, ovviamente) e' seguito da un numero dispari e viceversa. Ovviamente e' possibile utilizzare i predicati even? e odd? di Scheme.  

Esempio:    (alternevenodd? (list 3 6 7 8 1 4)) ---> #t          (alternevenodd? (list  6 2 7 4 3)) ---> #f

(b) Si condideri la seguente definizione informale del tipo di dato Sarchiapone :

Un sarchiapone  e' o il  manzanillo o il  minollo, oppure e� il  tirulero di un numero naturale e di un sarchiapone, oppure e� il  zumpappero di due sarchiaponi e di una lista di numeri naturali.

Definire in Scheme il tipodi dato Sarchiapone (e' sufficiente dire quali sono i costruttori, predicati di base e selettori del tipo di dato, non occorre implementarli).

Scrivere in Scheme la funzione porompoppo che, preso un sarchiapone S e due  numeri naturali  n e m, ritorna un sarchiapone uguale ad S, ma con tutte le possibili occorrenze del numero n nel sarchiapone sostituite con m.

Esercizio 3
(a) Definire in HASKELL il tipo di dato Sarchiapone di cui all'esercizio 2(b)

(b) Mostrare la situazione dei frame al termine della valutazione della seguente espressione Scheme.

                                     (let   ((a (lambda (x) x)))  (let  ((b a))  ((b a) 1) ) )