Subject: order of loading & a style questin
From: Erik Naggum <erik@naggum.no>
Date: 1997/07/18
Newsgroups: comp.lang.lisp
Message-ID: <3078224960031803@naggum.no>


the general problem is simply stated: sort the set of function and macro
definitions in an application topoligically so that all of them are defined
before they are used.  I believe this has a reasonably straight-forward and
mechanizable general solution, so won't waste time on it.

but my specific problem is similarly simply stated, although I see no easy
route to the solution: how to _rewrite_ a set of functions and macros to
remove conflicts when the topological sort does not return a proper the
loading order?

this particular case arose in GNU Emacs recently, so I have the opportunity
to discuss the code.  (I didn't solve it when I faced the same problem with
propritary code this spring, but resorted to "remembering" how to do things
depending on the loading order.  yuck.)

GNU Emacs has recently acquired a "customization facility" (written by Per
Abrahamsen) that collects user-settable variables (called "user options")
into a hierarchy of groups, with predefined sets of default values, types,
etc, with a clickable user interface to select values.  all very neat.

however, after some discussion, a user option to select the radix of
numeric quoted-insert was added.  (i.e., C-q 377 in the old, octal days now
depends on a variable for the radix.)  the problem arose when this was to
be loaded into the bare Emacs.  the function that reads character numbers
for C-q is in the first file that Emacs loads (subr.el), but the custom.el
package is loaded much later.  here's the naive solution, done first:

(defcustom read-quoted-char-radix 8
  "*Radix for \\[quoted-insert] and other uses of `read-quoted-char'.
Legitimate radix values are 8, 10 and 16."
  :type '(choice (const 8) (const 10) (const 16))
  :group 'editing-basics)

`defcustom' is a macro that compiles to a call to `custom-declare-variable'
which does a lot of hairy work, calling a lot of other functions depending
on the keywords supplied.  of course, `custom-declare-variable' and all the
other functions were not defined at this time, so this didn't work.

the problem is that we couldn't move custom.el before subr.el, nor could we
move the functions into subr.el at this point because almost everything
loaded after subr.el depends on stuff defined therein, and custom.el would
have be rewritten nearly completely to work with the bare Emacs.  we
_could_ have moved `read-quoted-char' and this user option out of subr.el,
but this opens up a whole Pandora's box of reorganizing things, and we're
hard pressed for time before the release of Emacs 20.  a quick and dirty
solution needed to be found.

this is what I proposed, as a principle.  (`push' and `pop' aren't defined
at this time, either, but they translate to pure bytecode under compilation
(i.e., no function calls), so there's no harm in using them in compiled
code.  there is a glimmer of hope in this particular fact, but let me not
digress.)

at the top of subr.el

;;; Delay evaluation of `defcustom' forms until custom.el is loaded.
(defvar custom-declare-variable ())
(defun custom-declare-variable (&rest arguments)
  (push arguments custom-declare-variable))

and at the end of custom.el:

;;; Evaluate any delayed `defcustom' forms.
(while custom-declare-variable
  (apply #'custom-declare-variable (pop custom-declare-variable)))
(makunbound 'custom-declare-variable)

and I felt this was so dirty that it should probably be done in a macro to
hide the internals, but the purpose of this solution was to make it
possible to keep the `defcustom' forms and write all code as usual instead
of forcing the programmer to remember load order.  I felt this was a noble
purpose, and much better than I did in the code I wrote for pay, which was
precisely what RMS implemented instead of my suggestion:

at the top of subr.el:

(defvar custom-declare-variable-list nil
  "Record `defcustom' calls made before `custom.el' is loaded to handle them.
Each element of this list holds the arguments to one call to `defcustom'.")

;; Use this rather that defcustom, in subr.el and other files loaded
;; before custom.el.
(defun custom-declare-variable-early (&rest arguments)
  (setq custom-declare-variable-list
	(cons arguments custom-declare-variable-list)))

and then the `defcustom' form from above was rewritten into this:

(defvar read-quoted-char-radix 8
  "*Radix for \\[quoted-insert] and other uses of `read-quoted-char'.
Legitimate radix values are 8, 10 and 16.")

(custom-declare-variable-early
 'read-quoted-char-radix 8 
 "*Radix for \\[quoted-insert] and other uses of `read-quoted-char'.
Legitimate radix values are 8, 10 and 16."
  :type '(choice (const 8) (const 10) (const 16))
  :group 'editing-basics)

and this was added to the end of custom.el:

;; Process the defcustoms for variables loaded before this file.
(while custom-declare-variable-list
  (apply 'custom-declare-variable (car custom-declare-variable-list))
  (setq custom-declare-variable-list (cdr custom-declare-variable-list)))

the principle is the same, but with a few notable variations:

(1) a different way to do `defcustom' for early code is introduced.
(2) a differently named function does the early work than the real work.
(3a) this solution leaves "residue" after it.
(3b) no function is redefined and no variable nuked.


I hope I have demonstrated two very different approaches to solve a problem
I believe is very common in Lisp applications, namely load order conflicts,
which I believe is different from the load-order problem in loading
libraries of discrete functions from a set of library files, because this
latter problem has the easy solution of listing a library from which to
extract unresolved problems several times if a dependency circularity is
discovered.

the problem I ran into when I had written a lot of code to lift the level
of abstraction in my application and I had incrementally compiled that code
while writing it, was that I had lost track of their compile and load
order.  I kept close track of users of macros and recompiled functions as
macro definitions changed, but when I took the disk with me to my client
and tried to compile it again (with a much less capable Lisp), I had to
spend a whole day rewriting my code so it would have a well-defined load
order.  with the aid of the cross referencing database in Allegro CL (for
Unix), I managed to keep from repeating the blunder by periodically doing
topological sorts on the functions and fixing problems, but this still Felt
Wrong.

in the Emacs case, which is much simpler, it would have been possible to
move the code around, and I started to look at ways to do that before I
gave up and wrote the redefining hack above.


ok, my questions to others I'm sure have had to deal with this:

(1) do you write code manually in clearly defined "steps of abstraction"
    (as opposed to "layers of abstraction") such that each step defines the
    abstraction level possible in the next step during compilation, or

(2) do you have tools to help you write at the proper level of abstraction
    for a given "position" in the load order, or

(3) do you arrange for your code to be compiled and loaded into an image
    iteratively in a way such that conflicts like this disappear or at
    least don't show up?

since incremental compilation made the problem (appear to) go away for me,
and I had to put in some really boring hours to make it _really_ go away, I
imagine others have done something smarter with this problem.

could it be called a bootstrapping problem?

(please quote sparingly -- I only tried to establish a sound context.)

#\Erik
-- 
Microsoft Pencil 4.0 -- the only virtual pencil whose tip breaks.