memory-management - 何时在 lisp 解释器中释放闭包的内存

Question

我正在从头开始编写一个简单的 lisp 解释器。我有一个全局环境，在评估文件中的所有表单时绑定(bind)了顶级变量。当文件中的所有表单都被评估后，顶级 env 和其中的所有键值数据结构都被释放。

当计算器遇到 lambda 形式时，它会创建一个 PROC 对象，其中包含 3 个东西:当过程执行时要绑定(bind)在本地框架中的参数列表applied，函数的主体，以及指向创建它的环境的指针。例如:

(lambda (x) x)

会在内部产生类似的东西:

PROC- args: x, 
      body: x, 
      env: pointer to top level env

当应用 PROC 时，会为框架创建一个新环境，并在那里暂存本地绑定(bind)，以允许使用适当的绑定(bind)评估主体。此框架环境包含指向其闭包的指针，以允许在 THAT 内部进行变量查找。在这种情况下，这将是全局环境。在评估 PROC 主体后，我可以释放与其关联的所有单元格，包括它的框架环境，然后在没有内存泄漏的情况下退出。

我的问题是高阶函数。考虑一下:

(define conser 
    (lambda (x)
        (lambda (y) (cons x y))))

一个接受一个参数并产生另一个函数的函数，该函数将把该参数转换为您传递给它的东西。所以，

(define aconser (conser '(1)))

将产生一个函数，该函数将 '(1) 转换为传递给它的任何内容。例如:

(aconser '(2)) ; ((1) 2) 

我的问题是 aconser 必须保留指向其创建环境的指针，即 conser 是通过调用 ( conser '(1)).当aconser应用PROC时，它的frame必须指向定义aconser时存在的conser的frame ，所以我无法在应用后释放 conser 的框架。我不知道如何/最好的方法来释放与 lambda 框架相关的内存，同时也支持这种持久的高阶函数。

我能想到一些解决办法:

• 某种类型的 ARC

• 在生成时将封闭环境复制到评估的 PROC 的框架中

这似乎是暗示的here .因此，我不是将 PROC 对象中的指针保存到它的闭包中，而是...复制闭包环境并将指向 that 的指针直接存储在单元格中？这不只是将 jar 头踢得更深一层并导致同样的问题吗？

• 在读取时递归地替换高阶函数体内的标签

我担心我可能在这里遗漏了一些非常简单的东西，而且我很好奇 lisp 的其他实现和其他通常带有闭包的语言如何支持这个过程。我没有太多运气寻找答案，因为这个问题非常具体，甚至可能是这个实现(我承认我只是作为一个学习项目脱颖而出)而且我能找到的大部分内容都只是解释了细节从正在实现的语言的角度来看闭包，而不是从正在实现的语言的语言来看。

Here is a link到我源代码中的相关行，如果有帮助的话，如果这个问题不够详细，无法彻底描述问题，我很乐意详细说明。谢谢!

Answer 1

在原始解释器中通常处理此问题的方式是使用垃圾收集器 (GC) 并在 GC 堆中分配您的激活帧。因此，您永远不会显式释放这些帧，而是让 GC 在适用时释放它们。

在更复杂的实现中，您可以使用稍微不同的方法:

• 创建闭包时，不要存储指向当前环境的指针。相反，复制闭包使用的那些变量的值(它称为 lambda 的自由变量)。并更改闭包的主体以使用这些副本，而不是在环境中查找这些变量。这称为闭包转换。
• 现在您可以将您的环境视为一个普通堆栈，并在您退出范围后立即释放激活帧。
• 您仍然需要 GC 来决定何时可以释放闭包。
• 这又需要一个“赋值转换”:复制变量的值意味着如果这些变量被修改则语义会发生变化。因此，要恢复原始语义，您需要查找那些“复制到闭包中”以及“修改”的变量，并将它们转换为“引用单元格”(例如 cons 单元格，其中您将值保存在 car 中)，以便副本不再复制该值，而只是复制对保存该值的实际位置的引用。 [旁注:这样的实现显然意味着避免 setq 并使用更函数式的样式最终可能会更有效率。 ]

更复杂的实现还有一个优点是它可以提供空间安全语义:闭包只会保留它实际引用的数据，这与闭包结束的朴素方法相反向上引用整个周围环境，因此可以防止 GC 收集实际上未引用但恰好在闭包捕获时环境中的数据。