SICP exercise 3.20 - understand the envrionmental diagram (missing binding in my diagram)

Question

There was a question regarding this exercise in this forum, but it dose not answer my specific question. This exercise asks to draw the environmental diagrams for

(define x (cons 1 2))
(define z (cons x x))
(set-car! (cdr z) 17)
(car x)

where cons, set-car! and car are defined as

(define (cons x y)
  (define (set-x! v) (set! x v))
  (define (set-y! v) (set! y v))
  (define (dispatch m)
    (cond ((eq? m 'car) x)
          ((eq? m 'cdr) y)
          ((eq? m 'set-car!) set-x!)
          ((eq? m 'set-cdr!) set-y!)
          (else (error "Undefined operation -- CONS" m))))
  dispatch)
(define (car z) (z 'car))
(define (cdr z) (z 'cdr))
(define (set-car! z new-value)
  ((z 'set-car!) new-value)
  z)
(define (set-cdr! z new-value)
  ((z 'set-cdr!) new-value)
  z)

The first two are very straightforward. My question is regarding the third one (set-car! (cdr z) 17) The Environmental Diagram I obtained is like this

Based on SICP textbook (section 3.2.1): To apply a procedure to arguments, create a new environment containing a frame that binds the parameters to the values of the arguments. The enclosing environment of this frame is the environment specified by the procedure.

Thus (define x (cons 1 2)) creates environment E1. (define z (cons x x)) creates E2.

The following parts I am not so sure, what I thought is: because procedure set-car! pointed to global environment, I think (set-car! (cdr z) 17) should create E3 which is enclosed in global. With the same logic, (cdr z) should create E4 under global, as cdr is also defined under global and points to global.

Then, evaluating (cdr z) invokes (z 'cdr). Because z points to E2, E5 is created under E2, with body of function dispatch and formal parameter m as 'cdr. This is evaluated to x which has its binding in global environment. Thus the formal parameters of set-car! are z bonded to x whose binding can be found through E3 to global E and new-value bonded to 17 in E3 directly.

Then by evaluating (set-car! z new-value), (z 'set-car!) evaluates first. As z is bonded to x pointed to E1, E6 is created with its formal parameter bonded to 'set-car! and the function body is dispatch in E1. The return value is procedure set-x! whose binding is found in E1. Evaluating of set-x! create E7 under E1 and new-value is assigned to its formal parameter v.

My question is how set-x! finds the value of new-value which assigned in a separate environment E3? It we trace the parents environments from E7 to E1 then global, it will never guide to E3 where the new-value bonded to 17.

Based on the sentence in SICP, E3 must be created under global when applying set-car!. Some solutions online skip the creation of E3 and E4 under global and assign 17 directly in E7, which I think is not correct. Because it is written clearly in SICP that when applying a procedure a new environment is created under the environment specified by the procedure.

Please help me to understand this. Thank you.

Update

To be more clear, I translate the code to python and run it under PyTutor http://www.pythontutor.com/. What I do not understand is between step 34 and 35 as shown in the pictures below

Step 34:

Step 35:

As you can see from step 34, setcar(cdr(z), 17) created a environment under global environment with the name newvalue bound to 17. In the next step (35), the evaluation of setx created a separate environment under the parent f1 (created by cons(1,2)). These are all clear for me.

What I do not understand is how it is possible in this environment created by setx, the binding of newvalue which is in a separate environment (setcar) can be found and assign to formal parameter of setx, v, as 17.

As I understand from SICP, the procedures will look in their own environments and their parents sequentially for name binding. But here, the environment that setcar pointed to is independent from the environment setx pointed to and its parent environment (f1). How the cross environments look-up is possible here?

Below is the python code can be tested in PyTutor with the link I gave above.

def cons(x, y):
    def setx(v):
        nonlocal x
        x=v
    def sety(v):
        nonlocal y
        y=v
    def dispatch(m):
        if m == 'car': return x
        elif m == 'cdr': return y
        elif m == 'setcar': return setx
        elif m == 'setcdr': return sety
        else: print("Undefined operation -- CONS", m)
    return dispatch

def car(z):
    return z('car')

def cdr(z):
    return z('cdr')

def setcar(z, newvalue):
    z('setcar')(newvalue)
    return z

def setcdr(z, newvalue):
    z('setcdr')(newvalue)
    return z

x = cons(1,2)
z = cons(x,x)
setcar(cdr(z), 17)
car(x)

Updated 2

Thanks to Will Ness's brilliant answer, the problem is clarified and below is my update for the environment diagram

related, almost duplicate (no pictures though). short recap of the answer: there's no E3. — Will Ness
I use my own textual representation for the environment frames, in the answer linked above. I can't follow these pictograms. :) --- see the illustrative sequence after the sentence "So when we call (((cons 1 2) 'set-car!) 17), it is progressively interpreted as ...". What is unclear there? — Will Ness
"it is written clearly in SICP that when applying a procedure a new environment is created under the environment specified by the procedure" this is done temporarily; then the answer is found and returned, and that environment is discarded. — Will Ness
@WillNess Thanks for your kind and valuable comment. Unfortunately I do see a E3, as shown clearly in the PyTutor plot in my updates. In PyTutor plot, the environment "setcar" under global is exactly what I have E3 in my plot which is created with evaluating set-car! (or setcar in python). What is unclear for me is then, why the name binding of new-value in this environment can be found in by set-x! which is inherited from E1 (created with (define x (cons 1 2))) not E3. Please have a look at my update python code and PyTutor output. Thanks again. — englealuze
@WillNess "this is done temporarily; then the answer is found and returned, and that environment is discarded." I think whether the environment is temporary is not the point. The problem for me is to understand why answer can be founded. For me, the name "new-value" is bound in a different environment then where procedure set-x! pointed to. And there is no inherit relation between these 2 different environments. Based on the evaluation rule defined in SICP, there should be no way for set-x! to find out the so called "new-value" for v is 17. — englealuze

Will Ness Will Ness · Accepted Answer · 2018-07-17T00:46:57

With your Python code (which I'll regard as a pseudocode with Scheme-like semantics),

def cons(x, y):
    def setx(v):
        nonlocal x
        x=v
    def sety(v):
        nonlocal y
        y=v
    def dispatch(m):
        if m == 'car': return x
        elif m == 'cdr': return y
        elif m == 'setcar': return setx
        elif m == 'setcdr': return sety
        else: print("Undefined operation -- CONS", m)
    return dispatch

def car(z):
    return z('car')

def cdr(z):
    return z('cdr')

def setcar(z, newvalue):
    z('setcar')(newvalue)
    return z

def setcdr(z, newvalue):
    z('setcdr')(newvalue)
    return z

we have (in pseudocode)

# xx = cons(1,2)
Exx = { x=1, y=2, setx={Exx,setx_proc}, sety={Exx,sety_proc}, 
        dispatch={Exx,dispatch_proc} }
xx = Exx.dispatch

sets xx to hold a value, a closure of dispatch procedure and its enclosing cons environment frame -- let's call this closure Exx -- with entries under x, y, setx, sety, and dispatch; in the place x there's stored the value 1, and in y - the value 2; then,

# zz = cons(xx,xx)
Ezz = { x=Exx.dispatch, y=Exx.dispatch, setx={Ezz,setx_proc}, sety={Ezz,sety_proc}, 
        dispatch={Ezz,dispatch_proc} }
zz = Ezz.dispatch

sets zz to hold a value, a closure of dispatch procedure and its enclosing cons environment frame -- let's call this closure Ezz -- with entries under x, y, setx, sety, and dispatch; in the place x there's stored the value of xx, Exx.dispatch, and in y - also the value of xx, Exx.dispatch; then,

setcar(cdr(zz), 17)                     # find the value of the argument
1. = setcar(cdr(zz), 17)                # find the value of the argument
2. = setcar(cdr(Ezz.dispatch), 17)      # zz is Ezz.dispatch !
3. = setcar(Ezz.dispatch('cdr'), 17)    # by the def'n of cdr
4. = setcar(Ezz.y, 17)                  # by the def'n of dispatch
5. = setcar(Exx.dispatch, 17)           # in Ezz.y there's Exx.dispatch !
6. =   Exx.dispatch('setcar')(17) ; return(Exx.dispatch)     # by the def'n of setcar
7. =   Exx.setx(17) ; return(Exx.dispatch)     # Exx.dispatch to Exx.setx !
8. =   Exx.x=17 ; return(Exx.dispatch)         # by the def'n of setx
9. = Exx.dispatch                       # where Exx.x=17, Exx.y=2

The evaluation of 7. Exx.setx(17) does not create any new environment frames. This setx belongs to Exx frame, and thus refers to the Exx's entry under x.

And so the x place in the Exx environment frame is updated to hold the value 17.

So then, afterwards,

car(xx)
= car(Exx.dispatch)
= Exx.dispatch('car')
= Exx.x
= 17

SICP exercise 3.20 - understand the envrionmental diagram (missing binding in my diagram)

2 Answers