我如何为用 C 实现的解释语言提供垃圾收集？
How can I provide garbage collection for an interpreted language implemented in C?
如果我要在 C 中实现垃圾收集解释语言，我如何在不编写自己的垃圾收集器的情况下提供精确的（即不保守的）垃圾收集？有图书馆吗？如果有，是哪些？我知道我必须为垃圾收集器跟踪的任何对象维护某些不变量。
在实现这种语言时，您的解释器需要跟踪它 运行 程序中的所有对象，包括了解它们的类型以及数据的哪一部分是对其他数据的引用。然后，您可以轻而易举地遍历所有数据并实现您喜欢的任何类型的垃圾收集器。没有像试图确定 C 实现的 "heap"/"stack"/等的伪造黑客。定位或猜测可能需要什么指针，因为您正在处理您知道其结构的数据。
对于 C 程序，有 2 个选项：替代 malloc 的 Boehm GC（它是 保守 GC，所以可能与您想要的不完全一样因为，但它要么 that 或...)，要么 write your own。
但是自己编写并不难。执行 mark-sweep 算法。用于标记的根集将是您的符号 table。并且您将需要另一个 table 或链表来跟踪所有可以 freed 分配的内存。当您扫过 分配列表时，free 任何没有标记的东西。
实际编码当然会更复杂，因为你要遍历这两种数据结构，但算法本身很简单。你可以的。
几年前，我发现自己在同一个搜索中，这些是（而且 AFAIK 仍然是）结果。自己编写是非常有益和值得的。
在实践中，随着 Basile 的回答触及，还会出现许多其他问题。
如果垃圾收集器是从调用堆栈的深处调用的（可能是通过需要更多内存的分配例程），则必须注意其句柄仍保存在 C 函数的局部变量中的任何分配在调用堆栈中，而不是保存到它们的符号-table 或数据库位置。在我的后记解释器中，我通过使用所有分配器都推送到的临时堆栈来处理这个问题。这个堆栈在所有子程序返回后被主循环清除，并且在标记期间它被认为是根集的一部分。在我的 APL 解释器中，我每次都在主循环周围调用 GC。对于小语言的小程序来说，速度问题不如更可怕的内存泄漏更重要，至少在影响我的圈子里是这样。
如果你想要精确 GC（不是保守的GC，比如Boehm's GC, which performs quite well in practice) you should track local pointer (to GC-ed data) variables, or else invoke the GC only with a nearly empty call stack when you are sure there are no such local variables (btw, the GCC compiler has such a mark&sweep garbage collector - 带有由一些专门的gengtype C++代码生成器生成的标记例程； GGC 仅在 between passes 被调用）。当然，您还应该跟踪全局（包括静态或线程本地）指针（指向 GC 数据）变量。
或者，有一些字节码虚拟机（比如 Ocaml GC 的 OCaml or NekoVM have), then the local GC-ed variables are those in the stacks and/or registers of your bytecode VM, and you trigger your GC at specific and carefully chosen points of your VM interpreter. (See this explanation）。
您应该阅读有关 Garbage Collection techniques, see the GC handbook 的更多信息。
如果您的 GC 正在复制分代，则需要实施写屏障（以处理旧数据指向新区域的突变）。你可以使用我的旧 Qish GC (which I don't maintain much anymore), or Ravenbrook's MPS，或者编写你自己的分代复制 GC（这在理论上并不难，但在实践中调试 GC 是一场噩梦，所以工作量很大）。
您可能想使用一些宏技巧（就像我的 Qish 所做的那样）来帮助保持局部变量。请参阅 Ocaml 文档的 Living in harmony with the garbage collector 部分作为示例（或查看 Qish 内部）。
请注意，分代复制 GC 在手动编写的 C 代码中处理起来并不友好（因为您需要显式保留本地指针，并且因为您需要写屏障来记住旧值何时被修改为具有指针到新一代）。如果你想这样做，你的 C 代码应该在 A-normal form (you cannot code x=f(g(y),z); but you need to code temp=g(y); x=f(temp,z); and add temp as a local variable, assuming that x, y, z are local GC-ed variables and that both f and g return a GC-ed pointer). In practice it is much easier to generate the C code. See my MELT domain specific language (to extend and customize GCC) 作为例子。
如果您的语言确实是多线程的（多个修改器线程并行分配），那么编写 GC 代码就会变得非常棘手。这可能需要几个月的工作（调试起来可能是一场噩梦）。
实际上，我今天会推荐使用 Boehm 的 GC（注意它是多线程友好的）。朴素的标记清除手工编码 GC 可能不会比 Boehm 的 GC 快。而且你将无法（我不推荐）使用 GGC，GCC 内部的垃圾收集器（恕我直言，这不是很好；这是很多年前的肮脏的 hack 设计）。
顺便说一句，您可以考虑 自定义 - 例如MELT- the GCC compiler (by adding some application specific __attribute__ or #pragma) to help your GC. With some work, you could generate some of the marking routines, etc. However, that approach might be quite painful (I really don't know). Notice that MELT (free software, GPLv3+) contains a copying generational GC whose old generation is the GGC heap, so you could at least look inside the code of melt-runtime.cc
PS。我也推荐Queinnec的书：Lisp In Small Pieces; it has some interesting material about GC and their connection to programming languages, and it is a great book to read when you are implementing an interpreter. Scott's book on Programming Languages Pragmatics也值得一读
如果我要在 C 中实现垃圾收集解释语言，我如何在不编写自己的垃圾收集器的情况下提供精确的（即不保守的）垃圾收集？有图书馆吗？如果有，是哪些？我知道我必须为垃圾收集器跟踪的任何对象维护某些不变量。
在实现这种语言时，您的解释器需要跟踪它 运行 程序中的所有对象，包括了解它们的类型以及数据的哪一部分是对其他数据的引用。然后，您可以轻而易举地遍历所有数据并实现您喜欢的任何类型的垃圾收集器。没有像试图确定 C 实现的 "heap"/"stack"/等的伪造黑客。定位或猜测可能需要什么指针，因为您正在处理您知道其结构的数据。
对于 C 程序，有 2 个选项：替代 malloc 的 Boehm GC（它是 保守 GC，所以可能与您想要的不完全一样因为，但它要么 that 或...)，要么 write your own。
但是自己编写并不难。执行 mark-sweep 算法。用于标记的根集将是您的符号 table。并且您将需要另一个 table 或链表来跟踪所有可以 freed 分配的内存。当您扫过 分配列表时，free 任何没有标记的东西。
实际编码当然会更复杂，因为你要遍历这两种数据结构，但算法本身很简单。你可以的。
几年前，我发现自己在同一个搜索中，这些是（而且 AFAIK 仍然是）结果。自己编写是非常有益和值得的。
在实践中，随着 Basile 的回答触及，还会出现许多其他问题。
如果垃圾收集器是从调用堆栈的深处调用的（可能是通过需要更多内存的分配例程），则必须注意其句柄仍保存在 C 函数的局部变量中的任何分配在调用堆栈中，而不是保存到它们的符号-table 或数据库位置。在我的后记解释器中，我通过使用所有分配器都推送到的临时堆栈来处理这个问题。这个堆栈在所有子程序返回后被主循环清除，并且在标记期间它被认为是根集的一部分。在我的 APL 解释器中，我每次都在主循环周围调用 GC。对于小语言的小程序来说，速度问题不如更可怕的内存泄漏更重要，至少在影响我的圈子里是这样。
如果你想要精确 GC（不是保守的GC，比如Boehm's GC, which performs quite well in practice) you should track local pointer (to GC-ed data) variables, or else invoke the GC only with a nearly empty call stack when you are sure there are no such local variables (btw, the GCC compiler has such a mark&sweep garbage collector - 带有由一些专门的gengtype C++代码生成器生成的标记例程； GGC 仅在 between passes 被调用）。当然，您还应该跟踪全局（包括静态或线程本地）指针（指向 GC 数据）变量。
或者，有一些字节码虚拟机（比如 Ocaml GC 的 OCaml or NekoVM have), then the local GC-ed variables are those in the stacks and/or registers of your bytecode VM, and you trigger your GC at specific and carefully chosen points of your VM interpreter. (See this explanation）。
您应该阅读有关 Garbage Collection techniques, see the GC handbook 的更多信息。
如果您的 GC 正在复制分代，则需要实施写屏障（以处理旧数据指向新区域的突变）。你可以使用我的旧 Qish GC (which I don't maintain much anymore), or Ravenbrook's MPS，或者编写你自己的分代复制 GC（这在理论上并不难，但在实践中调试 GC 是一场噩梦，所以工作量很大）。
您可能想使用一些宏技巧（就像我的 Qish 所做的那样）来帮助保持局部变量。请参阅 Ocaml 文档的 Living in harmony with the garbage collector 部分作为示例（或查看 Qish 内部）。
请注意，分代复制 GC 在手动编写的 C 代码中处理起来并不友好（因为您需要显式保留本地指针，并且因为您需要写屏障来记住旧值何时被修改为具有指针到新一代）。如果你想这样做，你的 C 代码应该在 A-normal form (you cannot code x=f(g(y),z); but you need to code temp=g(y); x=f(temp,z); and add temp as a local variable, assuming that x, y, z are local GC-ed variables and that both f and g return a GC-ed pointer). In practice it is much easier to generate the C code. See my MELT domain specific language (to extend and customize GCC) 作为例子。
如果您的语言确实是多线程的（多个修改器线程并行分配），那么编写 GC 代码就会变得非常棘手。这可能需要几个月的工作（调试起来可能是一场噩梦）。
实际上，我今天会推荐使用 Boehm 的 GC（注意它是多线程友好的）。朴素的标记清除手工编码 GC 可能不会比 Boehm 的 GC 快。而且你将无法（我不推荐）使用 GGC，GCC 内部的垃圾收集器（恕我直言，这不是很好；这是很多年前的肮脏的 hack 设计）。
顺便说一句，您可以考虑 自定义 - 例如MELT- the GCC compiler (by adding some application specific __attribute__ or #pragma) to help your GC. With some work, you could generate some of the marking routines, etc. However, that approach might be quite painful (I really don't know). Notice that MELT (free software, GPLv3+) contains a copying generational GC whose old generation is the GGC heap, so you could at least look inside the code of melt-runtime.cc
PS。我也推荐Queinnec的书：Lisp In Small Pieces; it has some interesting material about GC and their connection to programming languages, and it is a great book to read when you are implementing an interpreter. Scott's book on Programming Languages Pragmatics也值得一读