Dumping data structures with circular references.

[Richard Lamson <rsl%max-fleischer.ila-sf.dialnet.symbolics.com@RELAY.CS.NET>]

    Date: Thu, 2 Nov 89 11:06 PST
    From: Robert D. Pfeiffer <RDP@ALAN.LAAC-AI.Dialnet.Symbolics.COM>

    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.  

My solution for this is pretty non-general as well, although the idea is
generic.  The trick is that you need to have unique identifiers for your
objects, and refer to them via the unique ID's instead of via the objects
themselves.

For example, my :FASD-FORM method for a DLIST-ELEMENT might be something
like this:

   `(find-or-create-dlist-element
      :unique-id ',(unique-id self)
      :next ,(and next (unique-id next))
      :previous ,(and previous (unique-id previous)))

The function FIND-OR-CREATE-DLIST-ELEMENT maintains a database of uniquely-
named objects which, as the name implies, are created the first time they
are mentioned.

For a more complicated object, I might be tempted to write this slightly
differently:

  `(let ((whatever (find-or-create-whatever ',(unique-id self))))
     (setf (whatever-next whatever) (find-or-create-whatever ',(unique-id next))
	   (whatever-previous whatever) (find-or-create-whatever ',(unique-id previous))
	   ;;; more initializations here
	   )
     whatever)

Of course, you have to weigh convenience of writing your FASD-FORM against
the efficiency of loading -- remember that the form is handed to EVAL, which
is not the world's fastest function.  You can make FIND-OR-CREATE-WHATEVER
do something like this instead:

(defun find-or-create-whatever (unique-id &rest make-instance-options)
  (let ((whatever (gethash *whatever-table* unique-id)))
    (when whatever
      (apply #'initialize-whatever whatever make-instance-options)
      (return-from find-or-create-whatever whatever)))
  (setf (gethash *whatever-table* unique-id)
	(apply #'make-whatever make-instance-options)))

The functions MAKE-WHATEVER and INITIALIZE-WHATEVER would massage keyword
arguments like :NEXT and :PREVIOUS from the unique-id to the result of
FIND-OR-CREATE-WHATEVER at load time.  The last time I wrote a piece of
software which did this, I had a macro which permitted the programmer to
declare the "keys" for an object (i.e., the unique-id) and also the "finder"
functions which convert a keyword argument to the underlying object via
FIND-OR-CREATE-WHATEVER; the macro constructed the DEFFLAVOR form, the
:FASD-FORM method, the FIND-OR-CREATE-WHATEVER function, the
INITIALIZE-WHATEVER method, and the MAKE-WHATEVER function.