pythonschemecomputation-theorysicplexical-scope

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


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

enter image description here

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: enter image description here

Step 35: enter image description here

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)

Update 2

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

enter image description here

Update 3 (2022)

Some further clarification and an updated environmental diagram

Below is the updated diagram: enter image description here


Solution

  • 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 frame 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 frame 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