circular structures and bin files

["David L. Andre" <DLA@diamond.s4cc.symbolics.com>]

    Date: 22 Dec 87 14:08:50 EST
    From: Timothy Daly <DALY@ibm.com>

    Symbolics cannot handle the following in a compile-file.

    (defun foo () '#1=(#1#))

    This will fail complaining that bin files cannot handle
    circular objects. We create circular objects all over the
    place in our data structures and need to write them out.
    Symbolics customer service recommends that we un-circularize
    the objects first. Ha.

Please don't trivialize customer service's recommendations.  They are
made for a reason, however antagonistic you want to be.

    Does anyone have a fix for this behavior?

Circular structures cannot be constants in compiled functions, and
cannot be dumped into BIN files.  Some reasons are:

(1) BIN file format.  When loading BIN files, lists are not entered into
the BIN hash table until after all their elements have been initialized.
This is an artifact of the format of BIN files, which we cannot change
incompatibly in minor releases.  (Note that arrays are entered into the
BIN hash table as soon as they are created, and before they are
initialized, so it is possible to dump circular references to arrays.)

(2) Instances.  Instances, including user-defined flavors with
:FASD-FORM methods, are not entered into the BIN hash table until they
are created.  There is no real way around this, since the :FASD-FORM
method returns an initialized object.  A completely new protocol would
have to be created, and in order to dump circular structures including
instances, all participating instances would have to obey the new
protocol.

(3) Circular list detection overhead.  A very large amount of list data
is stored in typical BIN files.  Yes, even files which contain "only"
compiled functions.  Storing every sublist pointer into a hash table on
the off chance that there will be a pointer to it later in the file is
prohibitive in time and space, both at dump- and load-time.

Note that the problem is deeper than you might at first suspect.  For
example, the following function can return NIL if dumped and reloaded.
It always returns NIL in 7.2.

(defun foo ()
  (let ((one '#1=(a b c))
	(two '#.(cdr '#1#)))
    (eq (cdr one) two)))

(4) The detection of lists circular in the CDR is only brain-damage, and
could be fixed.  But the reason it hasn't been fixed is that the other,
more fundamental problems, haven't been fixed.

(5) Memory Reordering.  The part of the system which copies constants to
localize them with compiled functions does no circularity checking.  In
7.1 this is done only by the Optimize World command (or SI:REORDER-MEMORY), 
but in 7.2 it is done whenever functions are defined.  (In 7.2, your
function will not even compile with c-sh-C.)

(6) Resources.  As far as I am aware, there has not been much demand for
the ability to dump circular structures to BIN files.

Workarounds:

(I believe this is what Customer-Service told you.)  There are two
problems to get around here.  

First, although circular structures cannot be stored in BIN files,
arbitrary function calls can.  So while (defvar *foo* '#1=(#1#)) will
not work, (defvar *foo* (make-circular-structure)) will work.

Second, although compiled functions cannot have constant references to
circular structures, they can reference variables which contain circular
structures.  So you can do (defun foo () *foo*), using the variable
defined above, and you now have equivalent functionality.

And of course, with the power of Lisp you can even hide most of the gory
details from users.  Since you incited me, I spent 10 minutes and consed
up some macrology at the end which may give you some ideas.

The BIN-dumper and loader are distributed sources.  You're welcome to
play with them and send suggestions.

Finally, I don't mean to sound condescending or to imply that we don't
intend to do something about this.  We do, just not for 7.2.

-------------------------------------------

(DEFPROP DEFUN-WITH-CIRCULAR-REFERENCES DEFUN ZWEI:DEFINITION-FUNCTION-SPEC-TYPE)

;; This is the same as DEFUN, but within the body you can use
;; CIRCULAR-REFERENCE instead of QUOTE when you have a circular structure
;; you want to use as a constant.
(DEFMACRO DEFUN-WITH-CIRCULAR-REFERENCES
	  (FUNCTION-NAME ARGLIST &BODY BODY &ENVIRONMENT ENV)
  (MULTIPLE-VALUE-BIND (DECLARATIONS REAL-BODY)
      (LT:FIND-BODY-DECLARATIONS BODY ENV)
    (LET* ((CONSTANT-INIT-ALIST NIL)
	   (TRANSFORMED-BODY
	     (LT:COPYFORMS
	       #'(LAMBDA (SUBFORM KIND USAGE)
		   (DECLARE (IGNORE USAGE))
		   (COND ((AND (NULL KIND) (EQ (CAR SUBFORM) 'CIRCULAR-REFERENCE))
			  (LET ((NEW-SUBFORM (TRANSFORM-CONSTANT (CADR SUBFORM)))
				(VARIABLE (GENSYM)))
			    (PUSH `(DEFVAR ,VARIABLE ,NEW-SUBFORM) CONSTANT-INIT-ALIST)
			    VARIABLE))
			 (T SUBFORM)))
	       `(PROGN . ,REAL-BODY)
	       :ENVIRONMENT ENV)))
      `(PROGN
	 ,@(REVERSE CONSTANT-INIT-ALIST)
	 (DEFUN ,FUNCTION-NAME ,ARGLIST
	   (DECLARE (SYS:FUNCTION-PARENT ,FUNCTION-NAME DEFUN-WITH-CIRCULAR-REFERENCES))
	   ,@DECLARATIONS
	   ,TRANSFORMED-BODY)))))

;; This function turns a structure into a form which can generate it at load time.
;; You would obviously want to use something different.
(DEFUN TRANSFORM-CONSTANT (X)
  `',X)

(DEFUN-WITH-CIRCULAR-REFERENCES FOO (A B)
  (DECLARE (SYS:DOWNWARD-FUNARG A))
  (LIST A B
	(CIRCULAR-REFERENCE (FOO BAR BAZ))
	(CIRCULAR-REFERENCE (ZIPPY THE PINHEAD))))