scheme - 了解评估的环境模型

Question

SICP中的练习3.20:

绘制环境图以说明对序列的评估
表达

(define x (cons 1 2))
(define z (cons x x))


(set-car! (cdr z) 17)

(car x) 17

使用上面给出的对的过程实现。

我的眼睛被毁了，所以我不能画画。相反，我将尽我所能尽可能地想象环境模型如何演变。
首先，这是过程对的实现。

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

每个都有指向全球环境的指针。
这是我所想象的相互作用和解决方案。

(define x (cons 1 2))

应用缺点
缺点创建的环境称为e1-全局环境是封闭环境
x绑定到1
y绑定到2
设置x !，设置y!并调度每个都有一个指向e1的指针
在全局环境中，dispatch绑定到名称x

(define z (cons x x))

应用缺点
缺点创建E2-全局封闭
关于全局(共享)，x绑定到x
相对于全局(共享)，y绑定到x
设置x !，设置y!并调度每个都有一个指向e2的指针
在全局环境中，dispatch绑定到名称z

(set-car! (cdr z) 17)

套车!
订车!创建e3-全局封闭
z关于全局绑定到(cdr z)
应用cdr
cdr创建e4-全局包含
z相对于global绑定到z
调度创建e5-封闭e2
m绑定到'cdr
返回关于e2的x。
x与全局(以及与e1有关的x)共享x
回到e3
新值绑定到17
调度创建e6-封闭e2
m势必会“载车!
设置X!关于e2返回
套用x
设置X!创建e7-封闭e2
新值绑定到17
将关于e2的x设置为17
由于x是e1，因此e2中的x和global中的x共享一个过程对象，该过程对象具有一个指向e1的指针，因此过程对象的汽车发生了变化。
我希望这是可以理解的。我的解决方案正确吗？

Answer 1

这是您特定问题的答案。
我将全局变量x重命名为v以避免混淆。

 (define v (cons 1 2))

应用缺点
缺点创建的环境称为e1-全局环境是封闭环境
x绑定到1
y绑定到2
设置x !，设置y!并调度每个都有一个指向e1的指针
在全局环境中，dispatch绑定到名称 v
正确。

 (define z (cons v v))

应用缺点
缺点创建e2-全局封闭
x关于全局(共享)绑定到v
y关于全局(共享)绑定到v
设置x !，设置y!并调度每个都有一个指向e2的指针
在全局环境中，dispatch绑定到名称 z
正确。

 (set-car! (cdr z) 17)

套车!
订车!创建e3-全局封闭

没有。
(在下文中，不使用代码格式化降价，以将视障人士的噪音降至最低)。
首先，评估(cdr z)。它等效于(z'cdr)。 z势必从e2帧调度。收到消息“cdr”后，这将分派到e2的y。这将访问e2环境帧中的y插槽，该插槽保存全局环境中的v值。
接下来，评估(set-car!v 17)。它等效于((v'set-car!)17)。 v绑定到e1帧的调度。收到了“定车”!消息，它将分派到e1的set-x!功能。因此，这将使用e1的set-x!调用(set-x!17)。依次调用环境框e1中的(设置!x 17)。因此，它访问-并修改-环境框架e1中的“x”插槽!
从现在开始，将来任何使用v的操作都将反映此更改，因为v引用了框架e1，并且该框架已更改。 e1帧在“x”下的存储值不再为1，而是17。
通过访问这些值不会创建新的环境框架。值引用的隐藏帧将被访问，并且可能会被修改。
只有 cons会创建新的隐藏环境框架，这些框架会附加到新创建的“cons”值(即分配函数)上。

首先写了以下内容，以作为说明。不幸的是，我怀疑它对视线(如果有的话)更有帮助。它包括逐步的评估过程。
我将首先将您的 cons函数重新编写为等效的函数，只是稍微冗长一些

(define cons 
   (lambda (x y)
     (letrec ([set-x! (lambda (v) (set! x v))]
              [set-y! (lambda (v) (set! y v))]
              [dispatch 
                  (lambda (m)
                    (cond ((eq? m 'car) x)
                          ((eq? m 'cdr) y)
                          ((eq? m 'set-car!) set-x!)
                          ((eq? m 'set-cdr!) set-y!)
                          (else (error 
                            "CONS: ERROR: unrecognized op name" m))))])
        dispatch)))

Lambda函数也是值，更可以强调它们的价值，可以创建，命名和返回它们。现在，以上意味着在我们的代码中编写 (cons 1 2)与编写

(let ([x 1]
      [y 2])
     (letrec ; EXACTLY the same code as above
             ([set-x! (lambda (v) (set! x v))]
              [set-y! (lambda (v) (set! y v))]
              [dispatch 
                  (lambda (m)
                    (cond ((eq? m 'car) x)
                          ((eq? m 'cdr) y)
                          ((eq? m 'set-car!) set-x!)
                          ((eq? m 'set-cdr!) set-y!)
                          (else (error 
                            "CONS: ERROR: unrecognized op name" m))))])
        dispatch))

当对此求值时，将创建两个绑定-预留两个位置，我们以后可以将其称为 x，另一个称为 y-每个绑定均填充有其对应的值:对于 x而言，它是1放在那儿，然后输入 y –2。到目前为止，一切都很好。
然后，输入 letrec形式。它创建其绑定，并在其三个特殊位置分别命名为 set-x!， set-y!和 dispatch。每个位置均填充有其对应的值，即创建的对应的lambda函数。
这是关键部分:由于是在外部 (let ([x 1] [y 2]) ...)形式内完成的，因此这三个函数每个都知道 x和 y的两个地方，即两个绑定。每当 x， y或 set-x!使用 set-y!或 dispatch时，实际上分别指的是 x或 y的位置。
这三个函数中的每一个都还知道其他两个函数，以及它们自身的信息，它们由 (letrec ...)创建。这就是 letrec的工作方式。使用 let，由它创建的名称仅知道封闭环境。
并且在创建了三个函数之后，其中之一oj​​it_code作为整个对象(即原始调用 dispatch)的值返回。
我们编写了 (cons 1 2)，并获取了一个值，即一个知道其他两个过程以及另一个值位置 (cons 1 2)和 dispatch的过程 x。
这个返回值(在 y创建的环境中称为 dispatch的过程)中，我们可以使用一条消息作为参数来调用它，该消息读取 letrec， 'car， 'cdr或 'set-car!。没别的。
停止。回退一步。 “环境”。由 'set-cdr!创建的“环境”由 letrec创建的“环境”创建。我们可以将其可视化为两个嵌套框。两个嵌套的矩形，最外面的一个由 letrec创建，在其中放置了两个位置(两个间隔或“单元”)；内部是由 let创建的，里面有三个隔间，三个单元格。每个框与其代码片段，代码形式(如 let或 letrec)相对应，以创建“绑定”或名称和位置的关联。
实际上，每个这样的“盒子”都称为环境框架。和所有嵌套的盒子(每个都有其单元格)一起称为环境。
每个定义的函数都可以访问其框(在其中创建了该框)，并且该函数还可以访问所有外部框(其中包含其创建框)。就像代码形式一个位于另一个内部一样。 “作用域”的确切含义是–已知名称的代码区域，该名称指的是持有值的位置。
盒子里面盒子里面盒子里面。真的，仅此而已。

       ________________________________
      |                                |
      | (let   ([ .... ]               |
      |         [ .... ])              |
      |    ______________________      |
      |   | (letrec              |     |
      |   |      ([ .... ]       |     |
      |   |       [ .... ]       |     |
      |   |       [ .... ])      |     |
      |   |   ......             |     |
      |   |   ......             |     |
      |   |   )                  |     |
      |   *----------------------*     |
      |   )                            |
      *--------------------------------*

当返回 (let ...)值(该名称以该名称存储在内部环境框架中的过程)时，它还具有指向由 (letrec ...)创建的内部框架的隐藏指针。而且该框架还具有指向其封闭框的环境框架(由 dispatch形式创建)的隐藏指针。
输入 (letrec ...)框(代码区域，即范围)后，即会创建其框架。输入 (let ...)框(范围)时，将创建其框架。外框的框架对封闭框的框架一无所知。最里面的盒子的框架可以访问它周围所有盒子的所有框架，从紧挨着它的那个开始。因此，这是一种由内而外的方式:内盒的框架包含指向外盒框架的指针，而外盒(代码区域或作用域)包含内盒(代码区域)。
因此，当我们调用 let时，它会逐步解释为

(((cons 1 2) 'set-car!) 17)
=>
(( {dispatch where {E2: set-x!=..., set-y!=..., dispatch=... 
                    where {E1: x=1, y=2 }}} 'set-car!) 17)
=>
(  {(dispatch 'set-car!)
             where {E2: set-x!=..., set-y!=..., dispatch=... 
                    where {E1: x=1, y=2 }}} 17)
=>
(  {set-x!   where {E2: set-x!=..., set-y!=..., dispatch=... 
                    where {E1: x=1, y=2 }}} 17)
=>
{(set-x! 17) where {E2: set-x!=..., set-y!=..., dispatch=... 
                    where {E1: x=1, y=2 }}}
=>
{(set! x 17) where {E2: set-x!=..., set-y!=..., dispatch=... 
                    where {E1: x=1, y=2 }}}
=>
{(set! x 17) where {E1: x=1, y=2 }}
=>
{E1: x=17, y=2 }
     

因为 letrec实际上更改了存储在单元格中的值，所以此更改从现在开始在程序的其余部分中可见:

(define v (cons 1 2))
=>
{dispatch where {E2: set-x!=..., set-y!=..., dispatch=... where {E1: x=1, y=2 }}}
;
((v 'set-car!) 17)
=>
{dispatch where {E2: set-x!=..., set-y!=..., dispatch=... where {E1: x=17, y=2 }}}
;
(v 'car)
=>
({dispatch where {E2: set-x!=..., set-y!=..., dispatch=... where {E1: x=17, y=2 }}} 'car)
=>
{ (dispatch 'car) where {E2: set-x!=..., set-y!=..., dispatch=... where {E1: x=17, y=2 }}}
=>
{ x where {E2: set-x!=..., set-y!=..., dispatch=... where {E1: x=17, y=2 }}}
=>
{ x where {E1: x=17, y=2 }}
=>
17

希望这个伪代码足够清楚。下一个，

(define v (cons 1 2))
=>
{dispatch where {E2: set-x!=..., set-y!=..., dispatch=...
          where {E1: x=1, y=2 }}}
;
(define z (cons v v))
=>
{dispatch where {E5: set-x!=..., set-y!=..., dispatch=...
          where {E4: x=v, y=v
          where {E3: v={dispatch where {E2: set-x!=..., set-y!=..., dispatch=...
                                 where {E1: x=1, y=2 }}} }}}}

在这里，我们选择了顶层评估策略，以便每个新的顶层命令的环境框架都包含在前一个环境框架中。

(((z 'cdr) 'set-car!) 17)
=>
...... (z 'cdr)
...... =>
...... {(dispatch 'cdr) where {E5: set-x!=..., set-y!=..., dispatch=...
......     where {E4: x=v, y=v
......     where {E3: v={dispatch where {E2: set-x!=..., set-y!=..., dispatch=...
......                            where {E1: x=1, y=2 }}} }}}}
...... =>
...... { x where {E5: set-x!=..., set-y!=..., dispatch=...
......     where {E4: x=v, y=v
......     where {E3: v={dispatch where {E2: set-x!=..., set-y!=..., dispatch=...
......                            where {E1: x=1, y=2 }}} }}}}
...... =>
...... { v where {E3: v={dispatch where {E2: set-x!=..., set-y!=..., dispatch=...
......                            where {E1: x=1, y=2 }}} }}
...... =>
...... {dispatch where {E2: set-x!=..., set-y!=..., dispatch=... where {E1: x=1, y=2 }}}
...... <=
... ((z 'cdr) 'set-car!)
... =>
... {(dispatch 'set-car!) where {E2: set-x!=..., set-y!=..., dispatch=...
...                               where {E1: x=1, y=2 }}}
... =>
... { set-x! where {E2: set-x!=..., set-y!=..., dispatch=... where {E1: x=1, y=2 }}}
... <=
(((z 'cdr) 'set-car!) 17)
=>
{ (set-x! 17) where {E2: set-x!=..., set-y!=..., dispatch=... where {E1: x=1, y=2 }}}
=>
{ (set! x 17) where {E2: set-x!=..., set-y!=..., dispatch=... where {E1: x=1, y=2 }}}
=>
{ (set! x 17) where {E1: x=1, y=2 }}
=>
{E1: x=17, y=2 }

因此它可以正确找到合适的环境框架 (((cons 1 2) 'set-car!) 17)进行突变(即更改存储在其中的值)。