当前位置：文江博客话题详情

替代模型需要环境吗

发布于 2024-10-07 18:15:25 字数 165 浏览 1 评论 0原文

我正在为Scheme 编写一个小型评估器。

我需要使用替换模型编写评估器，因此不会使用像 set! 这样的分配。

但由于我仍然需要在某个地方存储原始过程和用户定义的变量，我需要一个环境吗？如果是这样，替代模型和环境模型有什么区别？

谢谢。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

黯然 2024-10-14 18:15:25

不——对于一个简单的基于替换的评估器，您不需要环境。这是因为一旦您进行了绑定（例如，当您执行函数调用时），您就会立即用值替换名称，因此无需保留名称->值映射。事实上，您可以将环境视为一种通过缓存替换并稍后执行替换来避免替换所涉及的开销的方法。请参阅 PLAI 获取遵循此观点的教科书 - 事实上，它从替换到替换缓存，直到后来它才将术语更改为环境。

但请注意，使用 set! 的问题与所有这些无关。当您考虑 set! 时，您首先需要明确您所讨论的 set! 的级别：是否使用您所使用的语言实现而不是在实现本身中，那么可以添加给定任何类型的可变值 - 例如，在 Racket 你可以使用 boxes 这足以实现set! 在语言中。传统上，这是在基于环境的求值器中完成的，其中环境类型从映射名称到值更改为将名称映射到位置（实现为框或类似的可变值）。但这并不是真正必要的：您仍然可以使用基于替换的求值器来做到这一点，其中这些框将成为您要替换的值域的一部分。举一个具体的例子，您可以从类似的表达式开始（使用类似方案的语言）：

(let ((x 1))
  (begin (set! x 2)
         (set! x 3)))

并且您可以分配一个包含 1 的框，而不是用 1 替换 x code>1，然后替换该相同框，导致

(begin (set! #<box> 2)
       (set! #<box> 3))

两个#是单个框。（请注意，这不是我正在谈论的实现代码，而是您正在评估的语言中的表达式。）通常不这样做的原因是它可能会令人困惑 - 您需要将值表示为框可以替换，这些框不是源用户程序的一部分，但它们是解释器应该处理的值（例如，最后一个 # 是返回值 - - 但它是您想要返回的值，而不是框），并且您需要注意框标识（例如，上面的两个框必须是相同框，这一点很重要第一个 set! 的解释在第二个中可见）。

因此，如果您刚刚学习编写解释器，不建议这样做。如果是这种情况，那么我建议你看看那本教科书。

No -- for a plain substitution-based evaluator you do not need an environment. This is because as soon as you have a binding (eg, when you perform a function call) you immediately substitute the name with the value, so there is no need to keep the name->value mapping around. In fact, you can view an environment as a way to avoid the overhead involved with substitutions by caching them and performing them later instead. See PLAI for a textbook that follows this view -- in fact, it goes from substitutions to substitution caches, and only later does it change the terminology to environments.

But note that the issue of using set! is unrelated to all of this. When you consider set!, you first need to be clear on what level of set! you're talking about: if it's in the language that you're implementing rather than in the implementation itself, then it's possible to add that given any kind of a mutable value -- for example, in Racket you can use boxes and that's enough for implementing set! in the language. This is traditionally done in an environment-based evaluator, where the environment type is changed from mapping names to values to mapping names to locations (implemented as boxes or a similar mutable value). But that's not really necessary: you can still do that with a substitution-based evaluator where these boxes are becoming part of the domain of values that you're substituting. To give a concrete example, you could start with an expression like (using a scheme-like language):

(let ((x 1))
  (begin (set! x 2)
         (set! x 3)))

and instead of substituting 1 for x you would allocate a box holding 1, then substitute that same box resulting in

(begin (set! #<box> 2)
       (set! #<box> 3))

where the two #<box>es are that single box. (Note that this is not implementation code that I'm talking about, but expressions in the language that you're evaluating.) The reason that this is not usually done is that it can be confusing -- you need to represent values as boxes that can be substituted, those boxes are not something that is part of the source user program yet they are values that the interpreter should deal with (eg, the last #<box> is the return value -- but it's the value that you want to return, not the box), and you need to be careful about box identity (eg, it is important for the two boxes in the above to be the same box for the interpretation of the first set! to be visible in the second).

So doing this is not recommended if you're just learning about writing interpreters. If this is the case, then I suggest you just look in that textbook.

回复收藏 0 原文

倾城花音 2024-10-14 18:15:25

是的，您仍然需要一个环境，因为就像您所说的，您需要能够存储变量等。

替代模型是一种帮助您了解如何评估给定过程的方法。例如，您可以定义平方函数

(define (square x) (* xx))

使用替换模型，如果您调用

(square 4)

，则将 4 替换为函数定义中每次出现的 x ，这样

(* 4 4) => 16

该环境用于让您可视化变量和状态如何存储在解释器中。简而言之，替换模型用于帮助您评估过程，而环境用于查看您的解释器如何记住用户在使用您的解释器时可能定义的变量和定义。

Yes you still need an environment because like you said you need to be able to store variables and such.

The substitution model is a way to help you see how a given procedure will be evaluated. For example, you can define the square function

(define (square x) (* x x))

With the substitution model, if you called

(square 4)

then you substitute the 4 into every occurrence of x in your function definition so

(* 4 4) => 16

The environment is used for you to visualise how variables and state are stored in your interpreter. So in a nutshell, the substitution model is used for helping you evaluate procedures while the environment is used to see how your interpreter will remember the variables and definitions that a user may define when they use your interpreter.

回复收藏 0 原文

~没有更多了~