2

有没有一种有效的方法来构建一个仅将环境的相关子集传递给递归调用的 Scheme 解释器eval？

例如，考虑以下表达式：

(let ([x 1]
      [y 2])
  (+ x 3))

当我们评估(eval '(+ x 3) env)时，环境包含绑定{ x : 1, y : 2 }。如何编写一个高效的解释器，使得环境只包含{ x : 1 }?

当然，通常我们无法事先知道一个值是否会被使用。我正在寻找的是一种粗略的句法方法——可能基于编译器优化技术？——这比在每次递归调用时遍历大部分环境eval以过滤掉不相关的值更有效。

（背景：我对编写一个记忆方案解释器的追求。）

4

2 回答 2

3

当然：对于每个子表达式，计算该子表达式的自由变量并以某种方式将其附加到 AST。然后在每次递归调用 时eval，将环境限制为您将要评估的表达式的自由变量。

编译器通常在lambda边界处这样做以避免创建保留对不必要值的引用的闭包，因为保留这些引用可能会阻止对象被 GC'd。也就是说，对于下面的程序

(let ([x 1]
      [y 2])
  (lambda (z)  ;; free vars = {x}
    (+ x z))

表达式的闭包lambda将包含x但 not的值y。但总的来说，这样做意味着您不能使用非常简单的“帧列表”环境表示；您可能必须将其展平（或至少复制和修剪）。

一些实现也会在局部变量不再使用时（尤其是在非尾调用之前）将局部变量（不被闭包保存的变量，您希望在寄存器或堆栈中看到的那种）清零。那是，

(let ([x some-big-object])
  (f (g x) long-running-expression-not-involving-x))

可能会被翻译成低级的等价物

(let ([x some-big-object])
  (let ([tmp1 (g x)])
    (set! x #f)
    (let ([tmp2 long-running-expression-not-involving-x])
      (f tmp1 tmp2))))

原因是一样的：尽早删除引用意味着可以更快地释放对象。（这也意味着它们不会被捕获的延续所束缚，类似于关闭案例。）谷歌“空间安全”以获取更多信息。

于 2012-05-03T22:24:31.530 回答
0

死代码消除的常见编译器优化在这里可以解决问题。不使用 Y，因此可以简单地删除 Y 绑定。

为了回答如何编写高效解释器的一般问题，我建议创建一个 AST，然后使用各种优化技术（例如部分解释）多次传递它，以尽可能地预先计算和简化。

于 2012-05-06T18:03:11.540 回答