Circular pointers in lisp

Question

In working through the CLRS Intro to Algorithms book and attempting to implement a red-black binary search tree in common lisp, I came across the following issue with circular pointers:

(defstruct node (ptr nil))

(defparameter *x* (make-node))

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

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

This code leads to a heap-exhausted-error, presumably due to an infinite recursion caused by having a pointer to a pointer which points back to that pointer, etc.

Is there a way to prevent this infinite recursion from happening while maintaining the pointer structure given here?

I know there are other ways to implement red-black trees (without using setf, for example), but I am interested in reproducing the imperative style in CLRS as common lisp is a multi-paradigm language.

PS. The BST in CLRS have parent pointers in addition to the usual left-child and right-child pointers.

Answer 1

There is no problem with circularity in Lisp. Common Lisp even has a special syntax for expressing it at read-time: For instance something like #1=(#1# . #1#) is a cons, both of whose elements are the cons itself: you could construct this explicitly by an expression like

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

However there is a problem when printing structure which may contain circularity. In order to do this correctly you need something called an occurs check: as you are printing objects (in particular objects which have components) you need to keep track of whether you have seen this object already, and if you have you arrange to print a reference, which CL does by printing #n#, where n is an integer which tells the reader -- both the human reader and the Lisp reader -- which object this corresponds to, so they/it can reconstruct the structure, including its sharing. What's worse is that you have to either annotate each possibly-shared object (with #n=) when you start printing it, which would be terrible, or avoid printing anything until you have run over all the objects to know which ones you need to so annotate.

An occurs check is computationally expensive in space (or it seemed so in the 1980s when CL was being standardised: it still can be for very large structures of course), so it is not the default behaviour of the CL printer, but it is controlled by a special variable *print-circle*: if this is true then circularity (and in fact general shared-structure) detection is done by the printer; if it is false, it is not, and the printer may loop or recurse unboundedly when printing circular structure.

Note that the problem is more general than circularity: how should this object be printed:

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

Well, we can construct this explicitly like this:

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

And this is how it will be printed, if *print-circle* is true, because in that case the reader detects shared structure and prints it properly. Here is a demonstration of all this:

(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))

This will print

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

---

Note that certain very old Lisps (notably InterLisp) used reference-counting for storage management and while the language had no problems with circularity the reference-counter did. I'm sure no modern language uses reference-counting however.