Una volta acquisite le nozioni contenute in “Structured Operational Semantics of a fragment of the language Scheme” di Honsell, Pravato, Ronchi Della Rocca vediamo come applicarle per la risoluzione di un esercizio tipico.

Descrivere gli ambienti 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) ))

Trattiamo la descrizione distinguendo i vari passi.
Sia P_A_top il puntatore al top level environment.

1. Leggiamo la definizione di una funzione (define (K x) …), perciò si crea l’associazione “nome funzione” à <1° argomento chiusura, 2° argomento chiusura >, in cui il 1° argomento della chiusura è la definizione della funzione, mentre il secondo indica il puntatore all’ambiente in cui abbiamo dichiarato la funzione : stiamo applicando la regola (dec 2).
   
   
   
   
2. Leggiamo (define t 44) quindi aggiungiamo all’ambiente corrente la nuova associazione (dec 1):
   
   
   
3. Leggiamo (define x 8) quindi aggiungiamo all’ambiente corrente la nuova associazione (dec 1):
   
   
   

4.   Valutiamo    (let ((x (+ x 2))
                               (gg (lambda (y) t))
                               (t 66)
                               (fun 21))
                                              ( (lambda (x) (+ (gg 1) fun)) ((K fun) x) )).
   Nell’ambiente corrente  calcoliamo il valore dei secondi argomenti delle coppie del let ed estendiamo l’ambiente con un nuovo frame che contiene le nuove associazioni. 
   
   

5. Dobbiamo valutare (lambda (x) (+ (gg 1) fun)) il cui valore è la chiusura
   < lambda (x) (+ (gg 1) fun)) , p₂ > ⁽¹⁾ (lambda).
   La valutazione dell’argomento ((K fun) x ) implica quella di (K fun) e cioè K nel frame puntato da p₂ .
   Il valore di K si trova in P_A_top, cerchiamo quello di fun a partire da p₂ verso P_A_top e lo troviamo in p₂ (appl 1).
   Estendiamo l’ambiente con un nuovo frame contenente l’associazione parametri formali / parametri attuali di K: x à 21 e vi valutiamo
   (lambda (x)(+ (let ((x 1) (fun (lambda (y) (+ x 1)))) (fun x)) (+ x x)) )).
   
   
   
6. Il valore di (lambda (x)  (+ (let ((x 1)   (fun (lambda (y) (+ x 1)))) (fun x))    (+ x x)) )) è la chiusura < lambda (x) (+ (let ((x 1)(fun (lambda (y) (+ x 1))))(fun x))  (+ x x)) ), p₃>.  Recuperiamo il valore da assegnare a x relativo a (lambda … ) e sarà quello contenuto nel frame puntato da p₂ per questione di scoping, e procediamo con la solita estensione con un nuovo frame:
   
   
   
7. Si tratta di un’addizione, quindi applichiamo la regola (appl 2): un argomento è il let, perciò …
   
   
   
8. Valutiamo in p₅ fun x recuperando tramite la regola (var 1) le associazioni x à 1 e   fun à < lambda (y) (+ x 1), p₄ >; quindi valutiamo il corpo di fun in p₄ calcolando    fun x = 11. I frame puntati da p₅ e p_5bis non servono più, quindi li eliminiamo. Per l’addizione interna (+ x 1) abbiamo utilizzato (appl 2) la quale non ha modificato l’ambiente.
   
   
   
9. Adesso calcoliamo l’altro termine dell’addizione: (+ x x) nel frame puntato da p4: a x è associato il valore 10 quindi (+ x x) vale 20. Perciò il valore di (+  (let ((x 1)  (fun (lambda (y) (+ x 1)))) (fun x))    (+ x x)) )) è 31 e cancelliamo p3 e p4 e i frame ad essi relativi. Abbiamo così terminato al valutazione di ((K fun) x).
   
   
   
10. Prima abbiamo calcolato il valore di (lambda (x) (+ (gg 1) fun)) dato dalla chiusura ⁽¹⁾ del punto 5. Possiamo quindi valutare l’applicazione: estendiamo l’ambiente con un nuovo frame.
    
    
    
11. Calcoliamo (+ (gg 1) fun)) in p₆. Cerchiamo gg che si trova nel frame indicato da p₂ ed appendiamo a P_A_top il frame contenente l’associazione y à 1 in cui si valuterà il corpo dell’applicazione gg.
    
    
    
12. Il valore di t è 44, poi valutiamo fun che ha valore 21 ed eseguiamo l’addizione. Il valore di  (+ (gg 1) fun))  è così 65. I puntatori p₂, p₆ e p₇ non sono più necessari e possiamo eliminarli.