了解评估的环境模型

问题描述 投票：2回答：1

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

适用利弊 cons创建了一个名为e1的环境 - 全球环境就是封闭的环境 x绑定到1 y必然是2 set-x！，set-y！并且每个都有一个指向e1的指针 dispatch绑定到全局环境中的名称x

(define z (cons x x))

适用利弊 cons创造e2 - 全球是封闭的 x相对于全局（共享）绑定到x y关于全局（共享）绑定到x set-x！，set-y！并且每个都有一个指向e2的指针 dispatch绑定到全局环境中的名称z

(set-car! (cdr z) 17)

适用套装车！ 设置的车！创造e3 - 全球是封闭的 对于全局，z被绑定到（cdr z） 申请cdr cdr创建e4 - 全局封闭 z相对于全局绑定到z 发送创建e5 - e2是封闭的 m必然是'cdr 相对于e2返回x。 x与全局共享x（以及与e1相关的x） 回到e3 新值必然是17 发送创建e6 - e2是封闭的 米必然会'定车'！ 设置-X！关于e2被退回 申请set-x！ 设置-X！创造e7 - e2是封闭的 新值必然是17 将x相对于e2设置为17 由于x是e1，e2中的x和全局中的x共享一个过程对象，该过程对象具有指向e1的指针，因此过程对象的汽车被更改。

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

scheme evaluation sicp lexical-scope
1个回答
3
投票

以下是您具体问题的答案。

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

 (define v (cons 1 2))

适用利弊 cons创建了一个名为e1的环境 - 全球环境就是封闭的环境 x绑定到1 y必然是2 set-x！，set-y！并且每个都有一个指向e1的指针 dispatch在全球环境中与v这个名称绑定

正确。

 (define z (cons v v))

适用利弊 cons创造了e2 - 全球是封闭的 x相对于全局（共享）绑定到v y与全局（共享）绑定为v set-x！，set-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！功能。因此，这将调用（set-x！17）e1的set-x！。这又在环境框架e1内调用（set！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将作为整个函数的值返回，即原始调用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框（范围）时，将创建其框架。外盒的框架对封闭盒子的框架一无所知，在它之前创建。最里面的盒子的框架可以访问它周围所有盒子的所有框架，从它周围的框架开始。所以这是以一种由内向外的方式进行的：内框的框架包含指向外框框架的指针，而外框（代码区域或范围）包含内框（代码区域）。

因此，当我们调用letrec时，它逐渐被解释为

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

所以它正确地找到适当的环境框架(((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 } 来变异（即改变存储在那里的值）。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.