compiler-construction - 仅将环境的相关子集传递给 eval 的方案解释器

Question

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

例如，考虑以下表达式:

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

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

当然，一般来说我们无法事先知道某个值是否会被使用。我正在寻找一种粗略的语法方法(也许基于编译器优化技术？)，这比每次递归调用 eval 时遍历大部分环境来过滤掉不相关的值更有效。 p>

(背景:我的quest编写一个内存Scheme解释器。)

Answer 1

当然:对于每个子表达式计算 free variables该子表达式的一部分，并以某种方式将其附加到 AST。然后，在每次递归调用 eval 时，将环境限制为仅包含您要计算的表达式的自由变量。

编译器通常在 lambda 边界执行此操作，以避免创建保留对不必要值的引用的闭包，因为保留这些引用可能会阻止对象被 GC 回收。即对于以下程序

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

lambda 表达式的闭包将包含 x 的值，但不包含 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))))

原因是相同的:尽早删除引用意味着可以更快地释放对象。 (这也意味着它们不会被捕获的延续所持有，类似于闭包情况。)Google“safe for space”了解更多信息。