三个问题w.r.t.评估的环境模型 [英] Three questions w.r.t. the environment model of evaluation

问题描述

我正在阅读SICP书这里介绍命令式编程模型。我无法理解两点的插图：

1. Wrt从 square 到pair（这两个圆圈）的箭头：这个箭头是什么意思？虽然在本节中，箭头表示封闭环境，但这个特定的箭头似乎并没有指向一个环境。（ square 的环境是 global env ，而不是pair）


2. 低于正确理解：在过程定义的值中，其代码文本部分）没有对符号内的符号进行解释。他们只是文本。只有在应用程序过程中，它们才会在应用程序的上下文/环境中获得含义。
如果2是正确的，为什么箭头从环境部分这对（右边的
圈）到封闭的环境是必要的吗？ （因为在过程定义内的过程代码中解释符号的含义是没有意义的。）

解决方案

SICP的箭头符号有点超载。我将引用文本的相关部分来理解此图。

过程对象是一对代码，它指定该过程具有一个形式参数，即x和一个过程体（* xx）。过程的环境部分是一个指向全局环境的指针，因为这是评估lambda表达式以生成过程的环境。将过程对象与符号正方形相关联的新绑定已添加到全局框架中。一般来说，define通过向框架添加绑定来创建定义。

所以，我们来分析每个箭头。

1. 全球环境→广场。这个箭头似乎只是将方块标记为象征全球环境的方块。值得注意的是，由于 define 在全局环境中被调用，因此该环境是唯一活动的堆栈框架。

square→两个点。这个箭头似乎指出，无论这两个点代表的是存储在全局环境中找到的名称square。 p>


2. left dot→参数/body。这个箭头表示左边的点是一个对象，被认为是存储两个数据，形式参数列表和过程体。




3. 右点→正方形。这个箭头表示正确的点包含一个指针，它返回到全局环境。

---

该图给出了一个高度可操作的POV，了解符号如何在Lisp中产生意义。特别是，符号在特定的上下文中被评估。上下文是一个环境框架链接列表，每个框架都包含一些名称→值映射集。要评估一个符号后面的链表，并返回从符号名称映射的第一个值。以图表方式为例：

 foo→{bar：3→{foo：8}→{ foo：10} 
，baz：4} 
  

通过跳过第一帧并找到值 8 ，$ c> foo 返回 8 >在第二帧中，而忽略第三帧。这种忽略功能非常重要 - 它暗示某些上下文可能具有影响来自更大上下文的值的名称。

---

这里的整个图像表示如下：

1. 在全局上下文中调用 define 添加一个新的名称→值映射到全局框架。



2. 存储一个lambda对象存储两条信息（两个点）
   
   

   
   

   • 左边的点包含lambda主体的文本以及被认为是形式参数的符号列表。

   >
   

   • 正确的点包含对某个堆栈帧的引用，它可能是也可能不是全局帧，尽管它恰好是图片中的全局框架

   
   





最后，我们应该谈谈评估lambda的含义。要评估一个lambda，你必须给它传递一个值的列表。它使用该输入值列表并将它们与它存储的正式参数列表进行匹配，以便生成一个将形式参数映射到输入值的新环境框架。然后，它使用该新框架作为主框架并将链接框架作为后续上下文来评估lambda的主体。在图表中，我们假设 square 看起来像



  + ---形式参数列表
 / + ---函数体
 | | 
（left：（x）（* xx））（right：{global frame}）
  



<然后，当我们评估它像（square 3）时，我们使用 3 和形式参数列表创建一个新框架

  {x：3} 
  

并评估身体。首先我们查找名称 * 。由于它不在我们新的本地框架中，我们必须在全局框架中找到它。

 *→{x ：3}→{global frame} 
  

原来存在那里，并且是乘法的定义。因此，我们需要传递一些值，以便查找x

 x→{x：3} →{global frame} 
  

自 x 存储在本地框架中，我们在那里找到它并将 3 和 3 作为参数传递给我们找到了乘法函数。





重要的部分是局部框架阴影全局框架。这意味着如果 x 在全局框架中也有意义，我们会在评估的主体的情况下覆盖正如我被要求在回答有关问题的背景下回答这个问题一样。




---





变量的含义是什么---重要的是要注意，以上是非常特定的变量语义的实现。在表面上，你总是可以说lisp中的变量意味着这个过程发生了。尽管如此，这还是有点难度的。



变量这个词的另一个语义（我和大部分数学都喜欢）是这样一个概念上下文中的变量表示域中特定的，固定但未知的值。如果我们检查 square

lambda 的定义> （lambda（x）（* xx））


在解释（* xx）时，我们看到 x 或多或少是这个短语的预期语义。作为一些价值的价值（例如一个数字），但我们不知道任何事情。在解释（lambda（x）（* xx））时，我们看到为了理解lambda内部短语的含义，我们必须给它一个 X 。这大体上是各地使用的变量和函数的标准语义。





挑战在于这里描述的栈框架实现也被设置为容易违反

这个语义---事实上，它在这个例子中非常巧妙。具体来说： define 打破了语义。原因在下面的代码片段中很明显：



 （define foo 3）
 foo 
（define foo 4）
 foo 
  

在这个片段中，我们依次评估每个短语并且看到假设固定但未知）变量 foo 从第2行改变为第4行。这是因为 define 允许我们编辑存在于上下文中的堆栈框架，而不仅仅是创建一个新的上下文，它会像 lambda 那样影响旧的上下文。这意味着我们必须将变量视为不是固定但未知的变量，而是一系列不能保证随时间推移而保持其价值的可变插槽 - 一种更为复杂的语义，可能会迫使我们调用 foo 一个槽或一个可分配的。



我们也可以将其看作是一个漏洞抽象。我们希望变量具有标准的固定但未知语义，但由于堆栈框架的机制和 define 的行为，我们并不完全遵循这个含义。



最后，Lisps经常给你一个叫做 let 的表单，它可以用来复制前面的例子而不会丢弃变量语义：



 （let（（foo 3））
 foo 
（let （foo 4））
 foo）
 foo）
  

在这种情况下，第2行的 foo 取值 3 ， foo 第4行存在于不同的变量上下文中，因此只有阴影第2行上的 foo ...和从而取得不同的固定值 4 ，最后第5行的 foo 再次与 foo 在第2行，并采用相同的值。





换句话说， let 允许我们创建任意l ocal上下文（巧合的是，你可能期望在后台创建新的栈帧）。让我们知道这些语义的金科玉律是安全的，被称为，稍有不幸，α转换。这条规则规定，如果您在一个上下文中将变量均匀地和均匀地重命名，那么程序的含义不会改变。





因此，前面的例子是通过α-转换，与这个例子相同的

pre $ （let（（ foo 3））
foo
（let（（bar 4））
bar）
foo）


，因为我们不再需要担心阴影效应 foo 。





---





那么我们可以让Lisp的 define 语义更安全吗？有点。您可以想象下面的转换：



1. 不允许定义的循环依赖关系，例如（定义xy）（定义yx）不允许，而（定义x 3）（定义yx）不允许。


2. 将所有 define s移到任何给定上下文（堆栈框架）的开头，并将它们按依赖顺序排列。 li>
   
3. 对于re define 任何变量
   

事实证明，这种转换有点棘手（代码移动很困难，所以可能是循环依赖），但是如果你解决了一些小问题，你会发现在任何情况下变量只能精确地一个固定但未知的值。





您还可以找到以下内容 - 以下任何程序，转换后的形式

 （define x ...定义x ...）
（定义y ...定义y ...）
（定义z ...的定义...）
 ... body ... 
  

相当于下面的内容：



 （let（（x ...定义x ...））
（ let（（y ...定义y ...））
（let（（z ...定义z ...））
 ... body ...）））
  

这是另一种显示我们漂亮，简单的固定但未知数量的变量语义保持的方式。


I am reading the SICP book Here about the imperative programming model. I could not understand the illustration in two points:

1. W.r.t. the arrow from square to the "pair" (the two circles): What does this arrow mean? Though throughout this section, an arrow means "enclosing environment", this specific arrow seems not pointing to an environment.(square 's environment is the global env, not the "pair")
2. Is below a correct understanding: in the value of a procedure definition, its "code text" part (the left circle) has no interpretation of the symbols within. They are just "text". Only at procedure application, they gain meaning inside the context / environment of the application.
3. If 2 is correct, Why the arrow from the environment part of the pair (the right circle) to the enclosing environment is necessary? (since there is no meaning to interpret the meaning of symbols within procedure code inside the procedure definition.)

解决方案

SICP's arrow notation is a little overloaded. I'll quote the relevant portion of the text to understand this diagram.

The procedure object is a pair whose code specifies that the procedure has one formal parameter, namely x, and a procedure body (* x x). The environment part of the procedure is a pointer to the global environment, since that is the environment in which the lambda expression was evaluated to produce the procedure. A new binding, which associates the procedure object with the symbol square, has been added to the global frame. In general, define creates definitions by adding bindings to frames.

So, let's analyze each arrow.

1. "global env" → the square. This arrow appears to simply be labeling the square as symbolizing the global environment. Notably, this environment is the only stack frame alive since define was called in the global environment.

2. "square" → the two dots. This arrow appears to be stating that whatever those two dots represent is stored at the name "square" which is found in the global environment.

3. left dot → "parameters"/"body". This arrow indicates that the left dot is an "object" thought to be storing two pieces of data, the "list of formal parameters" and the "procedure body".

4. right dot → the square. This arrow indicates that the right dot contains a "pointer" back to the global environment.

---

This diagram is giving a highly operational POV on how symbols derive meaning in Lisp. In particular, a symbol is "evaluated" in a particular "context". A context is a linked list of "environment frames" each containing some set of name→value mappings. To evaluate a symbol one follows that linked list and returns the first value which is mapped from the symbol's name. Diagrammatically an example would be

"foo" → { "bar" : 3    →  { "foo" : 8 }   →   { "foo" : 10 }
        , "baz" : 4 }

where evaluating foo returns 8 by "skipping" the first frame and finding the value 8 in the second frame while ignoring the third frame. This ignoring feature is important---it suggests that some contexts might have names which shadow values from larger contexts.

---

So the whole picture here is indicating the following:

1. Calling define in the global context adds a new name→value mapping to the global frame.

2. Storing a lambda object stores two pieces of information (two dots)

   • The left dot contains the text of the body of the lambda along with a listing of the symbols which are to be considered "formal parameters".

   • The right dot contains a reference to some stack frame which may or may not be the global frame, although it happens to be the global frame in this picture

Finally, we ought to talk about what it means to evaluate a lambda. To evaluate a lambda you must pass it a list of values. It uses that list of input values and matches them against the formal parameter list it stored in order to generate a new environment frame which maps formal parameters to input values. Then, it evaluates the body of the lambda using that new frame as the primary frame and the linked frame as the follow-up context. Diagrammatically, let's say square looked like

        +--- Formal parameter list
       /   +--- Body of function
       |   |
(left: (x) (* x x))    (right: {global frame})

Then when we evaluate it like (square 3) we create a new frame using 3 and the formal parameter list

{ "x" : 3 }

and evaluate the body. First we look up the name *. Since it's not in our new local frame we have to find it in the global frame.

"*"   →   { "x" : 3 }   →   { global frame }

It turns out to exist there and is the definition of multiplication. We thus need to pass it some values so we look up "x"

"x"   →   { "x" : 3 }   →   { global frame }

since x is stored in the local frame we find it there and pass 3 and 3 as arguments to the multiplication function we found.

The important part is that the local frame shadows the global frame. That means that if x also had meaning in the global frame we would override it in the context of evaluating the body of square.

---

Finally, as I was asked to answer this question in context of questions about what the meaning of "variable" is---it's important to note that the above is a very particular implementation of a very particular semantics of variables. At its surface, you can always say that "variables in lisp mean exactly this process occurs". That can be a little challenging to work with, though.

Another semantics of the word "variable" (one which I and much of mathematics favor) is the idea that a variable in a context stands for a particular, fixed but unknown value in a domain. If we examine the definition of the lambda in the body of square

(lambda (x) (* x x))

we see that this is more-or-less the intended semantics of this phrase---in interpreting (* x x) we see x as being some value value (e.g. a number) but one that we don't know anything about. In interpreting (lambda (x) (* x x)) we see that in order to understand the meaning of the phrase inside of the lambda we must provide it a meaning of x. This is roughly the standard semantics of variables and functions used everywhere.

The challenge is that the stack frame implementation described here is also set up to easily violate this semantics---in fact, it does so very subtly in this example. To be particular: define breaks semantics. The reason is apparent in the following fragment of code

(define foo 3)
foo
(define foo 4)
foo

In this fragment we evaluate each phrase sequentially and see that the (supposedly "fixed but unknown") value of the variable foo changes from line 2 to line 4. This is because define allows us to edit the stack frame that's live in a context rather than merely create a new context which shadows the old one like lambda does. This means that we must consider variables as not "fixed but unknown" but instead a series of mutable slots which cannot be guaranteed to maintain their value over time---a much more sophisticated semantics which perhaps should force us to call foo an "slot" or an "assignable".

We can also see this as a leaky abstraction. We would like variables to have the standard "fixed but unknown" semantics, but due to the mechanism of stack frames and the behavior of define we do not completely adhere to that meaning.

As a final note, Lisps often give you a form called let which can be used to replicate the previous example without throwing away variable semantics:

(let ((foo 3))
  foo
  (let ((foo 4))
    foo)
  foo)

In this case, the foo on line 2 takes the value 3, the foo on line 4 exists within a different variable context and thus only shadows the foo on line 2... and thus takes the different fixed value 4, finally the foo on line 5 is again identical to the foo on line 2 and takes the same value.

In other words, let allows us to create arbitrary local contexts (coincidentally by creating new stack frames behind the scenes as you might expect). The golden rule which lets us know theses semantics are safe is called, slightly misfortunately, α-conversion. This rule states that if you rename a variable everywhere and uniformly within a single context then the meaning of the program does not change.

Thus the previous example is, by α-conversion, identical in meaning to this one

(let ((foo 3))
  foo
  (let ((bar 4))
    bar)
  foo)

and perhaps slightly less confusing since we no longer need to worry about the effects of shadowing foo.

---

So can we make Lisp's define semantics safer? Kind of. You might imagine the following transformation:

1. Disallow cyclic dependencies in sets of define, e.g. (define x y) (define y x) is disallowed while (define x 3) (define y x) isn't.
2. Move all defines up to the very beginning of any given context (stack frame) and put them in dependency order.
3. Make it an error to "redefine" any variable

It turns out that this transformation is a little tricky (code movement is tough and so can be cyclic dependencies) but if you iron out some small problems you'll see that in any context a variable can only take exactly one fixed-but-unknown value.

You'll also find the following to hold---any program of the following, transformed form

(define x ... definition of x ...)
(define y ... definition of y ...)
(define z ... definition of z ...)
... body ...

is equivalent to the following

(let ((x ... definition of x ...))
  (let ((y ... definition of y ...))
    (let ((z ... definition of z ...))
      ... body ...)))

which is another way of showing that our nice, simple "variable as fixed but unknown quantity" semantics hold.

这篇关于三个问题w.r.t.评估的环境模型的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！