检测由 cons 细胞组成的树中的共享结构

Question

我正在编写一种编程语言（细节不相关），它使用类似 Lisp 的 cons 单元来存储数据（这使得垃圾收集器的实现变得容易）。我将不向您介绍其他所有细节，但我正在尝试编写一个函数，该函数允许用这种编程语言编写的代码检测对象何时是自引用的（例如 Lisp

#1=(#1#)

），或者是否有两个对象对象具有共享结构（例如

(#1=(123) #1#)

这是我拥有的最好的（递归）函数......

bool points_to(obj* from, obj* to) {
    if (from == NULL) return false;
    if (from == to || points_to(from->car, to)) return true;
    return points_to(from->cdr, to);
}

如您所见，如果我有一个循环列表

#1=(1 2 3 . #1#)

并调用

points_to(x, x)

，它会很容易地告诉我该列表是循环的。但是，如果我尝试另一个包含自引用对象的结构，但传入的头不是自引用的（例如

(1 2 . #1=(3 . #1))

），则上述函数将耗尽调用堆栈或永远挂起（取决于当它尝试在自引用部分中搜索自引用部分未指向的 cons 单元时，最后一次调用是否是由编译器优化的尾部调用。

显然这个问题有一个答案（有 Lisp/Scheme 实现可以在打印对象时检测到这一点，并使用

#N=

/

#N#

引用符号或功能相同的东西打印出对象），但我找不到关于这个算法实际上是什么的任何信息。

如果有帮助的话，我用 C++ 编写，而不是 Lisp，所以如果需要，我可以扫描整个图像（曾经分配的每个对象）和/或使用垃圾收集器的递归标记功能。

Answer 1

我是这样做的。可能还有更好的方法。您需要行走该物体两次。

您有一个哈希表：遍历该对象，对于每个有趣的事物，要么将其输入到表中，并将其值设置为 1，要么增加其值（如果已存在）。如果该东西已经在表中，则不要走进它，只需增加计数即可（实际上您永远不需要将其增加到 2 以上）。 “有趣”有点复杂：对于 CL 来说，conses 是有趣的，interned 符号不是，uninterned 符号是，等等。当事情不有趣时认为它们很有趣是安全的（但对于阅读输出的人来说很烦人），但当事情有趣时认为它们不有趣是不安全的）。

完成此操作后，使用上面构建的表格和计数器再次遍历对象以打印它，最初为 1。

• 如果到达一个值 > 1 的对象，请将其在表中的值设置为计数器的负值并递增计数器。这是您第一次在打印时看到此对象，因此请使用之前的计数器值

  #1=

  。
• 如果您得到的对象在表中的条目为负数，那么这是我们之前见过的另一次出现，因此请使用表中值的负数来表示

  #1#

  。

然后，您将花费很长时间才能使该东西能够在正确的位置打印consing点。