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
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 since set-x!
is defined there. This is reason why it could find the x
to update.z
in E3 is the dispatch function. The evaluation of set-x!
is in the frame created by itself (E7) not in E3.newvalue
is 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 name newvalue
in the frame created by the call of internal function.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