lisp中的循环指针

Question

在完成CLRS Intro to Algorithms一书并试图在常见的lisp中实现红黑二叉搜索树时,我遇到了以下问题:圆形指针:

(defstruct node (ptr nil))

(defparameter *x* (make-node))

(defparameter *y* (make-node :ptr *x*))

(setf (node-ptr *x*) *y*)

此代码导致堆耗尽错误,可能是由于指针指向指向该指针的指针等引起的无限递归.

有没有办法防止这种无限递归发生,同时保持这里给出的指针结构？

我知道还有其他方法可以实现红黑树(例如,不使用setf),但我有兴趣在CLRS中复制命令式样式,因为常见的lisp是一种多范式语言.

PS.除了通常的左子指针和右子指针之外,CLRS中的BST还有父指针.

Answer 1

Lisp中的循环没有问题.Common Lisp甚至有一个特殊的语法用于在读取时表达它:例如,类似于#1=(#1# . #1#)缺点,它们的元素都是缺点:你可以通过类似的表达式显式构造它

(let ((c (cons nil nil)))
  (setf (car c) c
        (cdr c) c))

然而,有是当一个问题印刷结构,其可包含圆形度.为了正确地执行此操作,您需要一种称为出现检查的东西:当您打印对象(特别是具有组件的对象)时,您需要跟踪是否已经看过此对象,以及是否已安排打印参考,CL通过打印进行#n#,其中n是一个整数,它告诉读者 - 人类读者和Lisp读者 - 这对应于哪个对象,因此他们/它可以重建结构,包括它的共享.更糟糕的是,#n=当你开始打印它时,你必须注释每个可能共享的对象(with ),这将是非常糟糕的,或者避免打印任何东西,直到你遍历所有对象以知道你需要注释哪些对象.

发生检查在空间上计算成本很高(或者在20世纪80年代,当CL被标准化时似乎如此:当然它仍然可以用于非常大的结构),因此它不是CL打印机的默认行为,而是受控制的通过一个特殊的变量*print-circle*:如果这是真的那么圆形(实际上是一般的共享结构)检测由打印机完成; 如果它是假的,则不是,并且打印机可能在打印圆形结构时无限循环或递归.

请注意,问题比圆形更通用:如何打印此对象:

(let ((c1 (cons nil nil))
      (c2 (cons nil nil)))
  (setf (car c1) c2
        (cdr c1) c2))

好吧,我们可以像这样明确地构造它:

(#1=(nil) . #1#)

这就是它的打印方式,如果 *print-circle*是真的,因为在这种情况下,读者会检测共享结构并正确打印.以下是所有这些的演示:

(let ((unshared (cons (cons nil nil) (cons nil nil)))
      (shared (cons (cons nil nil) nil))
      (circular (cons nil nil)))
  ;; construct the sharing explicitly rather than via syntax
  (setf (cdr shared) (car shared)
        (car circular) circular
        (cdr circular) circular)
  (with-standard-io-syntax
    (let ((*print-circle* nil))         ;it is anyway
      ;; don't print cicrular!
      (pprint unshared)
      (pprint shared))
    (let ((*print-circle* t))
      (pprint unshared)
      (pprint shared)
      (pprint circular)))
  ;; be careful not to return anything possibly toxic to the printer
  (values))

这将打印

((NIL) NIL)
((NIL) NIL)
((NIL) NIL)
(#1=(NIL) . #1#)
#1=(#1# . #1#)

请注意,某些非常古老的Lisps(特别是InterLisp)使用引用计数进行存储管理,而语言没有循环参数计数器的问题.我确信没有现代语言使用引用计数.