Re: SXHASH

[Jon L White <JONL at MIT-MC>]

    I presume that the current way to reach the union of BUG-LISP
and BUG-LISPM is LISP-FORUM.  If anyone got this msg who didn't
want such unions, he probably should remove himself from LISP-FORUM;
if anyone who wants to see BUG-LISP/LISPM msgs didn't get this
note, he should be put on LISP-FORUM.   Having said that, now let
me review the (miserable) history of SXHASH, due to
    GSB@MIT-ML 10/31/80 02:37:58 Re: sxhash
    There is nothing in the "definition" of sxhash which says that it
    should be insensitive to order in a list.  This has in fact been
    considered a bug in Maclisp.  The constraint however is that
    the hash should remain constant in a given lisp implementation
    for "all time". .  .  .
    Date: 31 October 1980 02:29-EST
    From: Alan Bawden <ALAN at MIT-MC>
	.  .  .
    Is it too late to change it in MacLisp?  (I'll bet the answer to that
    one is "yes".)
The only "constraint" that we have acknowledged (QUUX, myself, Ira Goldstein,
and many others about 7 years ago) was that SXHASH should be reasonably
definable by primitive-recursion, which is to say that the SXHASH of
a cons cell should be some trivial combination of the SXHASH's of the
car and of the cdr of that cell.  In fact, contrary to ALAN's conjecture,
it has never been too late to change the definition of SXHASH, and it
was changed twice --- once to accommodate the "primitive-recursive" desire.
There has never been any desire to have differing implementations of
MacLISP agree on the value of SXHASH, but it would be nice if an EXPR-coded
version of SXHASH would maintain its programmatic characteristics regardless
of which inplementation was supporting it.
    The factors affecting a change is that many FASL files have been 
assembled with sxhash's stored in them (about the only non-trivial usage 
of SXHASH which could even notice a change between LISP version numbers); 
future incorrectness in these number would not break anything, but only slow 
down the fasload process, and perhaps require extra space for storing 
"quotified constants".  Similarly, the EXPR-HASH "feature" tries to stop
a DEFUN from happening if the symbols EXPR-HASH property (from a previously 
compiled version) is the same as the current sxhash of the expr code;  thus
this feature would be broken for old FASL files by a change to sxhash, but
the loss is only one of address-space, not one of incorrect code.  The 
solution in each case is the same:  put up with slowness until you recompile 
old fasl files.
    The first midas-coded version of SXHASH did not have the "primitive"
property, but was some kind of data-walker which just bash'd and rotl'd 
a register.  The next version was something like
 (DEFUN SXHASH-PAIR (X) (+ (ROT (SXHAXH (CAR X)) -1) (SXHASH (CDR X))))
which has the unfortunate symmetry noted.  But the possible definition
 (DEFUN SXHASH-PAIR (X) (+ (SXHASH (CAR X)) (ROT (SXHAXH (CDR X)) -1)))
has the symmetry in the car direction rather than the cdr direction;
so the latter would at least not actually enforce symmetry, as the former 
surely does, for LISP lists --  its commutativity would be less appearant.
    How important is it to change?  The price really isn't that high
(except momentarily for MACSYMA, where even one extra segment of data 
is critical) but then the gain doesn't seem to be that high either.