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)应该在global下创建E4，因为cdr也在global下定义，指向global。

然后，评估 (cdr z) 调用 (z 'cdr)。因为z指向E2，所以在E2下创建E5，函数体dispatch，形参m为'cdr。这被评估为在全局环境中具有绑定的 x。这样就设置了car的形式参数！是 z 绑定到 x 的绑定可以通过 E3 找到到全局 E 和 new-value 直接绑定到 E3 中的 17。

然后(set-car! z new-value)先求值，(z 'set-car!)先求值。由于 z 绑定到指向 E1 的 x，因此创建 E6 时其形式参数绑定到 'set-car! 并且函数体在 E1 中调度。 return 值是在 E1 中找到绑定的过程 set-x!。评估set-x！在 E1 下创建 E7 并将新值赋给其形参 v.

我的问题是怎么设置-x！找到在单独环境 E3 中分配的新值的值？如果我们跟踪从 E7 到 E1 然后全局的父环境，它永远不会引导到新值绑定到 17 的 E3。

根据SICP中的那句话，应用set-car!时必须在全局下创建E3。网上有些解决方案跳过了全局下创建E3和E4，直接在E7中赋值17，我觉得是不正确的。因为SICP里面写的很清楚，当应用一个过程时，会在过程指定的环境下创建一个新的环境。

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

更新

为了更清楚，我在 PyTutor http://www.pythontutor.com/ 下将代码翻译成 python 和运行。我不明白的是如下图所示的步骤34和35之间

第 34 步：

步骤 35:

从第34步可以看出，setcar(cdr(z), 17)在全局环境下创建了一个环境，名称newvalue绑定到17。在下一步（35）中，[=31的评估=] 在父 f1 下创建了一个单独的环境（由 cons(1,2) 创建）。这些我都清楚了。

我不明白的是，在setx创建的这个环境中，如何可以找到在单独环境（setcar）中的newvalue的绑定并赋值给setx、v的形参，如17.

正如我从 SICP 了解到的那样，这些过程将依次在它们自己的环境和它们的父级中查找名称绑定。但是在这里，setcar 指向的环境独立于 setx 指向的环境及其父环境（f1）。这里如何进行跨环境查找？

下面是 python 代码，可以在 PyTutor 中使用我上面给出的 link 进行测试。

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 都是临时环境，在创建这些环境的函数调用得到 returned 后最终将被删除。
根据Python中的求值规则，操作数将在整个调用表达式求值之前先求值。因此，E3 到 E7 的顺序并不准确。我不会更改图表，因为这并不重要。
我之前更新的图表中提到的并不准确。应该是：在评估 E5（不是 E6）之后，E3 中 returned 为 z 的是调度函数。 set-x!的计算是在自己创建的框架（E7）中，而不是在E3中。
newvalue是一个操作数，求值为17。因此它传递给内部函数，直接绑定到内部函数的形参。内部函数调用创建的frame中不需要查找namenewvalue

下面是更新后的图表：

Answer 1

使用您的 Python 代码（我将其视为具有类似 Scheme 语义的伪代码），

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

我们有（伪代码）

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

设置 xx 来保存一个值，dispatch 过程的闭包及其封闭的 cons 环境框架——我们称这个框架为 Exx -- x、y、setx、sety 和 dispatch 下的条目；在 x 处存储了值 1，在 y 中存储了值 2；那么，

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

设置 zz 来保存一个值，dispatch 过程的闭包及其封闭的 cons 环境框架——我们称这个框架为 Ezz -- x、y、setx、sety 和 dispatch 下的条目；在 x 处存储了 xx、Exx.dispatch 的值，在 y 中存储了 xx、Exx.dispatch 的值；那么，

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

7. Exx.setx(17) 的评估不会创建任何新的环境框架。此 setx 属于 Exx 框架，因此引用 Exx 在 x 下的条目。

因此 Exx 环境框架中的 x 位置 更新为保存值 17.

那么，之后，

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

Answer 2

我仍然有这个练习的伤疤，不幸的是，我在发布这个问题之前就已经这样做了。

如果它有任何帮助，这是我认为与上述问题中的图表一致的图表，主要区别在于试图在过程和对它们的引用之间划清界限。

            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)

SICP 练习 3.20 - 理解环境图（我的图中缺少绑定）

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

python

scheme

sicp

computation-theory

lexical-scope