首页 文章

将值绑定到环境模型中的帧

提问于
浏览 次
1

我对评估的环境模型如何运作有点困惑，并希望有人可以解释 .

SICP说：

环境模型指定：要将过程应用于参数，请创建一个包含框架的新环境，该框架将参数绑定到参数的值 . 此框架的封闭环境是过程指定的环境 . 现在，在这个新环境中，评估过程体 .

第一个例子：

如果我：

(define y 5)

在全球环境中，然后打电话

(f y)

哪里

(define (f x) (set! x 1))

我们构建了一个新环境（e1） . 在e1中，x将绑定到y（5）的值 . 在体内，x的值现在为1.我发现y仍然是5.我相信这是因为x和y位于不同的帧中 . 也就是说，我完全取代了x的值 . 我修改了绑定x的帧，而不仅仅是它的值 . 那是对的吗？

第二个例子：

如果我们在全球环境中：

(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 (set-car! z new-value)
  ((z 'set-car!) new-value)
  z)

现在我说：

（定义z2（缺点1 2））

假设z2在一个名为e2的环境中有一个调度过程的值，我调用：

(set-car! z2 3)

设置车！创造一个新的环境e3 . 在e3中，参数z绑定到z2的值（e2中的调度过程），就像在我的第一个例子中一样 . 在执行主体之后，z2现在是'（3 2） . 我觉得定车！它的工作方式是因为我正在改变z所持有的对象的状态（在全局中也被z2引用），但不替换它 . 也就是说，我没有修改绑定z的帧 .

在第二个例子中，看起来全局中的z2和e3中的z是共享的 . 我不确定我的第一个例子 . 根据在环境模型中应用过程的规则，看起来x和y是共享的，尽管它完全不可检测，因为5没有本地状态 .

我说的一切都是正确的吗？我误解了这句话吗？

scheme parameter-passing lisp sicp lexical-scope

3 回答

  • 1

    回答你的第一个问题：假设你打算在第一个问题而不是 (f 5) 中写 (f y) ，y不被修改的原因是球拍（像大多数语言一样）是"call by value"语言 . 也就是说，值被传递给过程调用 . 在这种情况下，然后在调用 f 之前将参数 y 计算为 5 . 突变 x 绑定不会影响 y 绑定 .

    回答第二个问题：在第二个例子中，有共享环境 . 也就是说， z 是一个在环境中关闭的函数（你称之为 e2 ） . 每次调用 z 都会创建一个链接到现有 e2 环境的新环境 . 在此环境中对 x 或 y 执行突变会影响以后对 e2 环境的所有引用 .

    总结：传递变量的值与传递包含该变量的闭包不同 . 如果我说

    (f y)

    ......在完成调用之后，'y'仍将引用相同的值[*] . 如果我写

    f (lambda (...) ... y ...)

    （也就是说，传递一个引用 y 的闭包，那么在调用 f 之后y可能被绑定到一个不同的值 .

    如果你发现这令人困惑，你并不孤单 . 关键是：不要停止使用闭包 . 相反，停止使用变异 .

    [*]如果 y 是一个可变值，它可能会被突变，但它仍然是"same"值 . 请参阅上面关于混淆的说明 .

    回复于
  • 1

    TL; DR：Scheme中的简单值是不可变的，当作为参数传递给函数时会被完整复制 . 复合值是可变的，作为指针的副本传递，而复制的指针指向与原始指针相同的内存位置 .

    你正在努力解决的问题被称为"mutation" . 像5这样的简单值是不可变的 . 没有“ set-int! ”来改变 5 从此在我们的计划中保持42的值 . 而且没有 .

    但是变量's value is mutable. A variable is a binding in a function invocation'的帧，它可以用 set! 更改 . 如果我们有

    (define y 5)
(define (foo x) (set! x 42) (display (list x x)))
(foo 5)
   --> foo is entered
       foo invocation environment frame is created as { x : {int 5} }
       x's binding's value is changed: the frame is now { x : {int 42} }
       (42 42)    is displayed
       y still refers to 5 in the global environment

    但是如果 foo 收到一个本身持有可变引用的值，它可以被改变，即改变"in place"，那么虽然改变了foo 's frame itself doesn't，但是它所引用的绑定值可以是 .

    (define y (cons 5 6))     ; Scheme's standard cons
   --> a cons cell is created in memory, at {memory-address : 123}, as
                   {cons-cell {car : 5} {cdr : 6} } 
(define (foo x) (set-car! x 42) (display (list x x)))
(foo y)
   --> foo is entered
       foo invocation environment frame is created as 
             { x : {cons-cell-reference {memory-address : 123}} }
       x's binding's value is *mutated*: the frame is still
             { x : {cons-cell-reference {memory-address : 123}} }
           but the cons cell at {memory-address : 123} is now
                   {cons-cell {car : 42} {cdr : 6} } 
       ((42 . 6) (42 . 6))    is displayed
       y still refers to the same binding in the global environment
         which still refers to the same memory location, which has now 
         been altered in-place: at {memory-address : 123} is now
                   {cons-cell {car : 42} {cdr : 6} }

    在Scheme中， cons 是一个原语，它可以创建可变的cons单元格，可以使用 set-car! 和 set-cdr! 进行就地更改 .

    这些SICP练习打算表明的是，没有必要将它作为一个原始的内置程序;它可以由用户实现，即使它不是在Scheme中内置的 . 拥有 set! 就足够了 .

    另一个术语是说"boxed"值 . 如果我将5传递给某个函数，当该函数返回时我保证仍然有我的5，因为它是通过复制它的值传递的，设置函数调用框架的绑定来引用值5的副本（这也只是当然是整数5） . 这就是所谓的"pass-by-value" .

    但是如果我"box"它并将 (list 5) 传递给某个函数，那么复制的值 - 在Lisp中 - 是指向这个"box"的指针 . 这被称为"pass-by-pointer-value"或其他东西 .

    如果该函数使用 (set-car! ... 42) 突变该框，则它就地更改，此后我将在该框中有42个 (list 42) - 与之前相同的内存位置 . 我的环境框架的绑定将不会改变 - 它仍然会在内存中引用相同的对象 - 但是值本身将被更改，更改到位，变异 .

    这是因为盒子是复合基准 . 无论我在其中放入简单值还是复合值，框本身（即可变cons单元格）都不简单，因此将通过指针值传递 - 仅指针将被复制，而不是指向它 .

    回复于
  • 2

    x 绑定到 y 的值意味着 x 是一个新绑定，它接收 y 包含的相同值的副本 . x 和 y 不是共享内存位置的别名 .

    虽然由于优化问题，绑定并不完全是内存位置，但您可以通过这种方式对其行为进行建模 . 也就是说，您可以将环境视为一个由符号命名的存储位置包 .

    事实上，教育方案计划评估员使用关联列表来表示环境 . 因此 (let ((x 1) (y 2)) ...) 创建了一个看起来像 ((y . 1) (x . 2)) 的环境 . 存储位置是此列表中 cons 对的 cdr 字段，其标签是 car 字段中的符号 . 细胞本身就是结合;符号和位置由于处于相同的结构而绑定在一起 .

    如果这个 let 周围有一个外部环境，那么可以使用cons将这些关联对推到它上面：

    (let ((z 3))
  ;; env is now ((z . 3))
  (let ((x 1) (y 2))
     ;; env is now ((y . 2) (x . 1) (z . 3))

    环境只是我们推动的一堆绑定 . 当我们捕获一个词法闭包时，我们只需要获取当前指针并将其存入闭包对象 .

    (let ((z 3))
  ;; env is now ((z . 3))
  (let ((x 1) (y 2))
     ;; env is now ((y . 2) (x . 1) (z . 3))
     (lambda (a) (+ x y z a))
     ;; lambda is an object with these three pices:
     ;; - the environment ((y . 2) (x . 1) (z . 3))
     ;; - the code (+ x y z a)
     ;; - the parameter list (a)
     )
  ;; after this let is done, the environment is again ((z . 3))
  ;; but the above closure maintains the captured one
)

    因此，假设我们使用参数10调用 lambda .lambda获取参数列表 (a) 并将其绑定到参数列表以创建新环境：

    ((a . 1))

    这种新环境不是在真空中制造的;它被创建为捕获环境的扩展 . 所以，真的：

    ((a . 1) (y . 2) (x . 1) (z . 3))

    现在，在这个有效的环境中，执行了 (+ x y z a) 主体 .

    您可以通过参考这种绑定模型来理解您需要了解的有关环境的所有内容 .

    分配变量？对于基于cons的绑定，这只是 set-cdr! .

    什么是“扩展环境”？它只是将基于缺点的绑定推到前面 .

    什么是"fresh binding"的变量？这只是用 (cons variable-symbol value) 分配新单元格并通过推动它来扩展环境 .

    什么是"shadowing"变量？如果环境包含 (... ((a . 2)) ...) 并且我们将新绑定 (a . 3) 推送到此环境，则此 a 现在可见，并且 (a . 2) 被隐藏，因为 assoc 函数线性搜索并首先找到 (a . 2) ！内部到外部环境查找由 assoc 完美建模 . 内部绑定显示在外部绑定的左侧，更靠近列表的头部，并且首先被找到 .

    共享语义遵循这些单元列表的语义 . 在关联列表模型中，当两个环境关联列表共享相同的尾部时，会发生环境共享 . 例如，每次我们调用上面的lambda时，都会创建一个新的 (a . whatever) 参数环境，但它会扩展相同的捕获环境尾部 . 如果lambda更改 a ，则其他调用不会看到，但如果它更改 x ，则其他调用将看到它 . a 是lambda调用的私有，但 x ， y 和 z 在其捕获的环境中是lambda的外部 .

    如果你在精神上依赖这个关联列表模型，那么就可以解决环境行为，包括任意复杂的情况 .

    真正的实现基本上只围绕这个优化 . 例如，从像 42 这样的常量初始化并且从未分配的变量根本不必作为实际环境条目存在;名为"constant propagation"的优化只能用 42 替换该变量的出现，就像它是一个宏一样 . 真实实现可以使用哈希表或其他结构用于环境级别，而不是关联列表 . 可以编译实际实现：可以根据诸如"closure conversion"的各种策略来编译词汇环境 . 基本上，整个词法范围可以扁平化为单个类似矢量的对象 . 在运行时进行闭包时，将复制并初始化整个向量 . 编译代码不是指变量符号，而是指闭包矢量中的偏移，这实际上更快：没有通过关联列表的线性搜索是需要 .

    回复于

相关问题