SICP练习3.20 -理解环境图(在我的图表中缺少绑定)

Question

在这个论坛上有一个关于这项工作的问题，但它没有回答我的具体问题。此练习要求绘制环境图

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

其中cons、set-car!和car定义为

(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)

前两件事很简单。我的问题是关于第三个(set-car! (cdr z) 17)，我得到的环境图是这样的

​

​

基于SICP教科书(第3.2.1节)：对参数应用一个过程，创建一个新的环境，其中包含将参数绑定到参数值的框架。此框架的封闭环境是由过程.指定的环境。

因此，(define x (cons 1 2))创建了环境E1。(define z (cons x x))创建E2。

以下几个部分我不太确定，我想的是:因为程序设定--车！针对全局环境，我认为(set-car! (cdr z) 17)应该创建包含在全局中的E3。根据同样的逻辑，(cdr z)应该在全局下创建E4，因为cdr也是在全局下定义的，并且指向全局。

然后，计算(cdr z)调用(z 'cdr)。由于z指向E2，所以E5是在E2下创建的，函数调度体和形式参数m为'cdr，它被求为x，它在全局环境中有它的绑定，因此set-car！的形式参数是z与x的结合，它的绑定可以通过E3找到全局E，新值直接结合到E3中的17。

然后，通过评估(set-car! z new-value)，(z 'set-car!)首先进行评估。由于z被绑定到指向E1的x，所以创建E6时，它的形式参数绑定到'set-car!，函数体在E1中进行调度。返回值是过程set-x!，其绑定在E1中。评估组-x！在E7下创建E1，并将新值赋值给其形式参数v。

我的问题是如何设置-x！找到在单独的环境E3中分配的新值的值？我们追踪从E7到E1然后是全局的父级环境，它永远不会引导到E3，在那里，新值与17结合在一起。

在应用E3时，必须根据set-car!中的句子在全局下创建set-car!。一些在线解决方案跳过了E3和E4在全局下的创建，直接在E7中分配了17，我认为这是不正确的。因为在SICP中写得很清楚，在应用过程时，在过程指定的环境下创建了一个新的环境。

请帮助我理解这一点。谢谢。

更新

更清楚的是，我将代码转换为python，并在PyTutor http://www.pythontutor.com/下运行它。我不明白的是步骤34到35之间，如下图所示。

步骤34：

​

步骤35：

​

从步骤34中可以看到，setcar(cdr(z), 17)在全局环境下创建了一个名为newvalue绑定到17的环境。在下一步(35)中，setx的计算在父f1 (由cons(1,2)创建)下创建了一个单独的环境。这些对我来说都很清楚。

我不明白的是，在setx创建的这个环境中，如何能够找到独立环境(setcar)中的newvalue绑定，并将其赋值给setx，v，as 17的形式参数。

据我从SICP了解，这些程序将在他们自己的环境和他们的父母顺序寻找名字约束力。但是在这里，setcar所指向的环境与setx所指向的环境及其父环境(f1)是独立的。如何在这里进行跨环境的查找？

下面是用我上面给出的链接在PyTutor中可以测试的python代码。

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)

更新2

感谢Will Ness出色的回答，问题被澄清了，下面是我对环境图的更新。

​

​

更新3(2022年)

一些进一步澄清和更新的环境图

• set-x!确实创建了一个新的框架E7，因为它是一个函数调用。它的父框架是E1，因为set-x!是在那里定义的。这就是为什么它能够找到要更新的x的原因。
• E3-E7都是临时环境，最终将在创建这些环境的函数调用返回后被删除。
• 根据Python中的计算规则，在计算整个调用表达式之前，将首先计算操作数。因此，E3到E7的顺序并不准确。我不会更改图表，因为这并不重要。
• 我在上一次更新的图表中提到的内容实际上并不准确。应该是:在计算E5 (而不是E6)之后，在E3中返回的是z函数。set-x!的计算是在自己创建的框架(E7)中进行的，而不是在E3中。
• newvalue是一个操作数，计算值为17，因此它直接传递给内部函数，并直接绑定到内部函数的形式参数。不需要在调用内部函数创建的框架中查找名称newvalue。

以下是更新后的图表：

​

Answer 1

不幸的是，在发表这一问题之前，我仍然有这种做法留下的伤疤。

如果有任何帮助，这是我的图表，我认为它与上面问题中的一个是一致的，主要区别是试图在过程和对它们的引用之间画出所有的界线。

            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)