Dumping data structures with circular references.

["RDP%ALAN.LAAC-AI.Dialnet.Symbolics.COM %ALAN.kahuna.DECNET.LOCKHEED.COM"@WARBUCKS.AI.SRI.COM]

Received: from THOMAS.LAAC-AI.Dialnet.Symbolics.COM by ALAN.LAAC-AI.Dialnet.Symbolics.COM via CHAOS with CHAOS-MAIL id 4769; Thu 2-Nov-89 11:02:45 PST
Date: Thu, 2 Nov 89 11:06 PST
From: Robert D. Pfeiffer <RDP@ALAN.LAAC-AI.Dialnet.Symbolics.COM>
Subject: Dumping data structures with circular references.
To: SLUG@ALAN.LAAC-AI.Dialnet.Symbolics.COM
Message-ID: <19891102190650.0.RDP@THOMAS.LAAC-AI.Dialnet.Symbolics.COM>
Character-Type-Mappings: (1 0 (NIL 0) (:FIX :BOLD :NORMAL) "CPTFONTCB")
                         (2 0 (NIL 0) (NIL :ITALIC NIL) "CPTFONTI")
                         (3 0 (NIL 0) (NIL :BOLD NIL) "CPTFONTCB")
Fonts: CPTFONT, CPTFONTCB, CPTFONTI, CPTFONTCB

I'd like to know what people do in general to avoid the "circular
reference" problem when using SYS:DUMP-FORMS-TO-FILE.  I would guess
that this must have been solved many times but the documentation doesn't
seem to have anything to say about it.  

To make the question more concrete, I've written a toy program below
which exhibits the problem by building a simple doubly-linked list and
then trying to dump it.  The application I'm actually working on is
vastly more complicated so I am really looking for the right
philosophical approach to the issue with all of the right Software
Goodness (modularity, maintainability, extensibility, etc.).

To see the problem, simply compile the following code and the run
(MAKE-AND-DUMP-DLIST).  You will get an error that says:

1Error: The object #<DLIST-ELEMENT 501056061> is circular or self-referential.
0       1BIN files cannot deal with this; at load time the object
0       1would be needed before it has been created.

0I've tried a few approaches to avoid this problem but I don't consider
any of them particularly satisfactory.

--------------------------------------------------------------------------------
[Note: Character styles are used in the following passage of code.  For
those of you with the annoying "epsilon problem", skip to the next
section where I've stripped the style.]

2;;; A doubly-linked list.
0(defflavor 3dlist 0((head nil))
	   ()
  :initable-instance-variables)

2;;; A form to dump it to a .BIN file.
0(defmethod 3(:fasd-form dlist)0 ()
  `(make-instance 'dlist
		  :head ',head))

2;;; An element in a doubly-linked list.
0(defflavor 3dlist-element 0((next-element nil)
			  (previous-element nil))
	   ()
  :initable-instance-variables
  :writable-instance-variables
  (:conc-name nil))

2;;; And a form to dump it to a .BIN file.
0(defmethod 3(:fasd-form dlist-element)0 ()
  `(make-instance 'dlist-element
		  :next-element ',next-element
		  :previous-element ',previous-element))

2;;; A simple method to add a new element to the end of a doubly-linked list.
0(defmethod 3(add-element dlist)0 ()
  (if (null head)					2;If the list is empty...
0      (setf head (make-instance 'dlist-element))	2; add an element and we're done;
0      (let ((element head))				2; otherwise,
0	(loop						2; find the last element...
0	  until (null (next-element element))
	  do (setf element (next-element element)))
	(setf (next-element element)			2; and add a new element after it.
0	      (make-instance 'dlist-element :previous-element element))
	)))

2;;; A global variable to hold onto our test list.
0(defvar 3*dlist* 0nil)

2;;; And, finally, a simple test which shows the "circular reference" problem.
0(defun 3make-and-dump-dlist 0()
  (setf *dlist* (make-instance 'dlist))		2;Make a new (empty) doubly-linked list.
0  (add-element *dlist*)				2;And build up a few elements...
0  (add-element *dlist*)
  (add-element *dlist*)
  (sys:dump-forms-to-file #P"LOCAL:>FOO.DAT.NEWEST" (list `(setf *dlist* ,*dlist*)))	2;Now try to dump it.
0  )

--------------------------------------------------------------------------------
[Note: This is the same code as above with the style stripped.]

;;; A doubly-linked list.
(defflavor dlist ((head nil))
	   ()
  :initable-instance-variables)

;;; A form to dump it to a .BIN file.
(defmethod (:fasd-form dlist) ()
  `(make-instance 'dlist
		  :head ',head))

;;; An element in a doubly-linked list.
(defflavor dlist-element ((next-element nil)
			  (previous-element nil))
	   ()
  :initable-instance-variables
  :writable-instance-variables
  (:conc-name nil))

;;; And a form to dump it to a .BIN file.
(defmethod (:fasd-form dlist-element) ()
  `(make-instance 'dlist-element
		  :next-element ',next-element
		  :previous-element ',previous-element))

;;; A simple method to add a new element to the end of a doubly-linked list.
(defmethod (add-element dlist) ()
  (if (null head)					;If the list is empty...
      (setf head (make-instance 'dlist-element))	; add an element and we're done;
      (let ((element head))				; otherwise,
	(loop						; find the last element...
	  until (null (next-element element))
	  do (setf element (next-element element)))
	(setf (next-element element)			; and add a new element after it.
	      (make-instance 'dlist-element :previous-element element))
	)))

;;; A global variable to hold onto our test list.
(defvar *dlist* nil)

;;; And, finally, a simple test which shows the "circular reference" problem.
(defun make-and-dump-dlist ()
  (setf *dlist* (make-instance 'dlist))		;Make a new (empty) doubly-linked list.
  (add-element *dlist*)				;And build up a few elements...
  (add-element *dlist*)
  (add-element *dlist*)
  (sys:dump-forms-to-file #P"LOCAL:>FOO.DAT.NEWEST" (list `(setf *dlist* ,*dlist*)))	;Now try to dump it.
  )