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

Question

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

当求值程序遇到lambda表单时,它会创建一个PROC包含3个内容的对象:应用过程时要绑定在本地框架中的参数列表,函数体,以及指向它所创建环境的指针.例如:

(lambda (x) x)

会产生内部的东西,如:

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

当PROC被施加时,用于帧创造了一个新的环境和本地绑定上演那里,以允许主体与适当的绑定进行评估.此框架环境包含指向其闭包的指针,以允许在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应用,它的框架必须指向的框架conser,当存在aconser被定义,所以我不能自由的框架conser应用它之后.我不知道如何/最好的方法来释放与lambda帧相关的内存,并且还支持这种持久的高阶函数.

我可以想到一些解决方案:

• 某种类型的ARC

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

这似乎是这里隐含的内容.因此,而不是保存在PROC对象的指针,它的关闭,我想...复制封闭环境和存储指向的是 直接在单元格？这不只是将罐头更深一层并导致同样的问题吗？

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

我担心我可能会遗漏一些非常简单的东西,而且我很好奇这个过程如何在lisp和其他语言的其他实现中得到支持.我没有太多的运气寻找答案,因为这个问题非常具体,甚至对于这个实施(我承认我只是脱离了我的帽子作为学习项目)而且我能够找到的大部分内容只是解释了细节从正在实现的语言的闭包,而不是从语言实现的语言.

如果有帮助的话,这里是我的源代码中相关行的链接,我很高兴详细说明这个问题是否不够详细,无法彻底描述问题.谢谢!

Answer 1

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

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

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

更复杂的实现还具有可以为空间语义提供安全性的优点：闭包只会保留它实际引用的数据，这与简单的方法相反，闭包最终引用整个周围环境，因此可以防止 GC 收集实际上未引用但恰好在闭包捕获时的环境中的数据。