Linguaggi di Programmazione II
(programmazione funzionale)
20 Dicembre 2004
Niente appunti o calcolatrici.
Massima SINTETICITA' nelle risposte.
Esercizio 1
(a)
Qual e' la condizione che deve essere necessariamente soddisfatta per poter correttamente
effettuare una sostituzione M[N/x] ?
Perche' tale condizione e' necessaria?
(b)
Descrivere la differenza tra lambda calcolo tipato 'a la Church
e 'a la Curry.
Nel lambda calcolo tipato semplice 'a la Curry qual e' il senso di avere variabili di tipo
e del lemma di sostituzione?
(c)
Si consideri il seguente lambda termine: \x. cons 3 x.
Esiste un punto fisso di tale termine? Perche'? Qual e'? Cosa rappresenta?
Se tale punto fisso esistesse (chiamiamolo P), avrebbe senso valutare
il termine car(cdr(cdr P)) ? Motivare.
Esercizio 2
(a)
Si supponga di avere il tipo di dato Albero binario etichettato con etichette numeriche.
Si definisca la funzione Scheme che, preso un albero, un predicato P? su numeri, ed un
numero n,
restituisca un albero identico a quello in input, ma tale che le etichette che soddisfano P?
risultino sostituite con n.
(b)
Cosa calcola la seguente funzione Scheme?
(define (X y? n)
(lambda (x)
(or (and (null? x)
(= n 0))
(and (not (null? x))
(if (y? (car x)) ((X y? (- n 1)) (cdr x)) ((X y? n) (cdr x)) )))))
Dimostrare che la valutazione di (X y? n) termina per ogni y? e per ogni n.
Dimostrare che la valutazione di ((X even? n) ls) termina per ogni naturale n e lista ls.
Esercizio 3
(a)
Supponete di aver definito una funzione Haskell di nome funct.
Dire cosa fa il sistema se si scrive:
type funct
Dire cosa avrebbe fatto il sistema se prima della definizione di funct uno avesse scritto:
funct :: [Int] -> Bool
(b)
Considerare la seguente sessione SCHEME:
(define h
(lambda (g)
( (g (lambda (y) y) ) (+ 1 2))))
(define g 5)
(h (lambda (x) x))
Mostrare la situazione dei frame alla fine della valutazione di (h (lambda (x) x))
e prima che i frame non piu' necessari vengano eventualmente eliminati.
Qual e' il valore di (h (lambda (x) x)) ?