ESERCIZI SCHEME OPERATIONAL SEMANTICS
Esercizio 1
Fornire un'espressione define scorretta secondo la semantica operazionale
studiata nel corso, ma che risulterebbe corretta se si eliminasse
nella regola (dec1) l'assunzione che x non debba appartenere ad Op.
Esercizio 1.5
Si dica qual e' il valore restituito dalla
valutazione dell'espressione finale della seguente
sessione Scheme, e si mostri la situazione
dei frame.
(define f (lambda (x) x))
(define g (+ 1 2))
(let ((g f)
(a g))
(+ a (f g)))
Esercizio 2
Si dica qual e' il valore della seguente espressione Scheme,
mostrando la situazione dei frames al termine della sua valutazione
(let ((b 4)
(a 3))
(lambda (x) (x + a)))
Esercizio 3
Fornire nel modo piu' breve e conciso possibile il significato di
Scoping statico e Scoping dinamico
Esercizio 4
Introduciamo in Scheme una nuova parola chiave "buargh".
La semantica di
una buargh-espressione (buargh exp1 exp2) e' la
seguente:
si valutano,
nell'ordine, exp1 ed exp2 e si restitiusce una lista di quattro
elementi
in cui il primo
valore e' il valore di exp1, il secondo ed il terzo sono 0
ed il quarto
e' il valore di exp2.
Formalizzare
tale sematica con una o piu' regole della SOS.
Esercizio 5
Modificare le regole (dec2), lambda) e (appl1) della nostra SOS in modo tale
che SCHEME venga ad avere scoping dinamico (il corpo di una funzione e' cioe
valutato nell'ambiente di chiamata e non in quello in cui la funzione
viene definita).
Soluzione.
Esercizio 6
Nota: supporre che gli argomenti di una funzione vengano valutati da destra a sinistra.
Soluzione.
Esercizio 7
Fornire degli esempi che mostrino la differenza dei risultati che si possono
avere se nella SOS si modifica la regola (if1) in modo tale che anziche'
l'assuzione "v' diverso da #f" si abbia "v' = #t".
Considerare poi il caso in cui in (if1) si sostituisca "e1 -> v'" con
"e1 -> #t" ed in (if2) si sostituisca "e1 -> #f" con "e1 -> v' e v' diverso
da #t"
Esercizio 8
Soluzione.
Esercizio 9
Inoltre, dire quale sarebbe il valore dell'ultima espressione della seguente
sessione SCHEME supponendo l'interprete modificato come descritto:
(define x 2)
(define (f x)
(let ((g (lambda (y) (+ y x)))
(g x)))
(f 1)
Soluzione.
Esercizio 10
La regola (Var2) della nostra SOS e' quella che, insieme a (Var1) descrive
cosa fa l'interprete per trovare il valore di un identiicatore.
Consideriamo ora la seguente versione modificata della regola (Var2):
(a) Quale sarebbe ora il valore dell'ultima espressione della seguente
sessione SCHEME?
(define a 3)
(define (f y) (+ y a))
(f 1)
(b) Perche?
(c) Descrivere brevemente quello che fa l'interprete durante la valutazione di (f
1),
utilizzando la rappresentazione grafica dei frame.
Soluzione.
Esercizio 11
Dire sinteticamente, con precisione e proprieta' di linguaggio
quello che fa l'interprete al momento di valutare un'applicazione
in SCHEME e che e' formalmente descritto dalla regola (appl1)
della SOS.
Soluzione.
Esercizio 12
Modificare la regola (var 2) della nostra Semantica Operazionale Strutturata
nel seguente modo:
aggiungere le ipotesi zeta (n')= (n'',rho') e n''not= bottom
e sostituire n'' ad n' nella seconda riga delle ipotesi.
Dire come si modifica il comportamento dell'interprete con tali modifiche.
Dire qual'e' il valore dell'ultima espressione della seguente sessione
SCHEME con la semantica modificata e quale con la semantica non modificata,
descrivendo graficamente la situazione dei frame.
(define (f y)
(let ((h (lambda (y)
(let ((g (lambda (x)
(+ x y))))
(g 1)))))
(h 4)))
(f 7)
Soluzione.
Esercizio 13
Considerare la seguente sessione SCHEME:
(define f
(lambda (y)
((lambda (x) x) (g 1))))
(define g ????)
(f 4)
Dire cosa si puo' inserire al posto di "????" affiche'
alla fine della valutazione di (f 4) (e prima che i frame non piu'
utili vengano eventualmente eliminati) la situazione dei frame
sia la seguente:
| f --> <.., ....> |
| g --> ...... |
-----------------------
^ ^
n3 | | n1
------ |
|x-->1| ----------- n2 --------------------
----- | y --> 4 | <-----| x --> < n4, ...> |
^ ----------- --------------------
| n4
Ridisegnare anche la figura sopra riempiendo i puntini.
Soluzione.
Esercizio 14
- Scrivere una regola nello stile della Semantica Operazionale Strutturata
che esprima il fatto che in un'applicazione, se la prima espressione dopo
la parentesi
ha come valore un qualsivoglia
operatore (un elemento di Op) e se il valore
di tutte le altre espressioni e' uguale a 3, allora il valore
dell'applicazione e 0.
- Sia zeta l'ambiente totale descritto dalla figura dell'esercizio precedente.
Disegnare l'ambiente rappresentato dalla seguente espressione:
(zeta[n5,< n4,empty[w,3][z,8]>])[n6,< n2,empty[w,3]>]
dove empty denota l'ambiente vuoto.
Soluzione.
Esercizio 15
Considerare la seguente sessione SCHEME:
(define f
(lambda (y)
((lambda (x) x) (g 1))))
(define g ????)
(f 4)
Dire cosa si puo' inserire al posto di "????" affiche'
i frame aperti durante la valutazione di (f 4) siano quelli descritti nel seguito.
| f --> <.., ....> |
| g --> ...... |
-----------------------
^ ^
n3 | | n1
------ |
|x-->1| ----------- n2 ----------
------ | y --> 4 | <-----| x --> 2 |
^ ----------- ----------
| n4
------ n5
|x-->2| <-----
-------
Ridisegnare anche la figura sopra riempiendo i puntini.
Soluzione.
Esercizio 16
Vogliamo introdurre nello SCHEME un nuovo tipo di espressioni:
(paperinik e1 e2 e3)
La semantica informale di una paperinik-espressione e' la seguente:
Viene valutata l'espressione e1 e poi l'espressione e3. Se i loro valori
sono numerici e la loro somma e' 3 allora il valore di tutta l'espressione
e' il valore di e2. Altrimenti il valore dell'espressione e' 0. Inoltre,
nel secondo caso, le eventuali modifiche all'ambiente totale apportate
dalla valutazione di e1 ed e3 debbono scomparire.
Scrivere una o piu' regola nello stile della Semantica Operazionale Strutturata
che descrivano formalmente la semantica di una paperinik-espressione.
Esercizio 17
Disegnare l'ambiente rappresentato dalla seguente espressione:
zeta1[Next(zeta1), < Next(EMPTY), empty[y,2][x,2]>]
dove zeta1 e'
EMPTY[Next(EMPTY),< bottom, empty[f,1][g,1]>].
EMPTY denota l'ambiente totale vuoto, mentre empty il frame vuoto.
Esercizio 18
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 | <------
| | | |
------------------------------------ -------------
Soluzione.
Esercizio 19
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.
Esercizio 20
Vogliamo introdurre nello SCHEME un nuovo tipo di espressioni:
(paperoga e1 e2)
La semantica di una paperoga-espressione e' equivalente
a quella di (if e1 e2 5).
Scrivere una o piu' regola nello stile della Semantica Operazionale Strutturata
che descrivano formalmente la semantica di una paperoga-espressione.
Esercizio 21
Fornire l'espressione che denoti formalmente il seguente ambiente:
------------
| a --> 3 |
| b --> 4 |
------------
^
|
|
----------- ----------
| y --> 4 | <-----| x --> 2 |
----------- ----------
N.B. Useremo "EMPTY" per denotare l'ambiente totale vuoto, ed "empty" per il frame vuoto.
Esercizio 22
Descrivere una (o piu') regole in Semantica Operazionale Strutturata
che forniscano la semantica del costrutto "let" in modo diretto.
Mostrare come ad un identificatore locale del costrutto "let" non sia possibile
associare una funzione definita ricorsivamente.
Soluzione.
Esercizio 22b
Fornire una (o piu') regole in Semantica Operazionale Strutturata
che forniscano la semantica del costrutto "letrec", che
permette di associare ad un identificatore locale
una funzione definita ricorsivamente.
La semantica informale del costrutto letrec supponiamo essere la seguente:
estendiamo il frame corrente n con un nuovo frame n', in cui gli identificatori
locali sono inizialmente associati al valore indefinito '?'. Nel nuovo frame vengono poi
valutate le espressioni associate agli identificatori, una di seguito
all'altra, ed il loro valore sostituito ai vari '?' man mano. Alla fine si valuta il body.
Con tale semantica, la valutazione della seguente sessione Scheme
(define a 3)
(letrec ((a a))
a)
restituisce <undefined> (che e' appunto quello che restituiscce il DrScheme).
La valutazione di
(define a 3)
(letrec ((a 3)
(b (+ a b)))
a)
produce invece errore poiche' il valore da sommare ad a e' indefinito.
Notare che ad un identificatore locale, per esempio var1, e' possibile benissimo
associare il valore di una lambda espressione nel cui corpo sia presente l'identificatore var1
(o anche un'altra delle var_i).
Essendo tale lambda espressione
valutata a partire dal puntatore n', la chiusura corrispondente al valore v1,
sara' <n', exp1>. Questo significa che, quando andremo a valutare una applicazione
di tale chiusura ad un argomento, il corpo della funzione sara' valutato a partire dal
frame puntato da n' (che contiene la funzione ricorsiva).
Possibile Soluzione (By P. Giarrusso). (file pdf)
Esercizio 23
Dire perche' l'interprete da come valore di
(let ((fact (lambda (x) (if (= 0 x) 1
(* x (fact (- x 1)))))))
(let ((fact (lambda (x) (if (= 0 x) 1
(* x (fact (- x 1)))))))
(let ((fact (lambda (x) (if (= 0 x) 1
(* x (fact (- x 1)))))))
(let ((fact (lambda (x) (if (= 0 x) 1
(* x (fact (- x 1)))))))
(let ((fact (lambda (x) (if (= 0 x) 1
(* x (fact (- x 1)))))))
(fact 3))))))
il numero 6, mentre da il seguente errore:
"reference to undefined identifier: fact"
se cerchiamo di valutare
(let ((fact (lambda (x) (if (= 0 x) 1
(* x (fact (- x 1)))))))
(let ((fact (lambda (x) (if (= 0 x) 1
(* x (fact (- x 1)))))))
(let ((fact (lambda (x) (if (= 0 x) 1
(* x (fact (- x 1)))))))
(let ((fact (lambda (x) (if (= 0 x) 1
(* x (fact (- x 1)))))))
(let ((fact (lambda (x) (if (= 0 x) 1
(* x (fact (- x 1)))))))
(fact 5))))))
Esercizio 24
Scrivere una espressione SCHEME il cui valore sia una chiusura che contiene al suo
interno un'altra chiusura.
Soluzione.
Esercizio 25
Considerare la seguente sessione SCHEME:
(define f
(lambda (g)
( (g (lambda (x) x) ) (+ 1 1))))
(define g ????)
(f (lambda (x) x))
Dire cosa si puo' inserire al posto di "????" affiche'
l'interprete non dia errore.
Mostrare inoltre la situazione dei frame alla fine della valutazione di (f (lambda (x) x)) e prima che i frame
eventualmente non piu' necessari vengano eliminati.
Soluzione.
Esercizio 26
Fornire l'espressione che denoti formalmente il seguente ambiente:
------------
| a --> 3 | ----------
| b --> 4 | <----| a -->3 |
------------ ----------
^
|
|
----------- ----------
| y --> 4 | <-----| x --> 2 |
----------- ----------
N.B. Useremo "EMPTY" per denotare l'ambiente totale vuoto, ed "empty" per il frame vuoto.
Soluzione.
Esercizio 27
Scrivere una espressione SCHEME il cui valore sia la chiusura
< p1, (lambda (x) (x x)) >, dove p1 punta al frame empty[a,3] il cui padre
(il frame immediatamente superiore) e' il frame al top-level.
Soluzione.
Esercizio 28
Considerare la seguente sessione SCHEME:
(define f
(lambda (g)
(( k 3 ) (g 1))))
(define k ????)
(f (lambda (x) x))
Dire cosa si puo' inserire al posto di "????" affiche'
l'interprete non dia errore.
Mostrare inoltre la situazione dei frame alla fine della valutazione di (f (lambda (x) x)) e prima che i frame
eventualmente non piu' necessari vengano eliminati.
Soluzione.
Esercizio 29
Considerando la regola SOS (appl1), dire cosa succederebbe se la quarta assunzione
fosse sostituita con la seguente
Zeta'1 = Zetam+1[n', < n'', rho[x1, v1]...[xm, vm][y1, ?]...[yq, ?] > ]
dove
Zetam+1(n') = < n'', rho >.
Dire , con la semantica operazionale cosi' modificata, qual'e' il valore
dell'espressione (f 5) alla fine della seguente sessione SCHEME.
Rappresentare graficamente l'ambiente totale immediatamente prima
del completamento della valutazione di (f 5).
(define x 2)
(define a 3)
(define (f x)
(let ((x 4)
(a 1))
(+ a x)))
(f 5)
Soluzione.
Esercizio 30
A cosa serve la Semantica Operazionale Strutturata?
Esercizio 31
Fornire la semantica dell'espressione cond sia indirettamente
in termini di espressioni if, sia direttamente, con regole
della semantica operazionale strutturata.
Esercizio 32 (non difficile, ma piuttosto complesso)
Mostrare l'evoluzione dell'ambiente durante la valutazione della
seguente sessione SCHEME.
(define (K x)
(lambda (x)
(+ (let ((x 1)
(fun (lambda (y) (+ x 1))))
(fun x))
(+ x x))))
(define t 44)
(define x 8)
(let ((x (+ x 2))
(gg (lambda (y) t))
(t 66)
(fun 21))
( (lambda (x) (+ (gg 1) fun)) ((K fun) x) ))
Soluzione.
Esercizio 33
Fornire una o piu' espressioni "define" ed una espressione exp tali che,
una volta valutate le espressioni "define",
durante la valutazione di exp si produca un ambiente della forma seguente
|-------------| n1 |-------------| n2 |-------------|
| ........ | <------ | ........ | <------| y -> <..,n1>|
| ........ | | ........ | | ........... |
|-------------| |-------------| |-------------|
Il frame piu' a sinistra e' il frame al top-level.
I frames descritti possono contenere quello che si vuole, ma il frame piu'
a destra deve contenere l'associazione di y con una chiusura il cui puntatore
punta al frame al top-level.
Soluzione
Esercizio 34
Fornire la semantica dell'espressione cond con regole
della semantica operazionale strutturata.
Per semplicita' supporre che la valutazione di sottoespressioni di una
espressione cond non modifichi l'ambiente.
Soluzione
Esercizio 35
Considerare il seguente costrutto lett con la seguente sintassi
(lett ((b1 var1 exp1 exp'1)
..................
(bn varn expn exp'n))
exp)
Il valore di un'espressione lett e' il valore di exp valutata
nell'ambiente in cui viene valutata l'espressione lett esteso
con un frame con le associazioni vari --> vi. Il valore vi e' calcolato valutando
l'espressione booleana bi nell'ambiente in cui viene valutata l'espressione
lett. Se il valore di bi e' falso si valuta (sempre nell'ambiente di lett)
l'espressione expi, altrimenti exp'i.
Fornire la semantica dell'espressione lett o direttamente con delle regole
della semantica operazionale strutturata oppure indirettamente in termini
di altri costrutti SCHEME (let escluso).
Soluzione
Esercizio 36
Considerare il costrutto double-let con la seguente sintassi
(double-let ( ((var1 exp1)
:
(varn expn)) )
((var'1 exp'1)
:
(var'm exp'm)) ) )
expa; expb)
Il valore di un'espressione double-let valutata in un frame rho,
si ottiene nel seguente modo:
si estende rho con un frame rho' contenente le associazioni vari -> vi (i=1,..,n),
dove vi e' il valore di expi valutato in rho. Poi si estende sempre rho con un frame
rho" contenente le associazioni var'j -> v'j (j=1,..,m),
dove v'j e' il valore di exp'j valutato in rho'. Quindi si valuta expa in rho' e
expb in rho". Il valore finale dell'intera espressione double-let e' il valore
di expb.
Fornire la semantica dell'espressione double-let con una o piu' regole
della semantica operazionale strutturata.
Soluzione
Esercizio 37
Fare una bella domanda intelligente la cui risposta sia "chiusure".
Esercizio 38
Spiegare perche' perche' non e' possibile fornire (intendiamo "fornire in modo semplice",
in modo complicato si potrebbe)
una semantica operazionale dello SCHEME (non solo dello SCHEME completo, ma anche
del solo frammento da noi considerato nel corso)
solo in termini di lambda-calcolo e beta-riduzione,
ma occorra invece andare ad utilizzare nozioni come frame, ambiente ecc..
Esercizio 39
Dimostrare formalmente, con una deduzione nel sistema della Semantica Operazionale Strutturata
che la valutazione dell'espressione
( ((lambda (x) x) +) y 3 )
nell'ambiente Z a partire dal puntatore p1, ha come valore 8 e non modifica l'ambiente.
Si supponga che Z sia un ambiente contenente, tra gli altri, i frame descrivibili graficamente come segue:
^
| p3
------------------
| y --> 5 |
| pippo --> true |
------------------
^
| p2
|
--------------
| x --> 64 | <---- p1
| z --> 3 |
--------------
Soluzione
Esercizio 40
Supponiamo di introdurre un nuovo tipo di espressione in SCHEME, della forma
(clarabella var1 var2 exp1 exp2 exp3)
Se valutiamo una clarabella espressione partendo da un frame puntato da n,
il suo valore e' quello dell'espressione exp3 valutata in n2, dove n2 e'
come indicato nel diagramma seguente e dove i frame puntati da n1 e n2
vengono creati dalla valutazione della clarabella espressione.
Inoltre v1 e' il valore di exp1 valutato in n, mentre v2 e' il valore
di exp2 valutato in n1.
| n ______________ n1 ______________ n2
| <--- | var1 -> v1 | <--- | var2 -> v2 | <----
----------- -------------- --------------
Fornire una espressione SCHEME il cui effetto sia esattamente
quello della valutazione di una clarabella espressione.
Soluzione
Esercizio 41
Mostrare graficamente come evolve l'abiente se facciamo valutare all'interprete
SCHEME l'espressione
( (lambda (x) (x x)) (lambda (x) (x x)) )
Soluzione
Esercizio 42
Fornire una o piu' espressioni define e un'espressione exp
tale che il valore di exp sia 1, ma tale che avrebbe come valore 2 se
lo SCHEME avesse scoping dinamico.
Soluzione
Esercizio 43
Mostrare graficamente come evolve l'ambiente durante la valutazione
della seguente espressione SCHEME
( (lambda (f) (f 3)) (lambda (x) x) )
Soluzione
Esercizio 44
Mostrare graficamente come evolve l'ambiente se facciamo valutare all'interprete SCHEME l'espressione
(fun 1) dove fun e' definita precedentemente come
(define fun
(lambda (x)
(let ((a (- x 1)))
(fun a))))
Soluzione
Esercizio 45
Mostrare graficamente come evolve l'ambiente se facciamo valutare all'interprete SCHEME l'espressione (fun 1) dove fun e' definita precedentemente come
(define fun
(lambda (x)
(let ((a (- x 1)))
(fun x))))
Soluzione
Esercizio 46
Mostrare la situazione dei frame al termine della valutazione
della seguente espressione.
(define f
( (lambda (y) (lambda (x) (+ 1 y))) 1) )
Soluzione
Esercizio 47
Mostrare la situazione dei frame al termine della valutazione
della seguente espressione.
(define f ( (lambda (z) (lambda (y) (+ 5 z))) 1) )
Discutere brevemente la soluzione data.
Soluzione
Esercizio 48
Scrivere una regola per la Semantica Operazionale Strutturata dello
SCHEME per la valutazione di un nuovo tipo di espressione
(spatti e )
la cui semantica informale e' la seguente: si valuta l'espressione
"e" e si restituisce sempre il valore numerico 3.
Le eventuali
modifiche all'ambiente causate dalla valutazione di e vanno pero'
considerate.
Discutere brevemente la soluzione data.
Soluzione
Esercizio 49
Scrivere una regola per la Semantica Operazionale Strutturata dello
SCHEME per la valutazione di un nuovo tipo di espressione
(cacettu e1 e2)
la cui semantica informale e' la seguente: si valuta e1 poi, di seguito, e2.
Il valore di una cacettu-espressione e' sempre il valore booleano true.
Le eventuali
modifiche all'ambiente causate dalla valutazione di e1 ed e2 vanno pero'
considerate.
Soluzione
Esercizio 50
Mostrare la situazione dei frame al termine della valutazione della
seguente espressione Scheme.
(let ((a (lambda (x) x)))
(let ((b a))
((b a) 1) ) )
Soluzione
Esercizio 51
Per definire correttamente la Semantica Operazionale Strutturata dello Scheme il testo
(Structured Operational Semantics of a fragment of the language Scheme) introduce
una funzione Next(-). Quali sono il dominio e codominio di Next?
Cosa restituisce? Discutere un punto della Semantica Operazionale Strutturata in cui viene utilizzata.
Esercizio 52
Vogliamo introdurre nello SCHEME un nuovo tipo di espressioni:
(paperinika e1 e2 e3)
La semantica informale di una paperinika-espressione e' la seguente:
Viene valutata l'espressione e1 e poi l'espressione e2.
Se i loro valori sono numerici e il valore di e1 e' minore di quello di
e2 allora il valore di tutta l'espressione e' il valore di e2.
Altrimenti il valore dell'espressione e' il valore di e3.
Scrivere una o piu' regola nello stile della Semantica Operazionale
Strutturata che descrivano formalmente la semantica di una paperinika-espressione.
Esercizio 53
Mostrare l'ambiente al termine della valutazione della espressione Scheme
( (lambda (y) (+ y 3)) (+ x y) )
supponendo di valutarla nel seguente ambiente avendo p1 come puntatore di frame corrente.
^ pTop
|
------------------
| y --> 5 |
| pippo --> true |
------------------
^
| p2
--------------
| x --> 64 | <---- p1
| y --> 3 |
--------------
Esercizio 54
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 ((f (lambda (x) (+ x 1))))
((lambda (y) y) (f 2)))
Soluzione
Esercizio 55
Vogliamo introdurre nello SCHEME un nuovo tipo di espressioni: (paperoga e1 e2)
La semantica di una paperoga-espressione e' equivalente a quella di (if e1 e2 5).
Scrivere una o piu' regola nello stile della Semantica Operazionale Strutturata
che descrivano formalmente la semantica di una paperoga-espressione.
Esercizio 56
Mostrare l'ambiente al termine della valutazione della espressione Scheme
( ((lambda (x) x) +) (pippo y) (let ((y y)) 3) )
supponendo di valutarla nel seguente ambiente avendo p1 come puntatore di frame corrente.
Dire anche qual e' il valore restituito dall'interprete.
^
| pTop
-----------------------------------------
| y --> 5 |
| pippo --> < (lambda (x) (+ y x)), p1> |
-----------------------------------------
^
| p2
|
--------------
| y --> 64 | <---- p1
| z --> 3 |
--------------
Esercizio 57
Dire qual e' il valore di (f 1) nella seguente sessione scheme e giustificarlo
mostrando l'evoluzione dei frame durante la valutazione di (f 1).
(define a 3)
(define (f y)
(let ( (a (+ a 1) )
(b (+ a 1) ) )
(+ y (+ a b))))
(f 1)
Esercizio 58
Considerare la seguente sessione SCHEME:
(define f
(lambda (g)
( (g (lambda (x) x) ) (+ 1 1))))
(define g 1)
(f (lambda (x) x))
Mostrare la situazione dei frame alla fine della valutazione di (f (lambda (x) x))
e prima che i frame non piu' necessari vengano eventualmente eliminati.
Qual e' il valore di (f (lambda (x) x)) ?
Soluzione
Esercizio 59
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)) ?
Soluzione
Esercizio 60
- Mostrare l'ambiente alla fine della valutazione di (G 4) nella
seguente sessione Scheme.
(define (G z)
(let ((f (lambda (x) (let (( y 1)) (+ y x)))))
(f z)))
(G 4)
Esercizio 61
- Supponiate che venga aggiunta allo Scheme la parola chiave "oink"
e che la nostra S.O.S. per lo Scheme contenga la seguente regola di
inferenza:
Z,n |-- e1 --> <(lambda (x) e), n'>,Z'
Z'[Next(Z'),(n',0[pippo,<(lambda (x) e),
n'>])], Next(Z')|-- e2 --> v,Z"
-----------------------------------------------------------------------------------------
Z,n |-- (oink e1 e2) --> v, Z"
Descrivere a parole cosa fa l'interprete per valutare una
oink-espressione
Esercizio 62
- Qual e' il valore dell'ultima espressione valutata nella seguente
sessione Scheme?
(define x 1)
(define (F x y)
(let ((x 3)
(y x))
(let ((x 4)
(f
(lambda (z) (+ z x)))
(y
y))
(+ x ( f y)))))
(F x 3)
- Descrivere graficamente i frame al termine della valutazione di
(F x 3)
Esercizio 63
- Qual e' il valore dell'ultima espressione valutata nella seguente
sessione Scheme?
(define x 1)
(define y x)
(define (F z t)
(let ((x 3)
(y (+ z 3))
(f (lambda (z)
(+ z x))))
(+ x ( f y))))
(F y y)
Descrivere graficamente i frame al termine della valutazione di
(F y y)
Esercizio 64
Considerare la seguente sessione SCHEME:
(define (f y) (+ y 1))
(f ??)
Dire cosa si puo' inserire al posto di "??" affinche' alla fine della valutazione di (f ??) (e prima che i frame non piu' utili vengano eventualmente eliminati) la situazione dei frame sia la seguente ed il valore di (f ??) risulti 4:
| f --> <..., ........> |
---------------------------------------
^ ^ ^ ^
n1 | | | |___________
------------------------------- | | |
| g --> < n1, (lambda (x)...)>| | ----------- |
------------------------------- | | y --> 2 | |
----------- ----------- |
| x --> 3 | -----------
----------- | y --> 3 |
-----------
Ridisegnare anche la figura sopra riempiendo i puntini.
Soluzione
Esercizio 65
Supponiate che venga aggiunta allo Scheme la parola chiave "Boink"
e che la nostra S.O.S. per lo Scheme contenga la seguente regola di
inferenza:
Z,n |-- e1 --> <(lambda (x) e), n'>,Z'
Z'[Next(Z'),(n,0[pippo,<(lambda (x) e), n>])], Next(Z')|-- e2 --> v,Z"
-----------------------------------------------------------------------------------------------------------
Z,n |-- (Boink e1 e2) --> v, Z"
Descrivere a parole cosa fa l'interprete per valutare una Boink-espressione
Descrivere lo stato dei frame alla fine dalla valutazione della seguente
sessione Scheme e dire qual e' il valore restituito.
(define x 34)
(Boink ( (lambda (x) x) (lambda (y) y)) (pippo x) )
Soluzione
Esercizio 66
Si consideri la seguente funzione F sui numeri interi
F 0 = 0
F x = if x > 0 then 1 + F (1-x) else 1 + F (-1-x)
Che cosa calcola F?
Dimostrarlo formalmente.
Soluzione