三个问题与评估的环境模型

Question

我正在阅读SICP书籍这里有关命令式编程模型.我无法理解两点中的插图:

1. 从箭头square到"对"(两个圆圈):这个箭头是什么意思？虽然在本节中,箭头表示"封闭环境",但这个特定箭头似乎并未指向环境.(square环境是global env,而不是"对")
2. 低于正确的理解:在过程定义的值中,其"代码文本"部分(左侧圆圈)没有对其中的符号的解释.它们只是"文字".只有在程序应用程序中,它们才能在应用程序的上下文/环境中获得意义.
3. 如果2是正确的,为什么需要从该environment part对(右圆)到封闭环境的箭头？(因为没有任何意义来解释过程定义中过程代码中符号的含义.)

Answer 1

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

过程对象是一对,其代码指定过程具有一个形式参数,即x,以及过程体(*xx).过程的环境部分是指向全局环境的指针,因为这是评估lambda表达式以生成过程的环境.将过程对象与符号square相关联的新绑定已添加到全局框架中.通常,define通过向框架添加绑定来创建定义.

那么,让我们分析每个箭头.

1. "全球环境"→广场.此箭头似乎只是将方块标记为象征全球环境.值得注意的是,这个环境是自从define在全局环境中调用以来唯一的堆栈框架.

2. "方"→两个点.此箭头似乎表明无论这两个点代表什么,都存储在"square"全局环境中找到的名称中.

3. 左点→"参数"/"正文".该箭头表示左点是被认为存储两个数据的"对象","形式参数列表"和"过程体".

4. 右点→广场.此箭头表示右侧点包含一个返回全局环境的"指针".

该图给出了关于符号如何在Lisp中派生意义的高度可操作的POV.特别地,符号在特定的"上下文"中被"评估".上下文是"环境框架"的链接列表,每个框架包含一组名称→值映射.要评估符号,请遵循该链接列表,并返回从符号名称映射的第一个值.以图解方式为例

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

通过"跳过"第一帧并在忽略第三帧的同时在第二帧中找到值来评估foo返回8的位置.这个忽略的特征很重要 - 它表明某些上下文可能具有从较大的上下文中影响值的名称.8

所以这里的整个图片表明以下内容:

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

2. 存储lambda对象存储两条信息(两个点)

   • 左点包含lambda主体的文本以及要被视为"形式参数"的符号列表.

   • 右侧点包含对某些堆栈帧的引用,该堆栈帧可能是也可能不是全局帧,尽管它恰好是此图片中的全局帧

最后,我们应该讨论评估lambda的意义.要评估lambda,您必须传递一个值列表.它使用该输入值列表并将它们与它存储的形式参数列表进行匹配,以生成将形式参数映射到输入值的新环境帧.然后,它使用新帧作为主帧并将链接帧作为后续上下文来评估lambda的主体.如图所示,让我们说square看起来像

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

然后,当我们评估它时,我们(square 3)使用3和形式参数列表创建一个新的框架

{ "x" : 3 }

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

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

事实证明它存在于那里并且是乘法的定义.因此我们需要传递一些值,所以我们查找"x"

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

因为x 被存储在本地帧,我们在那里找到它,并通过3与3作为参数传递给我们找到了乘法功能.

重要的是局部框架影响全局框架.这意味着如果x在全局框架中也有意义,我们将在评估主体的上下文中覆盖它square.

最后,我被要求回答在什么的"变量"的含义是问题的背景下,这个问题---需要注意的是,以上是一个非常特殊的重要执行的变量非常特别的语义.从表面上看,你总是可以说"lisp中的变量意味着这个过程恰好发生".不过,这可能有点难度.

"变量"这个词的另一个语义(我和很多数学家都喜欢的)是上下文中的变量代表域中特定的,固定但未知的值的想法.如果我们检查一下lambda体内的定义square

(lambda (x) (* x x))

我们看到这或多或少是这个短语的预期语义 - 在解释中(* x x)我们认为x是一些价值(例如数字),但我们对此一无所知.在解释中,(lambda (x) (* x x))我们看到为了理解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)

在这种情况下,foo第2行上取值3,则foo在第4行不同的可变范围内存在,因此仅阴影的foo第2行...并因此采取不同的固定值4,最后foo在第5行是再次相同在foo第2行,并采取相同的值.

换句话说,let允许我们创建任意的本地上下文(巧合的是通过在幕后创建新的堆栈帧,如您所料).让我们知道这些语义是安全的黄金法则被称为,稍微不幸的是,α转换.该规则规定,如果重命名一个变量无处不在和统一的单一范围内,则程序的含义没有改变.

因此,前面的例子通过α转换,在意义上与这个相同

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

因为我们不再需要担心阴影的影响,所以可能会稍微有点混乱foo.

那么我们可以让Lisp的define语义更安全吗？的种类.您可以想象以下转换:

1. 不允许循环依赖于集定义,例如(define x y) (define y x)是不允许的,而(define x 3) (define y x)不是.
2. 将所有defines 移动到任何给定上下文(堆栈帧)的最开头,并按顺序放置它们.
3. 将"重新define"变量变为错误

事实证明,这种转换有点棘手(代码移动很难,因此可能是循环依赖)但是如果你解决了一些小问题,你会发现在任何上下文中变量只能只取一个固定但未知的值.

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

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

相当于以下内容

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

这是另一种表明我们漂亮,简单的"固定但未知数量的变量"语义的方式.