了解评估的环境模型

Question

SICP 练习 3.20：

Draw environment diagrams to illustrate the evaluation of the sequence of expressions
(define x (cons 1 2))
(define z (cons x x))


(set-car! (cdr z) 17)

(car x) 17
using the procedural implementation of pairs given above.

我的眼睛坏了，不能画画。相反，我会尽可能地想象环境模型是如何演变的。

首先，这里是程序对的实现。

(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！和 dispatch 每个都有一个指向 e1
的指针 dispatch 绑定到全局环境中的名称 x

(define z (cons x x))

应用缺点
cons create e2 - 全局封闭
x 绑定到 x 关于全局（共享）
y 相对于全局（共享）绑定到 x
设置-x！，设置-y！和 dispatch 每个都有一个指向 e2
的指针 dispatch 绑定到全局环境中的名称 z

(set-car! (cdr z) 17)

申请套车！
定车！创建 e3 - 全局封闭
z 绑定到 (cdr z) 关于 global
应用 cdr
cdr 创建 e4 - 全局封闭
z 相对于 global
绑定到 z dispatch 创建 e5 - e2 被包围
m 绑定到 'cdr
return x 相对于 e2。
x 与 global 共享 x（以及与 e1 共享 x）
回到 e3
新值绑定到 17
dispatch creates e6 - e2 is enclosing
m 绑定到 'set-car!
设置-x！关于 e2 是 returned
应用 set-x!
设置-x！创建 e7 - e2 被包围
新值绑定到 17
将关于 e2 的 x 设置为 17
由于x是e1，e2中的x和global中的x共享一个指向e1的过程对象，过程对象的car被改变。

我希望这是可以理解的。我的解决方案正确吗？

Answer 1

这里是您的特定问题的答案。

我将全局变量 x 重命名为 v 以避免混淆。

 (define v (cons 1 2))
apply cons
cons created environment called e1 - the global environment is the enclosing environment
x bound to 1
y bound to 2
set-x!, set-y! and dispatch each has a pointer to e1
dispatch is bound to the name v in the global environment

正确。

 (define z (cons v v))
apply cons
cons creates e2 - global is enclosing
x is bound to v with respect to global (shared)
y is bound to v with respect to global (shared)
set-x!, set-y! and dispatch each has a pointer to e2
dispatch is bound to the name z in the global environment

正确。

 (set-car! (cdr z) 17)
apply set-car!
set-car! creates e3 - global is enclosing

没有

_{（以下不使用代码格式化markdown，为visually-impaired把噪音降到最低）}

首先，计算(cdr z)。它等同于 (z 'cdr)。 z 必须从 e2 帧发送。这会发送给 e2 的 y，收到消息 'cdr.此访问 e2 环境框架中的 y 槽，其中包含来自全局环境的 v 值。

接下来，(set-car!v 17) 被评估。它等同于 ((v 'set-car!) 17)。 v 必须调度 of the e1 frame。收到'set-car！消息，它发送到 e1 的 set-x！功能。因此，这将调用 (set-x!17) 和 e1 的 set-x!。这又会在环境框架 e1 内调用 (set! x 17)。因此它访问 - 并且修改 - 环境帧 e1!

中的“x”槽

从现在开始，以后对 v 的任何操作都将反映此更改，因为 v 引用帧 e1，而该帧已更改。 e1帧在“x”下的存储值不再是1，而是17.

访问这些值不会创建新的环境框架。访问值引用的隐藏帧，并可能对其进行修改。

只有 cons 创建新的隐藏环境框架，这些框架附加到新创建的“cons”值（即调度函数）。

下面是先写的，作为说明。不幸的是，我怀疑它对视觉（如果有的话）更有帮助。它包括逐步的评估过程。

我会先 re-write 你的 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))

并且当 this 被评估时，创建了两个绑定——两个地方被预留，一个我们稍后可以称为 x，另一个作为y - 每个都填充了相应的值：对于 x，它是放在那里的 1，对于 y - 2。到目前为止一切顺利。

然后，输入letrec表格。它创建 its 绑定，its 三个特殊位置，分别命名为 set-x!、set-y! 和 dispatch。每个地方都填充了它对应的值，即创建的对应lambda函数。

这是关键部分：因为它是在内部外部(let ([x 1] [y 2]) ...)形式完成的，所以这三个函数中的每一个都知道 关于那两个地方，那两个绑定，对于 x 和 y。每当x或y被set-x!、set-y!或dispatch使用时，实际指的是x或x的位置分别为 y。

这三个函数中的每一个都知道由 (letrec ...) 创建的其他两个函数及其自身。这就是 letrec 的工作原理。使用 let，它创建的名称只知道封闭环境。

创建三个函数后，其中一个 dispatch 作为整个函数的值返回，即原始调用 (cons 1 2).

我们写了 (cons 1 2)，得到了一个值，一个过程 dispatch 知道另外两个过程，也知道两个值的地方，x 和 y.

这个返回值，这个程序在那个letrec里面叫做dispatch-创建了环境，我们可以调用它并使用消息作为参数，读取 'car、'cdr、'set-car! 或 'set-cdr!。没有别的。

停止。退一步。 “环境”。 letrec-created "environment"，由 letrec 表单在 let-created "environment"。我们可以把它想象成两个嵌套的盒子。两个嵌套的矩形，由 let 创建的外部矩形，其中有两个位置（两个隔间，或 "cells"）；和内部的，由 letrec 创建，有三个隔间，里面有三个 单元格 。每个框对应于它的代码片段，代码 form like (let ...) or (letrec ...)，创建 "bindings"，或者名称和地点的关联。

实际上，每个这样的“盒子”都被称为一个环境 frame；所有的嵌套框，每个框都有它的单元格，一起被称为环境。

每个定义的函数都可以访问它的框 – 那个它是创建的 框] – 并且该函数还可以访问恰好包含其创建框的所有外部框。就像代码形式位于另一个内部一样。这正是“作用域”的意思——一个已知名称的代码区域，它指的是一个保存值的地方。

盒子里面的盒子里面的盒子...里面有隔间。仅此而已，真的。

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

并且当返回 dispatch 值时，它是一个存储在该内部环境框架中的名称下的过程，它还有一个隐藏的指针指向由 (letrec ...) 创建的内部框架。该框架还有一个隐藏的指针，指向 its 封闭框的环境框架，由 (let ...) 表单创建。

当let框（代码区域，即作用域）被输入时，它的框架被创建。当输入 letrec 框（范围）时，会创建 its 框架。外框的框架对在它之前创建的封闭框的框架一无所知。最里面的盒子的框架可以访问它周围所有盒子的所有框架，从紧邻它的那个开始。所以这以一种 inside-out 的方式进行：内框的框架包含指向外框框架的指针，而外框（代码区域或范围）包含内框框（代码区域）。

所以当我们调用(((cons 1 2) 'set-car!) 17)时，它被逐步解释为

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

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

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

这里我们选择了top-level评估策略，这样每个新的top-level命令的环境框架都包含在前面的环境框架中。

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

因此它正确地找到了合适的环境框架，E1，进行变异（即改变存储在那里的值）。

了解评估的环境模型

Understanding the environment model of evaluation

evaluation

scheme

sicp

lexical-scope