'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
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)
Update 2
Thanks to Will Ness's brilliant answer, the problem is clarified and below is my update for the environment diagram
Update 3 (2022)
Some further clarification and an updated environmental diagram
set-x!does create a new frame E7 as it is a function call. Its parent frame is E1 sinceset-x!is defined there. This is reason why it could find thexto update.- E3-E7 are all temporary environments and will be eventually removed after the function calls that create those environments get returned.
- Based on evaluation rule in Python, the operand will be first evaluated before the whole call expression gets evaluated. Thus the order of E3 to E7 is not really accurate. I will not change the diagram as this is not critical.
- What I mentioned in the diagram of my previous update was not really accurate. It should be: After E5 (not E6) is evaluated what is returned to be
zin E3 is the dispatch function. The evaluation ofset-x!is in the frame created by itself (E7) not in E3. newvalueis an operand and evaluated as a value 17. Therefore it passed to internal function and bind to the formal parameter of the internal function directly. There is no need to look for namenewvaluein the frame created by the call of internal function.
Below is the updated diagram:
Solution 1:[1]
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.dispatchsets 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.dispatchsets 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=2The 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
Solution 2:[2]
I still have the scars from this exercise which, unfortunately, I did before this question was posted.
In case it's of any help, here's my diagram which I think is consistent with the one in the question above, the main difference is an attempt to draw all the lines between procedures and the references to them.
para: x para: z
para: y para: z para: z para: new-value
(define (set-x!... (z 'car) (z 'cdr) ((z 'set-car!)...
^ ^ ^ ^
? ? ? ?
@ @ ?? @ @ ?? @ @ ?? @ @ ??
^ ? ^ ? ^ ? ^ ?
global env ??? ? ? ? ? ? ? ? ?
v ? v ? v ? v ? v
????????????????????????????????????????????????????????????????????????????
?cons:???????????? ? ? ? ?
?car:???????????????????????????????? ? ? ?
?cdr:????????????????????????????????????????????? ? ?
?set-car!:???????????????????????????????????????????????????????? ?
? ?
?(after calls to cons) ?
?x:? z:? ?
????????????????????????????????????????????????????????????????????????????
??? ^ ? ^
? ? ? ?
? ,???????????????????????????????????????????????<??? ?
?/ ? ? ? ?
? ,????????????????????????????????????????????<??? ? ?
?/ ? ? ? ? ?
? ? ? ? ? ?
? call to cons ? ? ? ? call to cons ?
v ????????????????????????????? ? ?????????????????????????????
? ?x: 1 (17 after set-x!) ? ? ?x:?? ? ?
? E1 ->?y: 2 ? ? E2 ->?y:????? ?
? ?set-x!:????????????????? ? ? ?set-x!:????????????????? ?
? ?set-y!:?????????? ? ? ? ?set-y!:?????????? ? ?
? ?dispatch:? ? ? ? ? ?dispatch:? ? ? ?
? ????????????????????????????? ? ?????????????????????????????
? ? ^ ? ^ ? ^ ? ? ^ ? ^ ? ^
???>?????????????? ? ? ? ? ? ???????>?????????? ? ? ? ? ?
? v ? v ? v ? ? v ? v ? v ?
? @ @ ? @ @ ? @ @ ? ? @ @ ? @ @ ? @ @ ?
? ? ??? ? ??? ? ??? ? ? ??? ? ??? ? ???
? ? ? ? ? ? ? ?
? ???????????????????????????????????????? ? ?
? ? ???????????????????????????????????????? ?
? ? ????????????????????????????????????????
? ? ? ? ?
? v ? v v
? parameter: m ? parameter: v parameter: v
? (define (dispatch m) ? (set! x v) (set! y v)
? (cond ((eq? m 'car) x) ?
? ((eq? m 'cdr) y) ^
? ((eq? m 'set-car!) set-x!) ?
? ((eq? m 'set-cdr!) set-y!) ?
? (else ... ))) ?
^ ?
? ???????????
??????????? ?
? ? call set-car! ?
? ????????????????????????????? ?
? ?z:? ? ^
? E3 ?>?new-value: 17 ??> global env ?
? ? ? ?
? ????????????????????????????? ?
? ?
? ?????????????
? call to cdr ?
? ?????????????????????????????
? ?z:?????????????????????? ?
? E4 ?>? ??> global env
? ? ?
? ?????????????????????????????
?
?
? call to z (dispatch)
? ?????????????????????????????
? ?m: 'cdr ?
? E5 ?>? ??> E2
? ? ?
? ?????????????????????????????
? (returns 'x' (E1 dispatch))
?
^
?
? call to z (dispatch)
? ?????????????????????????????
? ?m: 'set-car ?
? E6 ?>? ??> E1
? ? ?
? ?????????????????????????????
?
?
? call to set-x!
? ?????????????????????????????
? ?v: 17 ?
? E7 ?>? ??> E1
? ? ?
? ?????????????????????????????
? (E1 modified)
^
?
???????????
? call to car
?????????????????????????????
?z:? ?
E8 ?>? ??> global env
? ?
?????????????????????????????
call to z (dispatch)
?????????????????????????????
?m: 'car ?
E9 ?>? ??> E1
? ?
?????????????????????????????
(returns 17)
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | |
| Solution 2 |